Editorial for DMOPC '22 Contest 4 P5 - Blackboard Game

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: mangoqwq

Subtask 1

Consider the sum of \log_2(A_i) - 1 where A_i are the numbers currently written on the board. This sum decreases by exactly 1 on each move. Thus, we can find the winner by considering the parity of this sum.

Subtask 2

The described game is an impartial game, and the remainder of the editorial will assume knowledge of the Sprague-Grundy theorem.

Observe that we only need to care about the prime factorizations of the numbers on the board. More specifically, for X = p_1^{e_1} \cdots p_k^{e_k}, we only care about the multiset \left\{ e_1, \ldots, e_k \right\}.

It turns out there are around 7000 such multisets for blackboard numbers between 2 and 10^{12}. To reduce the number of states, observe that multisets S and S + \left\{ 1 \right\} (adding one 1 to S) will always have the same Grundy number. This can be proved inductively, but the intuition is that if prime factor p of X has multiplicity 1, we cannot do anything with p when splitting X into Y and Z.

With this observation, the number of states is cut down to around 1500. Then we can compute Grundy values in \mathcal{O}(M^2 \log A), where M \approx 1500 is the number of such states. Since we do not care for prime factors of multiplicity 1, we can calculate the multisets corresponding to each A_i in A^{1/3} time. Hence we have solved this problem in \mathcal{O}(NA^{1/3} + M^2 \log A).

Note from the problem author: Thanks to mangoqwq for preparing the problem :)


There are no comments at the moment.