Editorial for DMOPC '17 Contest 2 P5 - Game
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Let .
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:
For the second subtask, say that there are stones currently. The first player can win if they are allowed to take
stones on this turn. Then clearly, the player can win if they are allowed to take
stones on this turn and
. So store the least amount of stones the first player must take to guarantee a win if there are currently
stones and call this
. A DP recurrence can be found involving this array: if
is the largest number (less than
) such that
, then
. (Also,
.)
Time Complexity:
For the third subtask, finding each in the second subtask can be sped up. Previously, it took
to compute
. Using data structures such as an RMQ segment tree, this may be sped up to
.
Time Complexity:
For the fourth subtask, first note the following fact: For any with
, let
be the largest number less than
such that
. Then
. This claim can be proved by strong induction on
.
Consider an arbitrary with
and
(it is not hard to see that
for all
). Let
be the smallest number larger than or equal to
with
and
be defined as
. Then
is the least number larger than
such that
.
Proof: It can be seen from the earlier claim and from the fact that , that for any
with
, that
and also
. Now for any
with
,
. So the largest number
less than
such that
is
. So
.
So using this, all such that
can be computed. There are approximately
such
s between
and
. For each
with
, compute the number of
s such that
using the first claim. Then, using these values, the final answer can be computed using the first claim.
Time Complexity:
Comments