“This is the third day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Topic describes

This is 2029. Stone Game IX on LeetCode, medium difficulty.

Tag: game Theory

Alice and Bob take turns, with Alice taking the lead. Each turn, you need to remove one of the stones from the stones.

If the player removes stones so that the total value of all removed stones is divisible by 333, the player loses the game. If the previous rule is not met and there are no stones left after removal, Bob wins directly (even on Alice’s turn). Assume that both players make the best decision. Returns true if Alice wins; If Bob wins, return false.

Example 1:

Stones = [2,1] output: true explanation: the game proceeds as follows: - round 1: Alice can remove any stone. - Turn 2: Bob removes the remaining stones. The total value of the removed stones is 1 + 2 = 3 and is divisible by 3. So Bob loses and Alice wins.Copy the code

Example 2:

Input: stones = [2] Output: false Explanation: Alice removes the only stone, and the total value of the removed stones is 2. Since all stones have been removed and the sum of values is not divisible by 3, Bob wins.Copy the code

Example 3:

Input: stones = [5,1,2,4,3] output: false One possible way to play the game is as follows: - Turn 1: Alice can remove the second pebble with a value of 1. The total value of the removed stones is 1. - Turn 2: Bob can remove the 5th stone with a value of 3. The total number of removed stones is = 1 + 3 = 4. - Turn 3: Alices removes the fourth stone with a value of 4. The total number of removed stones is = 1 + 3 + 4 = 8. - Turn 4: Bob can remove the third stone with a value of 2. The total value of the removed stones is = 1 + 3 + 4 + 2 = 10. - Round 5: Alice can remove the first stone with the value of 5. The total number of removed stones is = 1 + 3 + 4 + 2 + 5 = 15. Alice loses the game because the total number of removed stones (15) is divisible by 3, and Bob wins.Copy the code

Tip:


  • 1 < = s t o n e s . l e n g t h < = 1 0 5 1 <= stones.length <= 10^5

  • 1 < = s t o n e s [ i ] < = 1 0 4 1 <= stones[i] <= 10^4

Let’s talk about the game case by case

For convenience, we use A for Alice and B for Bob.

There’s only one way for A to win, and that’s if B chooses A multiple of 333; In addition to allowing A to make A multiple of 333, B can also win by allowing the game to end as usual.

So throughout the game, we only care about the “total number of stones removed” and the “number of remaining stones/value situation”.

Further, we only need to care if the total number of stones removed is a multiple of 333, and if the value of the remaining stones added to the total number of stones removed makes a multiple of 333.

So we can divide the value of the stones by the remainder of 333 into three groups and count the corresponding numbers.

Without loss of generality, before the start of a turn, the total state of the stones removed is XXX (there are three kinds, dividing by 333, the remainder is 000, 111 and 222 respectively. If the state is 000 and not the first turn, it means that the multiple of 333 is reached and the game is over). The SSS of the remaining stones divided by 333 are 000, 111 and 222, respectively.

First of all, if the current
x = 1 x = 1 “, cannot choose
s = 2 s = 2 Otherwise, the sum will be zero
3 3 Multiple of and fail; In the same way
x = 2 x = 2 “, cannot choose
s = 1 s = 1 Stones; And choose
s = 0 s = 0 That’s not going to change
x x Can be seen as a hand change operation.

Simultaneous paired
s = 0 s = 0 Is equivalent to nothing
s = 0 s = 0 Stones (both sides only need to take turns to choose these
s = 0 s = 0 Of stones, will eventually return to the first hand at the beginning of the situation); The selection and
x x The same
s s Can lead to
x x Change (i.e.,
x = 1 x = 1 When choosing
s = 1 s = 1 The number of pebbles will cause
x = 2 x = 2 ; while
x = 2 x = 2 When choosing
s = 2 s = 2 The number of pebbles will cause
x = 1 x = 1 ).

After making clear the rules, it is the process of discussion by case:

  • The number of stones with s=0s =0 is even: at this point, it is equivalent to that there are no stones with S =0s =0. We only need to care about S =1s =1s =1 and S =2s =2s =2:

    • The number of stones where S =1s =1s =1 is 000: This means that A can only choose s=2s =2s =2 at the beginning, and B is given the situation of “x=2x =2x =2, and only s=2s =2s =2 remaining stones”, and B can only choose the stones s=2s =2s =2. Since x=2x =2x =2 and the selected stone s=2s =2s =2, the situation handed back to A is “x=1x =1x =1, and the rest is only S =2s =2s =2”. Therefore, if the game continues, A will lose. Meanwhile, if the stone is taken out at any moment during the process, B wins directly, that is, A is still bound to lose;

    • The number of stones with S =2s =2s =2 is 000: Similarly, A can only select s=1s =1s =1. At this time, the situation handed to B is “x=1x =1x =1, only s=1s =1s =1”. At this time, B can only select the stones s=1s =1s =1. Since x=1x =1x =1 and the selected stone s=1s =1s =1, the situation handed back to A is “x=2x =2x =2, and the rest is only S =1s =1s =1”. Therefore, if the game continues, A will lose. Meanwhile, if all stones are taken out at any moment during the process, B wins directly, that is, A is still bound to lose;

    • The number of stones s=1s =1s =1 and s=2s =2s =2 is not 000: A chooses the type of stones that does not have the largest number, and B can only choose the same type of stones in the next round (or fails due to lack of choice). Then the game continues, and FINALLY B enters the situation of “only A multiple of 333”, which leads to failure. In other words, A must win.

  • The number of stones with S =0s =0s =0 is odd: At this point, it is equivalent to that there will be A change of mobile phone, and the change of mobile phone will be applied to “transfer the losing situation”. Therefore, only the difference in the number of stones between S =1s =1s =1 and S =2s =2s =2 is greater than 222, and the first-mover advantage of A will not be transferred because of the change of mobile phone:

    • The quantity difference between the two is no more than 222: at this point, B can make use of the rule of “the other party will fail if it makes a multiple of 333” and the right of “s=0s = 0S =0 stone” to ensure that it is a must win state:

      • For example, 🌰, when s=1s =1s =1 and s=2s =2s =2 have the same number of stones, although s=0s =0 stones, A is the first, but A must not choose S =0s =0s =0 in the first round, otherwise the failure will end immediately. Therefore, A can only choose s=1s =1s =1 or S =2s =2s =2. At this time, B directly chooses the stone s=0s =0, and the situation XXX handed over to A does not change, so A can only choose the same SSS game as the first round to continue. Therefore, the situation will become “B has the first hand, s=1s =1s =1 and S =2s =2s =2, the difference in the number of stones is 222”. The game will continue, and FINALLY A will encounter the situation of “only A multiple of 333” first, that is, B will win.

      • The quantity difference between the two is not more than 222: At this time, no matter A chooses less or more S, B immediately changes hands with stones of S =0s = 0S =0 in the second round. A can only continue to select stones of the same type as in the first round before the game can proceed. Finally, A will first encounter the situation of “only A multiple of 333” or “all stones are taken out”. B is going to win.

    • The difference between the two numbers is over 222: At this time, even if A only needs to ensure that A chooses A large number of SSS for the first time, regardless of whether B uses the stones of “s=0s =0” in preference, A has enough times and A large number of SSS to offset the change of hands (or uses them immediately after B gives up using S =0s =0s =0). In the end, B is the first to meet the “multiple of 333” situation, that is, A wins.

Code:

class Solution {
    public boolean stoneGameIX(int[] stones) {
        int[] cnts = new int[3];
        for (int i : stones) cnts[i % 3] + +;return cnts[0] % 2= =0? ! (cnts[1] = =0 || cnts[2] = =0) : !(Math.abs(cnts[1] - cnts[2< =])2); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.2029 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.