How to solve Game of Bullets from the recent contest Code Hard?

Link- https://www.codechef.com/COHA2019/problems/BULLETS
I realise that by seeing others solutions that the answer will be Gaitonde if the XOR of all numbers is non-zero or Isa otherwise(if zero), but can anybody explain the logic behind it?

1 Like

It’s the game of Nim in (a bit of a) disguise.

The reasons why the xor trick works is due to the Sprague Grundy Theorem.

Hackerrank have a Game Theory section with lots of nice practice problems :slight_smile:

3 Likes

So quick! Did you take part in the contest? Anyway I was solving problems after the contest was over and I found the 5th problem easier then this one. I couldn’t crack this.

1 Like

No, that contest was too short for me :slight_smile: The Hackerrank Game Theory section is full of Nim-style games, so I was primed to spot it quite quickly :slight_smile:

This question is really a “you have to know it (or at least Google it)” - the Sprague-Grundy Theorem is not something people are likely to come up with in a 2 hour contest, and the results of the theorem are not at all intuitive.

1 Like

@anon62928982 Yeah, this is the correct explaination.
I am the setter for the question, the editorial is Coming Soon !

2 Likes

How to solve the question Sartaj Drinks Gotchi?

Thanks for the links :slightly_smiling_face:

1 Like

Because I checked, Gaurav Sen has nice videos on Game Theory and Grundy Numbers. You may want to check that.

1 Like

Thanks to you too :slightly_smiling_face: