SRM 699, D1, 250-Pointer (OthersXor)

James S. Plank

Sun Sep 18 22:59:27 EDT 2016

Adding some notation

First, let's think about the wolves who answer -1. If there are more than one of them, then we only have to worry about one of them, because we can set all of the others to zero. So, let's create a second vector, which we'll call W, which is composed of all of the answers that are not -1. And let's have a boolean, U, which is true if any wolves answer -1.

Let's use examples 0, 1 and 3 to make this clearer:

Example 0:
W = { 1, 3 }
U = true
Example 1:
W = { 0, 0, 1 }
U = false
Example 3:
W = { 0, 100, 36 } 
U = true

Let's add another vector to the equation. I'll call this the "answer" vector, A. Let the size of W be s. Then, the size of A is also s, and we define A[i] to be the integers chosen by the wolfs who answered W[i]. We'll also define a value R, which is the integer chosen by the wolf that answered -1. If U is false, we'll set Rto zero. If U is true, then R is flexible.

In example 0, the topcoder writeup tells us that the three wolf's answers are 2, 1 and 0. That means that:

A[0] = 2
A[1] = 0
R = 1

Dealing with bits

The fact that we're dealing with XOR's means that we should be looking at the bits. In fact, we can consider each bit of the various W's, A's and R independently. Let's look at example 0 in a different way -- I'm going to draw the two A's, the two W's, and R vectors of bits, with the least significant bit on the top. I'm also going to draw two more column vectors, T and B, which I'll define below:

T is a column vector of bits. Each bit in row i of T is equal to the XOR of all of the A values in its row, and R.

B is a column vector of integers. Each value in row i of B is equal to the sum of all of the A values in its row, and R.

Now, each row of the system composes an independent problem, which we'll state as follows: For each row, we want to determine the values of A and R that are legal given the constraints of our problem, so that B is minimized. Then, row i will contribute B(2i) to the final sum.

Where does this T value fit in?

We are going to focus on just one row of the system now, so that all of the W's, A's, R and T are bits, and B is a single integer.

Here's how we use T. Suppose we affix the value of T. Then, we can calculate A[j] as the XOR of T and W[j]. Think about that until you can convince yourself that it's true. Let's use row 0 of example 0 to illustrate. Suppose T is zero. Then, here is row 0 of the system:

We can set A[0] to be (T XOR W[0]), which equals 1, and A[1] to be (T XOR W[1]), which also equals 1:

Now, since T needs to be the XOR of all of the A's, and R, this means that we can set R to be zero. And since B equals the sum of the A's and R, we can set B to two. Here's our completed system:

Suppose instead, we set T to be one. Then our system will look as follows:

Since that's the smaller value of B, we use that setting in our final answer. Let's do the same thing for the second row (bit 1) of the system. Here's what happens when you set T to zero:

And when you set T to one:

Putting it all together

So, your steps to solving this problem are as follows:
My solution.