Editorial for COCI '07 Contest 1 #3 Prinova

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.

A solution that iterates over all odd numbers from $[A, B]$ ~[A, B]~ and calculates the distance to the nearest name is too slow for the given constraints.

Let us solve a modified version of the problem where the solution can be odd or even. Then the solution is one of the following:

$A$ ~A~
$B$ ~B~
$(P_i+P_j)/2$ ~(P_i+P_j)/2~, for every pair $i, j$ ~i, j~

For each solution candidate, we first check if it falls inside $[A, B]$ ~[A, B]~ and then find the distance to the nearest name. The solution is thus the number that maximizes that distance.

In the original problem, only odd solutions are allowed. To account for this, we simply substitute each even solution candidate $X$ ~X~ with numbers $X-1$ ~X-1~ and $X+1$ ~X+1~.

Comments

There are no comments at the moment.