Editorial for Wesley's Anger Contest 1 Problem 1 - Simply a Simple Simplex Problem


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

Solution Sketch

Subtask 1

The first subtask was meant to reward those who solved the problem by hand. When M = 1, the answer is 2. When 2 \le M \le 3, the answer is 3. When 4 \le M \le 6, the answer is 4. Finally, when 7 \le M \le 10, the answer is 5.

Time Complexity: \mathcal{O}(T)

Subtask 2

For the second subtask, it can be seen that in order to minimize the number of vertices, we want to create a graph where there is an edge between as many pairs of vertices as possible. It can be shown that a simple, undirected graph with N vertices has at most \frac{N \times (N - 1)}{2} edges. Thus, we are looking for the smallest value of N such that the inequality \frac{N \times (N - 1)}{2} \ge M holds true. This can easily be done with a linear search. It can be shown that the linear search takes \mathcal{O}(\sqrt{M}) time in the worst case, though solution with \mathcal{O}(M) linear search should also pass.

Time Complexity: \mathcal{O}(T \cdot \sqrt{M})

Subtask 3

For the third subtask, we can either binary search for the answer using the inequality from subtask 2, or we can make the observation that the solution is always one of \sqrt{2 \cdot M} + 1 or \sqrt{2 \cdot M} + 2. Depending on implementation, you may need to use long double instead of double to accurately perform floating point operations.

Time Complexity: \mathcal{O}(T) or \mathcal{O}(T \cdot \log{M})


Comments


  • 2
    Narcariel  commented on April 13, 2020, 10:59 a.m.

    For Subtask 2, isn't it, an undirected graph with N vertices has at most N x (N-1)/2 edges?


    • 1
      wleung_bvg  commented on April 13, 2020, 12:57 p.m.

      Thank you! This (also) has been fixed.


  • 2
    YaySushi  commented on Dec. 29, 2019, 9:40 p.m.

    For subtask 1, second sentence, it should be "when M = 1".


    • 2
      wleung_bvg  commented on Dec. 30, 2019, 6:31 a.m.

      Thank you! This has been fixed.