Game of Towers - EDITORIAL
Author and Editorialist: kishen1912000
DIFFICULTY:
Easy
PROBLEM:
Alice and Bob are playing the following game:
- There are N buildings of Lego 1\times 1 blocks, where the i^{\text{th}} building has n_i towers.
- Each tower is just a stack of Lego 1\times 1 blocks.
- In the i^{\text{th}} building, the number of blocks in the towers are h_i, h_i+1, h_i+2,\cdots, h_i + n_i -1, in order.
- On each turn, the player picks up a building and selects one particular tower and removes non-zero number of blocks from that tower.
- The player who is left with no more blocks to pick loses.
- Alice starts the game and the players alternate turns. Both play optimally.
Given the arrangement of these blocks as buildings, find the winner of the game.
QUICK EXPLANATION:
This is an instance of the standard Nim Game with the individual towers behaving as the stacks. The only difficulty is to compute the XOR value of all the towers, as there are a lot of towers. Observe that the number of blocks in any building are consecutive integers.
Let XORS(n) denote the XOR of all integers from 1 to n. Then the XOR of all towers in the i^{\text{th}} building is XORS(h_i+n_i-1) \oplus XORS(h_i-1). And, XORS(n) can be found in \mathcal{O}(1) time, as it can take at most 4 values (see below for details).
EXPLANATION:
The first and most important observation to make here is that this problem is an instance of the standard Nim Game. In the Nim Game, we are given n stacks with r_i rocks in the i^{\text{th}} stack. Players alternate turns and pick a non-zero number of rocks from any stack. The player who has no rock to pick loses. Here, if we notice, every tower behaves as a stack in the Nim Game.
In Nim Game, if r_1\oplus r_2\oplus \cdots \oplus r_n = 0, then player two wins. Otherwise, player one wins. See here for the proof and more details.
So, essentially, we need to find XOR of all towers in the given problem and check its value. In total there are at most 10^{21} towers according to the constraints. Hence, directly computing the XOR is inefficient.
The second important observation here is that the values of the number of blocks (or heights) in each tower of a particular building are consecutive integers. This observation is crucial to solving this problem efficiently.
We will first go over a very important property of XOR, a\oplus b\oplus b = a. This behaves like a subtraction operation for XOR (something similar to a+b-b = a).
Lets define XORS(n) = 1\oplus 2\oplus \cdots \oplus n. Now, notice that a\oplus (a+1) \oplus (a+2)\oplus \cdots \oplus (b-1)\oplus b = (1\oplus 2 \oplus \cdots \oplus b)\oplus (1\oplus 2\oplus \cdots \oplus (a-1)) = XORS(a-1) \oplus XORS(b).
Now, let us see some interesting properties of XORS.
Consider any consecutive integers of the form 4n, 4n+1, 4n+2, 4n+3. In the binary representation, the last (least significant) 2 bits of these numbers are 00, 01, 10, 11, respectively.
4n = 4n
4n\oplus (4n+1) = 1,
4n\oplus (4n+1) \oplus (4n+2)= 4n+3
4n\oplus (4n+1) \oplus (4n+2) \oplus (4n+3) = 0.
Therefore, we get,
\text{XOR}(n) = \left. \begin{cases} n, & \text{if } n\%4=0\\ 1, & \text{if } n\%4=1\\ n+1, & \text{if } n\%4=2\\0, & \text{if } n\%4=3\end{cases} \right\}
Therefore, based on the above observations, the algorithm for this problem is as follows: For each building, compute the XOR value using the above formula. Next, compute the XOR value of the buildings. Finally, if the total XOR value is 0, Bob wins, else Alice wins.
Time Complexity:
Computing XOR value of each building takes \mathcal{O}(1) time, and computing the total XOR value of all buildings takes \mathcal{O}(N) time.
Running time: \mathcal{O}(N)
SOLUTIONS:
Setter's Solution
def xors(n):
if n%4==0:
return n
elif n%4==1:
return 1
elif n%4==2:
return n+1
else:
return 0
n = int(input())
ans = 0
for i in range(n):
hi,ni = [int(s) for s in input().split()]
ans = ans^xors(hi-1)^xors(hi+ni-1)
if ans==0:
print("Bob")
else:
print("Alice")