Editorial for WC '18 Contest 3 J4 - Leveling Up - Olympiads Online Judge

Editorial for WC '18 Contest 3 J4 - Leveling Up

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.

Let $Z$ $Z$ be the maximum possible position ( $Z = 100\,000$ $Z = 100 000$ ), and let $WM_p$ $W M_{p}$ and $WG_p$ $W G_{p}$ be the $M$ $M$ and $G$ $G$ values of the wild Pokémon at position $p$ $p$ (if any), with $WM_p = WG_p = 0$ $W M_{p} = W G_{p} = 0$ if there's no such Pokémon. Then, $WM_1, \dots, WM_Z$ $W M_{1}, \dots, W M_{Z}$ and $WG_1, \dots, WG_Z$ $W G_{1}, \dots, W G_{Z}$ may be populated in $\mathcal O(Z+N)$ $O (Z + N)$ time by iterating over the $N$ $N$ Pokémon.

We'll greedily simulate Jessie and Arbok's training process. Let $p_1$ $p_{1}$ be the smallest position which Jessie can currently freely reach, $p_2$ $p_{2}$ be the largest one, and $a$ $a$ be Arbok's current level. Initially, $p_1 = p_2 = S$ $p_{1} = p_{2} = S$ and $a = L$ $a = L$ .

At any point in time, if $p_1-1 \ge 1$ $p_{1} - 1 \geq 1$ and $a \ge WM_{p_1-1}$ $a \geq W M_{p_{1} - 1}$ , then Jessie is able to expand her reachable range to encompass position $p_1-1$ $p_{1} - 1$ , and has no reason not to do so. Therefore, we can increase $a$ $a$ by $WG_{p_1-1}$ $W G_{p_{1} - 1}$ , and then decrement $p_1$ $p_{1}$ . Similarly, if $p_2+1 \le Z$ $p_{2} + 1 \leq Z$ and $a \ge WM_{p_2+1}$ $a \geq W M_{p_{2} + 1}$ , then Jessie might as well expand her reachable range to encompass position $p_2+1$ $p_{2} + 1$ . Therefore, we can increase $a$ $a$ by $WG_{p_2+1}$ $W G_{p_{2} + 1}$ , and then increment $p_2$ $p_{2}$ .

We should repeat the above process of expanding Jessie's range of reachable positions left and right whenever possible until we arrive at a situation in which it cannot be expanded in either direction. At that point, nothing more can be done, and we can proceed to output the current value of $a$ $a$ .

The time complexity of the above solution is $\mathcal O(Z+N)$ $O (Z + N)$ . A similar algorithm running in $\mathcal O(N \log N)$ $O (N \log N)$ time is also possible, if we sort and consider only positions of interest (Jessie's starting position as well all wild Pokémons' positions) instead of all $Z$ $Z$ possible positions.

Comments

There are no comments at the moment.