SRM 699, D1, 250-Pointer (OthersXor)

James S. Plank

Sun Sep 18 22:59:27 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: September, 2016
Competitors who opened the problem: 370
Competitors who submitted a solution: 182
Number of correct solutions: 154
Accuracy (percentage correct vs those who opened): 41.6%
Average Correct Time: 33 minutes, 38 seconds.

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(2ⁱ) 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:

First, calculate U, which is true or false, depending on whether any wolves answered -1.
Next, create W which is a vector of all of the answers that are not -1.
Then, for each bit i from 0 through 31, do the following:
Set T equal to 0, and calculate bit i of each A from T and W.
Calculate R to be the XOR of T and the A's. If U is false, R has to equal zero for this answer to be legal. If the answer is legal, then calculate B to be the sum of the A's and R
Now, repeat this process for T equal to 1. If both of the B values are illegal, then return -1. Otherwise, add the smaller B(2ⁱ) to the answer.

My solution.