PROBLEM LINK:
Setter- Bogdan Ciobanu
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey
DIFFICULTY:
HARD
PRE-REQUISITES:
XOR Convolution (FWT), Schwartz-Zippel Lemma, Finding determinant of matrix using Gaussian Elimination, Edmond’s Matrix
PROBLEM:
Given a 2-D matrix, you are allowed to chose one element from each row, column (N in total). Find what numbers are possible by xoring all the selected elements.
QUICK-EXPLANATION:
Key to AC- Deduce that we are to find perfect matching in the bipartite graph where nodes are rows and columns. After that, its all on finding out the lemma and its use
Let there be one variable per bit in binary representation of number. We will need 2^k variables such that 2^k>Max(A_{ij}). Define a matrix M such that-
M_{i, j} = x_{i, j} * z_{i_1} * z_{i_2} * ... * z_{i_p}\ (if\ \{i, j\}\ consists\ of\ colors\ i_1, i_2, ..., i_p).
We ideally need to find permanent of the matrix and check for terms/powers with non-zero coefficients, but its a NP hard problem with exponential complexity. Notice that with Schwartz-Zippel lemma, we can say that “Using randomized algorithm, the chances that we get “Not possible” (i.e. 0 polynomial/coefficient ) for a possible value (i.e. non-zero polynomial/coefficient) are very less.” Hence, compute determinant using Gaussian elimination under XOR convolution and evaluate it at \{-1,1\}^k. If its non-zero, the particular value defined by variables/bits z_1,z_2,...,z_k is possible, else we can say with good confidence that it is not.
EXPLANATION:
A good gist of what we are going to discuss can be found here, the concept is essentially same as setter’s solution. Please have a read of the pre-requisites, notes given at end of editorial and perhaps the further reading section if you want, in case the explanation doesnt make much sense at first.
So, the problem asks us to pick 1 number from each Row and Column (picking one number counts against both, that row and that column), so we have to pick N numbers covering all N rows and N columns. Make a bipartite graph, where one set of nodes consist of all the rows, and other set of nodes consist of all the columns. Clearly, picking a number to cover all rows and columns (or vertices in bipartite graph), is perfect matching by definition.
However, we need to compute all possible values which are possible over all perfect matchings. This brings terms like Edmond’s matrix, Permanent of Matrix and finally Schwartz Zippel lemma into the picture.
Define a matrix M whose entries can be represented by M_{ij}=x_{ij}*z_{i_1} * z_{i_2} * ... * z_{i_p} where x_{ij} is a random integer and variable z_{i_k} is present if k'th bit is set in corresponding value in input matrix.
Now, the answer would have been non-zero terms of the permanent of this matrix, but finding permanent is of exponential complexity. Thankfully, there is a neat randomized algorithm that comes to our rescue here (you can refer to further reading sections to know more on its fundamentals, working etc.)
The algorithm is used for testing if a polynomial is a zero polynomial or not, and guarantees with a high probability that if you get a 0 on the random set of values you take, then that polynomial itself is 0 instead of your value being one of the root. (Refer to statement of Schwartz-Zippel lemma in pre-requisites).
Hence, for every value whose possibility we are checking in matrix, first generate a mask (the binary representation of the value we are checking), and then compute determinant under XOR convolution. If there is at least one odd power with non-zero coefficient, then we can say that this value is possible. Now, in case of single variable, for any function f(x), we can relate that -
2*OddPart=f(x)-f(-x).
A generalized version of this can be extended to k variables, which involves inclusion-exclusion principle.
2*OddPart=f(1,1,1,1,1....)-f(-1,1,1,...)-f(1,-1,1,1...)
Basically, the series goes like, all variables positive, all combinations where 1 variable is negative, all combinations where 2 variables are negative, all combinations where 3 variables are negative…all combinations where N variables are negative. This can be achieved using bit-masking.
Setter’s implementation and some more explanation is given in tab below-
Click to view
for (int i = 0; i < kMaxValue; ++i) {//Value which we are checking
Matrix y(x);
for (int bit = kMaxValue; bit > 0; bit >>= 1) {//To calculate odd sum.
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
if ((i & bit) and (m[r][c] & bit)) {
y[r][c] = kMod - y[r][c];//Under mod, -y=mod-y. This step multiplies by -1.
}
}
}
}
When mask = 1100110, we actually compute f(-1, -1, 1, 1, -1, -1, 1), this is the value associated with v[1100110_2]. so what happens in that first code is that we iterate fix the mask in the variable i and then we iterate all bits, and every match with a bit in the mask multiplies the cell in the matrix by -1, because remember that “f(z_1, z_2, ..., z_M) = det(M(z_1, z_2, ..., z_M)) where M_{i, j} = x_{i, j} * z_{i_1} * z_{i_2} * ... * z_{i_p} (if (i, j) consists of colors i_1, i_2, ..., i_p).” There i use colors to refer by bits, i_1, i_2, .., i_p are the current active bits in the mask.
When finding the determinant under XOR convolution, one actually obtains something else. That something else is “Walsh Spectrum” of the result we were intending to get. So, we need to derive the original result from it, which is achieved via inverse-FWT.
Click to view
for (int bit = 1; bit < kMaxValue; bit <<= 1) {
for (int i = 0; i < kMaxValue; ++i) {
if (!(i & bit)) {
int x = v[i], y = v[i | bit];
v[i] = (x + y) % kMod;
v[i | bit] = (x - y + kMod) % kMod;
}
}
}
Anyway, now v is not actually want we want, v[mask] might be different than 0 and we could still not obtain mask. This is because it contains parts of information from other masks. v is actually the Walsh spectrum of the result array we wanted to get. And to go from Walsh spectrum to the initial array we want, we apply the inverse fast walsh hadamard transform, which is exactly the code above.
And this was basically all. The question was very intensive in concept and maths, but was lenient in terms of coding. The setter’s code is short with descriptive naming (shoutout to Bogdan for the clear solution!) to which you can refer to for implementation doubts. The idea of the editorial will make more sense once you have a look at further reading section 
(I kind of had to skip all the overly complex stuff to focus on idea. Hope this works out for you guys, else shoot a comment and I will see what more I can add )
SOLUTION
Click to view
#include <bits/stdc++.h>
using namespace std;
const int kMaxValue = 1 << 10, kSeed = 7, kMod = 999119999;
using Matrix = vector<vector<int>>;
int RandInt() {
static mt19937 rng(kSeed);
static uniform_int_distribution<> distr(1, kMod - 1);
return distr(rng);
}
inline int Multiply(const int a, const int b) {
return static_cast<long long>(a) * b % kMod;
}
int Pow(int num, int p) {
int ans = 1;
while (p) {
if (p % 2) {
ans = Multiply(ans, num);
}
num = Multiply(num, num);
p /= 2;
}
return ans;
}
int Inverse(const int num) {
return Pow(num, kMod - 2);
}
int Determinant(Matrix m) {
const int n = static_cast<int>(m.size());
int res = 1;
for (int c = 0; c < n; ++c) {
int r = c;
while (r < n and m[r][c] == 0) {
++r;
}
if (r == n) {
return 0;
}
swap(m[r], m[c]);
if (r != c) {
res = kMod - res;
}
res = Multiply(res, m[c][c]);
for (int cc = c + 1, inv = Inverse(m[c][c]); cc < n; ++cc) {
m[c][cc] = Multiply(m[c][cc], inv);
}
for (++r; r < n; ++r) {
if (m[r][c] != 0) {
for (int cc = c + 1; cc < n; ++cc) {
m[r][cc] -= Multiply(m[c][cc], m[r][c]);
if (m[r][cc] < 0) {
m[r][cc] += kMod;
}
}
}
}
}
return res;
}
void Solve(const Matrix& m) {
const int n = static_cast<int>(m.size());
Matrix x(n, vector<int>(n));
for (auto& row : x) {
generate(row.begin(), row.end(), RandInt);
}
array<int, kMaxValue> v;
for (int i = 0; i < kMaxValue; ++i) {
Matrix y(x);
for (int bit = kMaxValue; bit > 0; bit >>= 1) {
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
if ((i & bit) and (m[r][c] & bit)) {
y[r][c] = kMod - y[r][c];
}
}
}
}
v[i] = Determinant(y);
}
for (int bit = 1; bit < kMaxValue; bit <<= 1) {
for (int i = 0; i < kMaxValue; ++i) {
if (!(i & bit)) {
int x = v[i], y = v[i | bit];
v[i] = (x + y) % kMod;
v[i | bit] = (x - y + kMod) % kMod;
}
}
}
bool first = true;
for (int i = 0; i < kMaxValue; ++i) {
if (v[i]) {
if (not first) {
cout.put(' ');
}
cout << i;
first = false;
}
}
cout << '\n';
}
int main() {
int num_tests; cin >> num_tests;
while (num_tests--> 0) {
int n; cin >> n;
Matrix mat(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> mat[i][j];
}
}
Solve(mat);
}
return 0;
}
Tester
Editorialist
Time Complexity=O(2^s *N^3)
Space Complexity=O(N^3)
CHEF VIJJU’S CORNER 
1. Hall of fame for noteworthy solutions-
2. Setter’s Notes-
Click to view
Note- They correspond to an older version of problem when it asked to find largest such number possible, instead of all numbers possible.
The permutation we’re looking for is in fact a perfect maching in the complete bipartite graphs represented by rows x columns.
Suppose some of these edges are black, while the others are white.
To check if we have a perfect matching with odd number of black edges we want the sum of even coefficients of f(z) = det(M(z)) where M_{i, j} = x_{i, j} * z (if \{i, j\} is black) or M_{ij}= x_{i, j} (if \{i, j\} is white) to be non-zero.
To go about finding the sum of odd coefficients, we’ll compute f(1) - f(-1).
Let’s generalize a bit. Let’s say we want to see whether there is a matching with odd number of edges of colors K_1, K_2, ..., K_M. We’ll consider a polynomial in F^M[z_1, z_2, ..., z_M].
f(z_1, z_2, ..., z_M) = det(M(z_1, z_2, ..., z_M)) where M_{i, j} = x_{i, j} * z_{i_1} * z_{i_2} * ... * z_{i_p} (if \{i, j\} consists of colors i_1, i_2, ..., i_p). We’re interested to see if there is at least one coefficient of this multinomial in which all exponents of z_i are odd.
This can be done using a generalized approach of the former solution, computing-
f({1, 1, ..., 1})
- f({-1, 1, 1, ..., 1}) - f({1, -1, 1, ..., 1}) - f({1, 1, -1, ..., 1}) - ... - f({1, 1, ..., 1, -1})
+ f({-1, -1, 1, ..., 1}) + f({-1, 1, -1, ..., 1}) + ... +
+ ... + (-1)^M f({-1, -1, -1, ..., -1}).
We will start from the most significant bit and determine whether we can add a new bit to our configuration using the above mentioned algorithm. The time complexity is T(N) = T(N/2) + O(N * W) = O(N * W), where N is the maximum value and W is the time to compute the determinant.
3. Alternate Notes-
Click to view
We basically want to check those powers of x whose coefficients are non zero under when we find determinant under XOR convulution. This is given by f(1,1,1,1,..) -f(-1,1,1...)-f(1,-1,1,1,..)... . Normally we’d had gone for permanent of the matrix, but since its exponential complexity,we use Schwartz-Zippel lemma which tells by which we guarantee on not missing any term by a high probability (since the probability that a coefficient is 0 when it wasnt supposed to be is <=d/|S|)
We can compute the determinant under FWT (Fast-Walsh Transformation, its the XOR convolution). Once done, we need to compute the inverse and finally check if its 0 or not. If v[i]=0, the number cannot be made, else it can be made
4. Further Reading-