Problem link: contest practice
Difficulty: Easy
Pre-requisites: Nim game
Problem: Determine the number of winning positions for the first player in a two player game, described by the statement.
Explanation:
At first, let’s solve the simplified version of the problem: given N, M, X, Y and we have to determine whether the first player wins or not. We will consider that X is between 1 and N and Y is between 1 and M for convenience.
Consider some vertical cut that is located to the left of the marked cell. If we make this cut, the number of columns that we can cut to the left of the marked cell will change. But this will not change the number of columns to the right of the marked cell, and the number of rows to the bottom and to the top of this cell that we’ll be able to cut. The same applies for three other types of cuts. That means that actually, all four types of our possible cuts are independent from each other. Let’s denote the number of cells to the left of the marked cell by L, to the right by R, to the top by U and to the bottom by D. The fact that all four types of cuts are independent gives rise to the following idea: it’s a nim game with four piles with sizes respectively L, R, U, D. So, if the XOR of these four numbers isn’t equal to zero, the first player wins.
Now, knowing how to check a single cell, the following solution is straightforward: check every cell. It’s time complexity is O(N*M) and it will bring us 61 point.
How to get the remaining 39 points? At first, we should notice that L+R is a constant and always equals to M-1. So, we obtain O(M) possible values for L XOR R. At second, U+D is also a constant, and it equals to N-1, and again, we obtain O(N) possible XOR values for U XOR D. And now the problem is: given two lists of numbers, find the number of pairs, where the first number is from the first list and the second number is from the second list and XOR of these numbers is nonzero. As we know, XOR equals to zero only if the first it’s argument equals to the second. So, we can get the answer as (N*M - number of pairs (i, j) such that the i-th number in the first list equals to the j-th number in the second). And to calculate the number of such pairs fast, you can handle some array, let’s call it F[], where F[X] equals to the amount of numbers that equal to X in the first list. Then, the number of “equal pairs” is simply the sum of F[B[i]] for all possible natural values from 1 to M, where B[i] corresponds to the i-th number in the second list. This gives us 100 point solution.
Setter’s solution: link
Tester’s solution: link
