Chip Game
Contest: Lyft Level 5 Challenge 2018 - Elimination Round
Difficulty rating: 3500
Tags: games

Alice and Bob decided to play one ultimate game. They have $$$n$$$ piles, the $$$i$$$-th pile initially contain $$$v_i$$$ chips. Alice selects a positive integer $$$a$$$ from interval $$$[1, m]$$$, and Bob selects a number $$$b$$$ the same way.

Then the game starts. In her turn, Alice can select any pile containing at least $$$a$$$ chips, and remove exactly $$$a$$$ chips from it. Similarly, in his turn, Bob can choose any pile with at least $$$b$$$ chips, and remove exactly $$$b$$$ chips from it. If a player cannot make a move, he or she loses.

If both players play optimally, the outcome ultimately depends on the choice of $$$a$$$ and $$$b$$$, and on the starting player. Consider a fixed pair $$$(a,b)$$$. There are four types of games:

- Alice wins, regardless of who starts.
- Bob wins, regardless of who starts.
- If Alice starts, she wins. If Bob starts, he wins. We say that the first player wins.
- If Alice starts, Bob wins. If Bob starts, Alice wins. We say that the second player wins.

Among all choices of $$$a$$$ and $$$b$$$ (i.e. for each pair $$$(a, b)$$$ such that $$$1\leq a, b\leq m$$$), determine how many games are won by Alice (regardless of who starts), how many are won by Bob (regardless of who starts), how many are won by the first player, and how many are won by the second player.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 100, 1 \leq m \leq 10^5$$$) — the number of piles, and the upper bound on the number of chips allowed to be taken in one turn, respectively.

The second line contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$1 \leq v_i \leq 10^{18}$$$) — the starting number of chips in each pile.

Output format:
Print a single line containing four integers $$$w_a$$$, $$$w_b$$$, $$$w_f$$$, $$$w_s$$$ — the number of games won by Alice, Bob, the first player, the second player, respectively.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first sample, there are a total of four choices for the tuple $$$(a,b)$$$.

- $$$a = b = 1$$$: It does not matter from which pile the chips are removed — there are $$$9$$$ turns to be made, and the first player also makes the last, and hence he wins.
- $$$a = b = 2$$$: The second player may win by always selecting the same pile as the first before there are $$$0$$$ and $$$1$$$ chips in the piles. Since it is impossible to remove $$$2$$$ chips from any of them, the first player loses.
- $$$a = 1$$$ and $$$b = 2$$$:   Suppose Alice starts. She can win by removing a single chip from the pile with $$$5$$$ chips and then copying Bob's decision. After the next four turns, the game ends with $$$1$$$ chip in each pile and Bob unable to make a move.  Suppose Bob starts. If he removes two chips from second pile, Alice counters by removing a chip from the first pile. From then on, she can always copy Bob's decision and win. If Bob removes two chips from the first pile in his first turn, Alice can also remove one. As the first pile only has one chip left, Bob is forced to remove two chips from the second pile, leaving $$$3$$$. Regardless of what Alice does, she wins.  Hence, Alice wins no matter who starts.
- $$$a = 2$$$ and $$$b = 1$$$: This is symmetric with the previous case — hence Bob always wins.

In the second sample, a lot of games, e.g. $$$a = 7$$$ and $$$b = 6$$$, end without anybody being able to remove single chip — which counts as a win for the second player. The games won for the first player are $$$(1, 1)$$$, $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(4, 1)$$$, and $$$(5, 5)$$$.

Example input:
2 2
4 5

Example output:
1 1 1 1

Example input:
2 20
4 5

Example output:
82 82 6 230

Editorial:
Let's solve the task for a fixed tuple $$$(a, b)$$$. If $$$a = b$$$, this is a very simple symmetric game, where the parity of $$$\sum \lfloor \frac{v_i}{a} \rfloor$$$ determines the winner (regardless of the players' choices).
Without loss of generality, let $$$a < b$$$ as the case where $$$a > b$$$ is symmetrical. It is obvious that Bob never has an advantage in this game. Furthermore, the game outcome doesn't change if we set $$$v'_i = v_i \mod (a + b)$$$.
To see why this is true, consider a strategy $$$S'$$$ for a winning player in the modified game $$$G'$$$, and build strategy $$$S$$$ for the original game:
• If the winner takes first turn in $$$G'$$$, take the same first turn in $$$G$$$ – this is always valid as $$$v'_i \leq v_i$$$.
• If the loser's last turn was valid in the game $$$G'$$$, follow the strategy $$$S'$$$ in the game $$$G$$$. Again, this is valid as $$$v'_i \leq v_i$$$.
• If the loser's last turn was invalid in the game $$$G'$$$, this means that he reduced the state from $$$x_1 \cdot (a+b) + y_1$$$ to $$$(x_1-1) \cdot (a+b) + y_2$$$ for some $$$x_1 > 0$$$ and $$$0 \leq y_1 < y_2 < a + b$$$. The winner can play in the same pile to reduce it to $$$(x_1-1) \cdot (a+b) + y_1$$$, and the corresponding $$$v'_i$$$ doesn't change. In essence, these two moves are a no-op in the game $$$G'$$$.
Let's break down the single pile games $$$P$$$ based on the number of chips modulo $$$a+b$$$:
1. $$$0 \leq v'_i < a$$$: As neither Alice nor Bob can make a move, this is a zero game ($$$P = 0$$$).
2. $$$a \leq v'_i < b$$$: Alice can take at least one move in this pile, and Bob none. This is a strictly positive game ($$$P > 0$$$).
3. $$$b \leq v'_i < 2a$$$: If either of the players makes a move, it changes to a zero game. This is thus a fuzzy game ($$$P || 0$$$). Note that this interval may be empty.
4. $$$\max(2a, b) \leq v'_i < a + b$$$: If Alice makes a move, she can turn this game into a positive game for her. Bob can turn this into a zero game. This is a fuzzy game ($$$P || 0$$$).
As we see, there are no negative games. Hence, in the combined game, we can ignore the zero games in our calculation (type $$$1$$$) and if there is at least one positive game (type $$$2$$$), the game is won for Alice. If there is at least one game of type $$$4$$$ and Alice starts, or at least two games of type $$$4$$$, Alice can always play one of them to make herself a positive game, thus winning. Otherwise, it is always optimal to play in a game of type $$$3$$$ or $$$4$$$ if there is one, and the game is subsequently turned into a zero game. The parity of the number of these games thus determines whether the starting player wins or loses.
For a fixed $$$(a, b)$$$, we are now able to determine the outcome of the game in $$$\mathcal O(n)$$$ time, leading to $$$\mathcal O(m^2n)$$$ total runtime, which is too slow.
To make this faster, let's group the games by the sum $$$a + b$$$. For a fixed $$$v'_i$$$, define function $$$f(a)$$$ which tells us the type of the single-pile game based on the value of $$$a$$$ for this particular $$$v'_i$$$. We can see that this function is not arbitrary – we can partition the interval $$$[0, a+b)$$$ into constantly many intervals on which the function is constant (e.g. if $$$a \in (v'_i, a+b)$$$, this is a zero game. We simply collect all these intervals for all values of $$$v'_i$$$ and using a linear sweep determine the outcome of each game. This needs $$$\mathcal O(n \log n)$$$ for sorting and $$$\mathcal O(n)$$$ for the sweep. All combined, this yields a $$$\mathcal O(m n \log n)$$$ algorithm.
Bonus: Can you get rid of the log factor?