Let \(x_i\) be the number of coins on Dish \(i\) after \(N\) operations. We will omit the details and just state that it only matters whether \(\oplus x_i\) is \(0\) or not, where \(\oplus\) is the bitwise XOR.

The players’ objectives depend on the parity of \(N\).

• If \(N\) is odd: the first player plays so that \(\oplus x_i\) becomes \(0\), and the second player plays so that \(\oplus x_i\) does not become \(0\).
• If \(N\) is even: the first player plays so that \(\oplus x_i\) does not become \(0\), and the second player plays so that \(\oplus x_i\) becomes \(0\).

Let us first explain the case in which \(N\) is even. If there is an even number of bags with \(n\) coins for every integer \(n\), the second player always wins. This is because the second player can always play symmetrically to the first player so that \(\oplus x_i\) is always \(0\) after the second player’s move. On the other hand, the first player always wins in all other cases. This is because the first player can always choose the dish with the most coins and the bag with the most coins, which puts more than half of the coins on one dish, which guarantees \(\oplus x_i\) will not be \(0\).

Then, let us explain the case in which \(N\) is odd. We can see that this case is almost the same as the case above: the second player can always choose the dish with the most coins and the bag with the most coins to put more than half of the coins on one dish. Thus, the second player always wins if \(N\) is odd.

We can check if the conditions above hold in \(O(N \log N)\) time, which is fast enough.