Editorial for DMOPC '17 Contest 2 P5 - Game

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.

Author: r3mark

Let $Z=\max(X, Y)$ ~Z=\max(X, Y)~.

For the first subtask, keep a 2-D boolean array storing if the first player can win given a certain state. The states are number of stones remaining and number of stones player is allowed to take on this turn. This array can be computed using DP.

Time Complexity: $\mathcal O(Z^3)$ ~\mathcal O(Z^3)~

For the second subtask, say that there are $N$ ~N~ stones currently. The first player can win if they are allowed to take $A$ ~A~ stones on this turn. Then clearly, the player can win if they are allowed to take $B$ ~B~ stones on this turn and $B \ge A$ ~B \ge A~. So store the least amount of stones the first player must take to guarantee a win if there are currently $N$ ~N~ stones and call this $dp[N]$ ~dp[N]~. A DP recurrence can be found involving this array: if $M$ ~M~ is the largest number (less than $N$ ~N~) such that $dp[M]>N-M+K$ ~dp[M]>N-M+K~, then $dp[N]=N-M$ ~dp[N]=N-M~. (Also, $dp[0]=\infty$ ~dp[0]=\infty~.)

Time Complexity: $\mathcal O(Z^2)$ ~\mathcal O(Z^2)~

For the third subtask, finding each $dp[N]$ ~dp[N]~ in the second subtask can be sped up. Previously, it took $\mathcal O(N)$ ~\mathcal O(N)~ to compute $dp[N]$ ~dp[N]~. Using data structures such as an RMQ segment tree, this may be sped up to $\mathcal O(\log N)$ ~\mathcal O(\log N)~.

Time Complexity: $\mathcal O(Z \log Z)$ ~\mathcal O(Z \log Z)~

For the fourth subtask, first note the following fact: For any $M$ ~M~ with $dp[M] \ne M$ ~dp[M] \ne M~, let $N$ ~N~ be the largest number less than $M$ ~M~ such that $dp[N]=N$ ~dp[N]=N~. Then $dp[M]=dp[M-N]$ ~dp[M]=dp[M-N]~. This claim can be proved by strong induction on $M-N$ ~M-N~.

Consider an arbitrary $N_1$ ~N_1~ with $dp[N_1]=N_1$ ~dp[N_1]=N_1~ and $N_1 \ge K+2$ ~N_1 \ge K+2~ (it is not hard to see that $dp[N]=N$ ~dp[N]=N~ for all $1 \le N \le K+2$ ~1 \le N \le K+2~). Let $N_3$ ~N_3~ be the smallest number larger than or equal to $N_1-K$ ~N_1-K~ with $dp[N_3]=N_3$ ~dp[N_3]=N_3~ and $N_2$ ~N_2~ be defined as $N_1+N_3$ ~N_1+N_3~. Then $N_2$ ~N_2~ is the least number larger than $N_1$ ~N_1~ such that $dp[N_2]=N_2$ ~dp[N_2]=N_2~.

Proof: It can be seen from the earlier claim and from the fact that $dp[N_2-N_1]=N_2-N_1$ ~dp[N_2-N_1]=N_2-N_1~, that for any $N$ ~N~ with $N_1<N<N_2$ ~N_1<N<N_2~, that $dp[N] \ne N$ ~dp[N] \ne N~ and also $dp[N]=dp[N-N_1] \le N_3-(N-N_1)+K=N_2-N+K$ . Now for any $N$ ~N~ with $0<N \le N_1$ ~0<N \le N_1~, $dp[N] \le N = N-(N_1+N_1-K)+K \le N-(N_1+N_3)+K = N-N_2+K$ . So the largest number $M$ ~M~ less than $N_2$ ~N_2~ such that $dp[M]>N_2-M+K$ ~dp[M]>N_2-M+K~ is $0$ ~0~. So $dp[N_2]=N_2$ ~dp[N_2]=N_2~.

So using this, all $N$ ~N~ such that $dp[N]=N$ ~dp[N]=N~ can be computed. There are approximately $\log_2 Z$ ~\log_2 Z~ such $N$ ~N~s between $K+2$ ~K+2~ and $Z$ ~Z~. For each $N$ ~N~ with $dp[N]=N$ ~dp[N]=N~, compute the number of $M$ ~M~s such that $dp[M]=1$ ~dp[M]=1~ using the first claim. Then, using these values, the final answer can be computed using the first claim.

Time Complexity: $\mathcal O(\log Z)$ ~\mathcal O(\log Z)~

Comments

There are no comments at the moment.