I didn't even consider solutions that involved passing messages containing 100,000+ integers because I somehow intuitively assumed that sending huge messages would incur a delay on the network. Turns out that transfer delays in DCJ are independent of message size.

You have to check if f(k) = 0 as mentioned. However, f(k) may be very large and thus cannot be stored. I used a slightly different approach to calculating f(k).

ll done = a[n];
for(i = n - 1; i >= 0; i--) {
  if(abs(done) > 10000000000LL) {
    break;
  }
  done = a[i] + (k * done);
}

Finally, check if done is zero. The comparison with 10000000000LL works because of the following. When i = 0, abs(done) must be less than 10^4, since the problem specifies that abs(a[0]) < 10^4 and their sum must be zero. Now, when i = 1, abs(done) must be < 2 * 10^4, since abs(a[1]) < 10^4. Continuing so on, abs(a[n]) < 10^5 * 10^4 if n = 10^5.

Nice solution! Here's an alternate proof for this being the minimum number of flips.

Let H(i, j) denote the number of black tiles in the row i and column j. If H(i, j) is odd, we plan to flip the tile (i, j) as described in the algorithm above. Now, note that the parity of H(i, j) can only be changed by flipping (i, j). Flipping any other tile on the board maintains the same parity of H(i, j). We know that in the final configuration (all tiles white), H(i, j) = 0 (an even number) for all (i, j). Thus, in order to reach the final configuration, we must flip at least all the tiles for whom H(i, j) is odd. Thus, no set of flipped tiles can be smaller than the set generated by the algorithm described above by Vercingetorix.

Why has registration been closed? Please open registration — the competition hasn't even started yet.