Official

F - Final Stage Editorial by evima

Hints

Hint 1 There are several ways to analyze the outcome of the game, but what would be a good choice for this problem?

Hint 2 Let’s apply backward analysis to the game.

Hint 3 At any point in the game, the outcome, “win for the player moving first,” “win for the player moving second,” or “draw”, can be determined by the number of stones remaining in the pile.
Moreover, (though it is obvious,) the set of numbers of stones that lead to each outcome can be represented as the union of several integer intervals \([l,r]\).
With a strong focus on the idea that “the numbers of stones that result in the same outcome form several intervals,” let’s apply backward induction again.

Hint 4 Let’s apply backward analysis to the sample.
  • Initial state: \([0,\infty)\)=Draw
  • Second player’s move \([1,2]\): \([0,0]\) = First player wins, \([1,\infty)\)=Draw
  • First player’s move \([3,4]\): \([0,2]\) = Second player wins, \([3,4]\)=First player wins, \([5,\infty)\)=Draw
  • Second player’s move \([1,2]\): \([0,0]\) = First player wins, \([1,4]\)=Second player wins, \([5,5]\) =First player wins, \([6,\infty)\)=Draw
  • First player’s move \([1,3]\): \([0,0]\) = Second player wins, \([1,3]\) =First player wins, \([4,5]\)=Second player wins, \([6,8]\) =First player wins, \([9,\infty)\)=Draw

Let’s consider what is happening in this backward analysis.


Hint 5 Suppose it’s the first player’s turn to take between \([L,R]\) stones. A backward analysis of this turn reveals the following:
  • If the number of stones left in the pile is within \([0,L-1]\), then the second player wins.
  • A previous winning interval for the first player \([A,B]\) moves to \([A+L,B+R]\). This interval can overlap with others.
  • A previous winning interval for the second player \([A,B]\) moves to \([A+R,B+L]\). If this interval collapses, it vanishes.

From here on, it becomes a data structure problem. Let’s try to perform this backward analysis efficiently.

Hint 6 For now, let’s ignore the complications of intervals collapsing or overlapping.
Then, updates always involve all winning intervals for the first player expanding by length \(l\) and all winning intervals for the second player shrinking by length \(l\) (or the opposite).

Hint 7 At any point, when arranging intervals, the pattern of the outcomes has one of the following forms:
  • …(First player wins)(Second player wins)(First player wins)(Draw)
  • …(Second player wins)(First player wins)(Second player wins)(Draw)
This shows that “collapsing intervals” and “overlapping intervals” are two sides of the same coin.
We should be familiar with a data structure that is convenient for “collapsing an interval at any position” → “merging the neighboring intervals if necessary.”

Hint 8 In Hint 6, we have the operation of “expanding or shrinking all intervals by the same length,” which can be handled by maintaining offsets corresponding to the lengths of the intervals and only adjusting the base value.
The convenient data structure mentioned in Hint 7 is a linked list. Let’s also make use of this.

posted:
last update: