SRM 737, D1, 300-Pointer (AliceAndBobEasy)

James S. Plank

Mon Oct 8 11:11:00 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: September, 2018
Competitors who opened the problem: 148
Competitors who submitted a solution: 134
Number of correct solutions: 101
Accuracy (percentage correct vs those who opened): 68.2%
Average Correct Time: 25 minutes, 24 seconds.

This problem sucks.

Either you know the optimal NIM strategy or you don't. I guess you're supposed to Google NIM and read the optimal solution. I tried to use my brain instead, and that was a failing endeavor. There's no way I was deriving the Sprague-Grundy theorem while doing a Topcoder problem. So it goes.

So, I'll tell you the Sprague-Grundy theorem as is applies to this problem, and let you think about a solution: If the XOR of all of the pile sizes is zero, then you are in a losing position. It's an if-and-only-if. So, here are some losing positions:

{ 5, 4, 1 }
{ anything, anything }
{ 1, 2, 4, 8, 16, 31 }

So, the challenge in this problem is to come up with n pile sizes that don't XOR to zero, and such that for each pile, you can lower its number of stones, and the resulting piles will XOR to zero. When the number of piles is odd, you can do this for all n piles. When the number of piles is even, you can only do it for n-1 piles -- you will be unable to do it for the smallest pile. You can prove that if you want, but I'm over proofs and the stupid Sprague-Grundy theorem, so just take my word on it.

So what I'll do now is let you think about and solve the problem, which I'll state formally:

Come up with n numbers, x₀, x₁, ..., x_n-1 with the following properties:
The x_i are distinct.
Each x_i ≤ 737,373,737.
Define S to be the XOR of all x_i.
S cannot equal zero.
For each x_i come up with a number y_i such that 0 ≤ y_i < x_i, and (y_i XOR x_i XOR S) equals zero.
Or, put another way, (x_i XOR S) must be < x_i.
If n is even, you won't be able to come up with y_i for the smallest x_i.

Now, I'm going to let you think about this and solve it. If you get stuck, read below.

Let's think about the odd case. Here's what I'd like: Every x_i should have the same highest bit set. And the lowest bits can be anything, so long as the x_i are distinct, and S doesn't equal zero.

This will work, because (x_i XOR S) will have an even number of highest bits, so the highest bit will equal zero. Therefore, (x_i XOR S) has to be less than x_i.

The highest number allowed is 737,373,737, which is 0x2bf36e29, which is between (1 << 29) and (1 << 30). So, my highest bit should be in position 28, because all numbers that start with that bit will be less than 0x20000000. My first thought was to have:

x_i = (1 << 28) | (1 << i).

However, since n can be as high as 37, that won't do. Instead, I decided to make it (using integer division):

x_i = (1 << 20) | (1 << (19-i/2)) | (i%2).

(I could have used 28 and 27 in place of 20 and 19, but 20 and 19 are big enough, and the numbers look more managable).

When n is 5, for example, that gives you the following values (in binary);

11000000000000000000
11000000000000000001
10100000000000000000
10100000000000000001
10010000000000000000

Since n is odd, it's clear that S won't equal zero, so this works.

When n is even, do the same thing, but have x_n-1 equal one.

If you want to double-check yourself, here are the answers for examples 0, 1, 2 and 3. For example 3, I've made n equal to 10:

UNIX> a.out 0
1572864
UNIX> a.out 1
1572864
1
UNIX> a.out 2
1572864
1572865
1310720
UNIX> a.out 3
1572864
1572865
1310720
1310721
1179648
1179649
1114112
1114113
1081344
1
UNIX>