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

**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:

#### Solution Sketch

##### Subtask 1

The first subtask was meant to reward those who solved the problem by hand. When , the answer is . When , the answer is . When , the answer is . Finally, when , the answer is .

**Time Complexity:**

##### 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 vertices has at most edges. Thus, we are looking for the smallest value of such that the inequality holds true. This can easily be done with a linear search. It can be shown that the linear search takes time in the worst case, though solution with linear search should also pass.

**Time Complexity:**

##### 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 or . Depending on implementation, you may need to use `long double`

instead of `double`

to accurately perform floating point operations.

**Time Complexity:** or

## Comments

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

Thank you! This (also) has been fixed.

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

Thank you! This has been fixed.