Tag Archives: xor

Hackerrank Weekly Challenge #7 // Problem 2: Chocolate in Box

If you want to me write an editorial to problem 3, 4 or 5 from Hackerrank Weekly Challenge #7, let me know in the comment section down below.

Problem statement

The problem is available here.

There are 1 \leq n \leq 10^6 stacks numbered from 1 to n. The i-th stack contains 1 \leq a_i \leq 10^9 objects. Two players are playing the following game with the stacks:

Players takes turns. Player 1 starts. In each turn, the current players can remove any number of objects from any single non-empty stack and he has to remove at least one object. The player who is unable to make a move loses. The task is to decide, how many different moves players 1 can take in the first turn in order to win a game. Both players play optimally.

Solution

If you've hear about the game of Nim, you probably already recognized it here. If not, read about it and remember, because this is one of the most fundamental games in game theory.

The theorem says:

The player making the first move has a winning strategy if and only if XOR of the binary representations of sizes of the stacks is nonzero.

In order to solve the problem, you have to decide, how many ways are to select the stack and take some number of object from it, in such a way, that the XOR of sizes of the remaining stacks equals 0, because then player 2 loses and you win. Let \oplus be the symbol of XOR operation.

The first basic observations is that:

a\oplus b = 0 if and only if a = b.

In order to get the answer for the problem, we have to examine every stacks and add 1 to the result, if we can make a move on this stacks. The fact is that in one move, we can take some objects only from one stack, so the other stacks remain the same. We will examine every stack separately.

Let's assume that we examine the i-th stack and let L = a_1 \oplus a_2 \ldots a_{i-1} \oplus a_{i+1} \ldots a_n - the XOR of sizes of all stacks without stack i. Based on above observation, we are interested in taking some number of a_i objects is such a way, that the number of remaining objects on this stack equals L. Obviously, we can do it if and only if L < a_i , because we have to take at least one object, so we can make the XOR of all stacks equal 0 for any 0 \leq L < a_i.

The time complexity of this solution is O(n). You can compute L for every stacks using prefix/suffix sums for XOR or by "unxoring".