Editorial for WC '18 Contest 3 S3 - Counterpicking

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.

For each Pokémon trainer $i$ ~i~, let $R_i = X_i/Y_i$ ~R_i = X_i/Y_i~. We can observe that this ratio is sufficient to determine which of Jessie's Pokémon is optimal to use against that trainer. We can furthermore observe that each of Jessie's Pokémon is either never optimal, or is optimal for a single interval of ratios.

Our objective will be to pre-process Jessie's set of $N$ ~N~ Pokémon into a sequence of Pokémon $P_{1 \dots K}$ ~P_{1 \dots K}~ and corresponding splitting points $S_{1 \dots (K-1)}$ ~S_{1 \dots (K-1)}~, such that $P_1$ ~P_1~ is optimal for ratios in the interval $(-\infty, P_1)$ ~(-\infty, P_1)~, $P_2$ ~P_2~ is optimal for ratios in the interval $[S_1, S_2)$ ~[S_1, S_2)~, and so on, with $P_K$ ~P_K~ being optimal for ratios in the interval $[S_{K-1}, \infty)$ ~[S_{K-1}, \infty)~. If we can perform this pre-processing, then we'll be able to obtain the answer for each trainer $i$ ~i~ in $\mathcal O(\log N)$ ~\mathcal O(\log N)~ time by binary searching on $S_{1 \dots (K-1)}$ ~S_{1 \dots (K-1)}~ for the interval containing $R_i$ ~R_i~, and using the corresponding optimal Pokémon.

Given two of Jessie's Pokémon $i$ ~i~ and $j$ ~j~, let's consider when one is more optimal than the other. If $A_i = A_j$ ~A_i = A_j~, then whichever Pokémon has a larger $B$ ~B~ value is simply always better. Otherwise, if we assume that $A_i < A_j$ ~A_i < A_j~ and let $f(i, j) = \frac{B_j-B_i}{A_i-A_j}$ ~f(i, j) = \frac{B_j-B_i}{A_i-A_j}~, then the two Pokémon are equally optimal for the ratio $f(i, j)$ ~f(i, j)~, Pokémon $i$ ~i~ is more optimal for all ratios smaller than $f(i, j)$ ~f(i, j)~, and Pokémon $j$ ~j~ is more optimal for all ratios greater than $f(i, j)$ ~f(i, j)~.

Given that fact, let's sort Jessie's Pokémon in non-decreasing order of $A$ ~A~ values and then iterate over them in that order, while ignoring any which are known to never be optimal (due to having an equal $A$ ~A~ value to another Pokémon and a smaller $B$ ~B~ value). As we go, we'll maintain our sequence $P$ ~P~ of optimal Pokémon, which is initially empty. Each time we process a new Pokémon, we'll add it onto the end of $P$ ~P~, but first we may need to remove zero or more Pokémon from the end of $P$ ~P~ if their intervals of optimal ratios have been rendered empty. For example, if the last two Pokémon in $P$ ~P~ are $P_{K-1}$ ~P_{K-1}~ and $P_K$ ~P_K~, we're currently processing Pokémon $i$ ~i~, and $f(P_{K-1}, P_K) > f(P_K, i)$ ~f(P_{K-1}, P_K) > f(P_K, i)~, then there is no ratio for which Pokémon $P_K$ ~P_K~ is optimal, and it should be removed from $P$ ~P~.

Sorting Jessie's Pokémon takes $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~ time, and then processing them to generate the sequence $P_{1 \dots K}$ ~P_{1 \dots K}~ takes another $\mathcal O(N)$ ~\mathcal O(N)~ time. The sequence of splitting points $S_{1 \dots (K-1)}$ ~S_{1 \dots (K-1)}~ may then be generated based on it in $\mathcal O(N)$ ~\mathcal O(N)~ time, with $S_i = f(P_i, P_{i+1})$ ~S_i = f(P_i, P_{i+1})~ for each $i$ ~i~. Finally, we can use this to compute the optimal answers for all of the Pokémon trainers as described above, bringing the total time complexity up to $\mathcal O((N+M) \log N)$ ~\mathcal O((N+M) \log N)~.

Comments

There are no comments at the moment.