Editorial for WC '17 Contest 2 S1 - Keeping Score


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.

At first glance, it may seem that there are 10^9 possible values of X to consider. However, we only need to bother considering at most G of them, the ones which are equal to SG_i (for some i), as it can't help Gimli to choose some other arbitrary value of X. This immediately gives us a solution with a time complexity of \mathcal O(LG), in which we try each such value of X, 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 SL_{1 \dots L} in non-increasing order (which can be done in \mathcal O(L \log L) time), and do the same with the values SG_{1 \dots G} (in \mathcal O(G \log G) time).

Let's now consider trying each possible value of X in this order, with the largest ones first. Let's skip indices i such that SG_i = SG_{i+1}. Now, when we consider X = SG_i, we can determine Gimli's score without iterating over all of his killed enemies – his score is simply i (as the values SG_{1 \dots i} are larger than or equal to X while the values SG_{(i+1) \dots G} are smaller than it).

Determining Legolas's score is trickier, but we can observe that there must be some corresponding index j such that the values SL_{1 \dots j} are larger than or equal to X while the values SL_{(j+1) \dots L} are smaller than it, meaning that Legolas's score is j. Furthermore, as i increases, X cannot increase and so j cannot decrease. Therefore, as we iterate over values of i, we can update j as necessary (incrementing it as long as SL_{j+1} \ge X), and stop if we find a value of X for which i > j.

The overall time complexity of this algorithm is \mathcal O(L \log L).


Comments

There are no comments at the moment.