FIZZBUZZ2305 - Editorial


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

Authors: naisheel, jalp1428
Tester: tabr
Editorialist: iceknight1093






Alice and Bob play a game with an integer N, taking turns with Alice going first.
On their turn, a player must choose an odd prime factor of N, and subtract it from N.
Whoever cannot move loses.

Find the winner if both play optimally.


Let’s get an edge case out of the way first: if N = 1, Alice cannot make a move at all and loses.

Now, let’s look at N\gt 1.
Let p be an odd prime factor of N.
Then, note that p is also an odd prime factor of N-p, since N is itself a multiple of p.

This allows Bob to win whenever N is even, by just copying Alice!

  • If Alice doesn’t have any moves, she loses.
  • Otherwise, Alice makes some move and N becomes N-p.
    Now, since N is even and p is odd, we surely have N-p\gt 0 (since N-p will be odd).
  • From our earlier observation, p divides N-p so Bob can always make this move, leading to N-2p (which is even).
  • This way, Bob can never lose: he can just copy Alice’s move at each step.

This also tells us that Alice can always win when N is odd (and greater than 1), since:

  • If N is a prime, Bob will receive N-N=0 and lose.
  • Otherwise, N being odd means N always has an odd prime factor p; and Bob will receive N-p which is even.
    Now the roles are reversed: after the first move, Alice can copy Bob’s moves and never lose.

This gives us a straightforward solution: Alice wins if N is odd and \gt 1, Bob wins otherwise.


\mathcal{O}(1) per testcase.


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

can any one simplify the observation