Official

D - Choosing Up Sides Editorial by evima


We will describe the admin’s solution, which is easy to explain.

Let \(\mathrm{popcount(n)}\) denote the number of 1s in the binary notation of \(n\), and \(x \ \mathrm{AND} \ y\) denote the bitwise AND of \(x\) and \(y\).

Let \(M = 2^{N-1}\). In one operation, the total number of pairs of players belonging to different teams increases by \(M^2\). Thus, it is necessary that \((n+m)M^2 = m \binom{2M}{2}\) holds, which can be transformed into \(n:m = M-1:M\).

From this, we can see that the number of operations must be a multiple of \(2^{N}-1\) to achieve the objective. In the end, we can achieve it in \(2^{N}-1\) operations, the minimum number of operations possible, as follows:

  • in the \(i\)-th operation, put Person \(j\) in Team A if \(\mathrm{popcount(i \ \mathrm{AND} \ j)}\) is odd, and in Team B if it is even.

We can do it in \(O(4^N)\) time, which is fast enough for \(N \leq 8\).

posted:
last update: