Editorial for Wesley's Anger Contest 1 Problem 1 - Simply a Simple Simplex Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 a 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