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).

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)

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

Time Complexity: \mathcal O(Z^2)

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

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

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

Consider an arbitrary N_1 with dp[N_1]=N_1 and N_1 \ge K+2 (it is not hard to see that dp[N]=N for all 1 \le N \le K+2). Let N_3 be the smallest number larger than or equal to N_1-K with dp[N_3]=N_3 and N_2 be defined as N_1+N_3. Then N_2 is the least number larger than N_1 such that 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, that for any N with N_1<N<N_2, that 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 with 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 less than N_2 such that dp[M]>N_2-M+K is 0. So dp[N_2]=N_2.

So using this, all N such that dp[N]=N can be computed. There are approximately \log_2 Z such Ns between K+2 and Z. For each N with dp[N]=N, compute the number of Ms such that 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)


Comments

There are no comments at the moment.