Editorial for WC '17 Contest 2 S1 - Keeping Score
Submitting an official solution before solving the problem yourself is a bannable offence.
At first glance, it may seem that there are possible values of to consider. However, we only need to bother considering at most of them, the ones which are equal to (for some ), as it can't help Gimli to choose some other arbitrary value of . This immediately gives us a solution with a time complexity of , in which we try each such value of , and tally up Legolas and Gimli's scores for it (by iterating over all of their killed enemies) to determine whether it's valid.
However, the above solution isn't efficient enough to receive full marks. To do better, let's start by sorting the values in non-increasing order (which can be done in time), and do the same with the values (in time).
Let's now consider trying each possible value of in this order, with the largest ones first. Let's skip indices such that . Now, when we consider , we can determine Gimli's score without iterating over all of his killed enemies – his score is simply (as the values are larger than or equal to while the values are smaller than it).
Determining Legolas's score is trickier, but we can observe that there must be some corresponding index such that the values are larger than or equal to while the values are smaller than it, meaning that Legolas's score is . Furthermore, as increases, cannot increase and so cannot decrease. Therefore, as we iterate over values of , we can update as necessary (incrementing it as long as ), and stop if we find a value of for which .
The overall time complexity of this algorithm is .
Comments