We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Calculating grundy value using mex definition instead of an explicit formula works nicely as described in the editorial. But we can also reuse previous challenge result.
x prime with 2
The grundy function g is the same as the one in previous challenge g'. All the divisors will be odd. By property of the nim sum, the grundy value for y towers of size z will be the same as for 1 tower of size z. So splitting tower x into y towers of size z is the same as replacing x by its divisor z.
g(x)=g'(x)
x not prime with 2
For y even, the nim sum cancels out and the next player loses. The grundy value is the same as well, but considering only primes other than 2 and offsetting by 1: Where alpha_2 is the exponent of prime factor 2,
g(x)=g'(x)-alpha_2+1
g' is the sum of the prime exponents in prime factorization. One could probably show this by induction on the number of prime factors and then on the prime exponent in the factorization. Same for above result.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tower Breakers, Again!
You are viewing a single comment's thread. Return to all comments →
Calculating grundy value using mex definition instead of an explicit formula works nicely as described in the editorial. But we can also reuse previous challenge result.
x prime with 2The grundy function g is the same as the one in previous challenge g'. All the divisors will be odd. By property of the nim sum, the grundy value for y towers of size z will be the same as for 1 tower of size z. So splitting tower x into y towers of size z is the same as replacing x by its divisor z.
For y even, the nim sum cancels out and the next player loses. The grundy value is the same as well, but considering only primes other than 2 and offsetting by 1: Where alpha_2 is the exponent of prime factor 2,
g' is the sum of the prime exponents in prime factorization. One could probably show this by induction on the number of prime factors and then on the prime exponent in the factorization. Same for above result.