ADD12GAME - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Alice and Bob play a game.
They start with X = 0, and then the players add either 1 or 2 to it, alternating turns.
The game ends when X \geq N.
If X = N Bob wins, otherwise Alice wins.

Alice starts first. Who wins?

EXPLANATION:

If N = 1, clearly Alice wins by just adding 2 to X. This is also showcased in the samples.

In general, notice that since each player adds either 1 or 2, the game will end with either X = N or X = N+1.
So, the only way for Alice to win is if X = N+1 in the end; which in turn can only happen when X = N-1 and the current player adds 2.

Of course, if X = N-1 on his turn, Bob will never add 2 - he will just add 1 and reach X = N, hence winning.
This means Alice’s only hope of winning, is to herself receive N-1, and then add 2 to it.

However, as it turns out, when N \gt 1 Bob can always ensure that Alice doesn’t receive N-1.
In other words, if N \gt 1, Bob always wins!

How?

Since N \gt 1 and we start with X = 0, certainly X \neq N-1 on Alice’s first turn.

Now,

  • If Bob receives X = N-1 or X = N-2 on his turn, he can simply add 1 or 2 respectively and reach X = N, immediately winning.
  • Otherwise, Bob will receive X such that X \leq N-3.
    He can simply always add 1, so that Alice will receive X \leq N-2 (in particular, it doesn’t equal N-1).

This way, Alice can never win.

In summary, Alice wins N = 1 and loses otherwise.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    print('Alice' if n == 1 else 'Bob')
2

For N = 9, consider this case:
A = Alice, B = Bob

A-2, B-4, A-6, B-8, A-10

A(Alice) now has X = 10 > 9, so Alice wins.

So, there is a possibility that Alice will win.
Because it’s not clearly defined what it means to play optimally?

3

Let’s analyze the game step-by-step to understand the strategy for both Alice and Bob.

Case when N = 3:

  • Alice can start by adding either 1 or 2.
  • In both scenarios, Bob can add the other number (2 or 1, respectively) and reach 3, winning the game.
  • Thus, Bob always wins when N = 3, as he can always make the sum reach 3.

Case when N = 4:

  • If Alice starts by adding 1 (making the total 1), Bob has two options:
    • If Bob adds 1, the total becomes 2, and Alice wins by adding 2 to reach 4.
    • If Bob adds 2, the total becomes 3, and Alice wins by adding 1 to reach 4.
  • If Alice starts by adding 2 (making the total 2), Bob can simply add 2 and reach 4, winning the game.
  • Thus, Alice’s optimal strategy when N = 4 is to start by adding 1, as this forces a win. If she starts with 2, she loses.

Case when N = 5:

  • Alice should start by adding 2 (making the total 2), forcing Bob into a losing position:
    • Bob can either add 1, making the total 3, or add 2, making the total 4. In both cases, Alice can win by adding the remaining number to reach 5.
  • Therefore, Alice wins when N = 5 by starting with 2.

Case when N = 6:

  • If Alice adds 1 (making the total 1), Bob can add 2 to make the total 3, where he can guarantee a win by following a similar strategy to the N = 3 case.
  • If Alice adds 2 (making the total 2), Bob can add 1, making the total 3, again leading to a winning position for Bob.
  • Therefore, Bob wins when N = 6, as he can always reduce the game to N = 3, where he has a guaranteed win.

General Strategy:

From the examples above, we can see a pattern:

  • Bob wins if he can reduce the game to a scenario where N is a multiple of 3.
  • To achieve this, Bob can always add the number that makes the current total a multiple of 3 (if Alice adds 1, Bob adds 2, and vice versa).
  • Therefore, Bob has a winning strategy when N is a multiple of 3.
  • Conversely, if N is not a multiple of 3, Alice can force Bob into a losing position by carefully choosing her moves.

Conclusion:

  • Bob wins if N is a multiple of 3.
  • Alice wins otherwise, by forcing Bob into a losing position.
1 Like