SRM 737, D1, 300-Pointer (AliceAndBobEasy)

James S. Plank

Mon Oct 8 11:11:00 EDT 2018

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:

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:

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 xi should have the same highest bit set. And the lowest bits can be anything, so long as the xi are distinct, and S doesn't equal zero.

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

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:

xi = (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):

xi = (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 xn-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>