Since the editorial has no mention of Sprague Grundy Theorem, I thought I’d shed some light on how to arrive at the solution without much observations. I believe it was a great task for a Long Challenge, as you had a lot of time to learn and experiment, especially to dive into the world of Nim (and Game Theory in general). Hence, I was a bit surprised to see no mention of this fact in the editorial.
All you need to follow through is just one reference
Now, I’ll assume you’ve read through the reference, and hence, would keep the editorial brief.
- Observe that the given game is an Impartial Game. So, even if we solve it by just observations, there has to be a way to simplify it into a Nim Game as per Sprague Grundy Theorem.
- Assume Y = 1 for the moment. Using an O(n^2) algorithm, (by computing MEX in O(N)), we can calculate Grundy Numbers of each state i.
- The last example of the reference states that Grundy numbers are generally periodic. Could that be the case here? We get a gut feeling it should be, as the large number of test cases indicate a closed form formula to compute the answer.
- It’s a long challenge after all, we have to take a leap of faith and implement that O(n^2) algorithm to compute Grundy numbers for all states. If you print it, you get the sequence 0, 1, 2, 3, 4, 5, 0, 1, 2, 3. Hence, Grundy numbers always increase (mod 6).
- Similarly, we compute for Y = 2, we’ll observe that Grundy numbers always increase (mod 30).
- We compute for Y = 3, we get that Grundy numbers always increase (mod 210).
So, we’ve deduced that the Grundy numbers are periodic (not proved, mind you, but it’s all right, as it would lead us to the intended observation).
So, now, we have 3 numbers 6, 30, 210. How do we know the relations between them? If you’re smart enough, you can figure out that the period has to involve primes (as the task is entirely based on prime numbers). So, you factorize it, and you observe the pattern,
2 \cdot 3
2 \cdot 3 \cdot 5
2 \cdot 3 \cdot 5 \cdot 7
This means that if starting states is divisible by product of first Y + 1 primes, only then the Grundy value would be zero. So, you have the solution. (You just have to check whether X! contains the first (Y + 1) prime numbers or not).
Lastly, suppose you’re not smart enough to figure out the relation between 6, 30, 210. What’s the next big thing? Of course, OEIS or Google. And sure enough, A quick Google search would tell you that these numbers are called Primorials and they are indeed the product of first i primes.