PROBLEM LINK:
Author: Pavel Sheftelevich
Tester: Kevin Atienza
Editorialists: Suhash Venkatesh and Pushkar Mishra
DIFFICULTY:
Hard
PREREQUISITES:
Hadamard matrices, Sylvester’s construction, Paley construction, Williamson construction
PROBLEM:
Given a vector a of length N^2 (consisting of only +1 and -1), we apply a TVT transformation on it to get a new vector b also of length N^2. The TVT transformation is applied as follows:
We say that the vector b is good if b[i] = N^2 ( if i \bmod N = \left\lfloor\frac{i}{N}\right\rfloor), 0 otherwise. Given N, find if there exists a vector of size N^2 (consisting of only +1 and -1) which becomes good after applying the TVT transformation.
EXPLANATION:
Before we proceed with the individual subtasks, let’s first try to simplify the given equation. Notice that we iterate over k from 0 to N^2-1, and we have an inner (k \bmod n) which can only take values from 0 to N-1. Therefore we can reduce the equation as:
Also, notice that when i \bmod N = \left\lfloor\frac{i}{N}\right\rfloor, the equation becomes:
Hence, we only need to worry about the case where i \bmod N \neq \left\lfloor\frac{i}{N}\right\rfloor and solve for the elements of a by equating b[i] = 0. Now, let us define N vectors A_{0}, A_{1}, …, A_{N-1} each of length N, such that A_{m} = (a[m*N], a[m*N + 1], …, a[m*N + (N-1)]), 0 <= m <= N-1. It is easy to see that on simplifying the above equations of the form b[i] = 0, we get N\times (N-1)/2 distinct equations of the form \vec{A_{i}}\cdot \vec{A_{j}} = 0 (dot product, i != j). Getting to this step is simple and is left as an exercise to the reader.
Now, the problem reduces to finding N vectors (each of length N) which are mutually orthogonal and whose entries can only be +1 or -1. After a bit of googling, it is easy to find that this problem is exactly the same as generating a Hadamard matrix of order N. Further, you can also infer that a Hadamard matrix of order N exists only if N = 1, 2 (or) 4*k (k > 0). This can be found here on OEIS.
Subtask 1
For this subtask, N <= 8. Hence, we need to generate Hadamard matrices of order 1, 2, 4 and 8 for this subtask. For N = 1 and N = 2, the answer is trivial (sample cases). For N = 4, we can solve it by brute force. There are a total of N^2 = 16 variables, each of which can be +1 or -1. Hence, we can try all 2^{16} combinations and check which of them is valid. Given a set of N^2 values, we can check if it forms a good vector in \mathcal{O}(N^3). Also, for N = 4 it is very easy to generate a solution by hand using pen & paper. Now, to pass this subtask we only need to find the answer for N = 8.
Sylvester’s construction:
If we have a Hadamard matrix of order N, then this method can generate a Hadamard matrix of order 2^{k}*N (k > 0). There is also a Hadamard conjecture that given two Hadamard matrices of orders X and Y, a Hadamard matrix of order X*Y can be constructed by considering the Kronecker product of the two matrices. Let M_{N} denote a Hadamard matrix of order N. For passing this case, consider M_{8} = M_{2} \otimes M_{4}. According to Sylvester’s construction, given M_{N}, we can generate M_{2N} in the following way:
Thus, we can construct M_{8} from M_{4}. Note that M_{4} could have also been constructed from M_{2} using this method. You can read about this method here. This will pass the first subtask.
Subtask 2
For this subtask, N <= 30. Hence, in addition to the first subtask we also need to generate Hadamard matrices of orders 12, 16, 20, 24 and 28. We only need to calculate M_{12}, M_{20} and M_{28}. We can calculate M_{16} and M_{24} using the method explained in subtask 1. M_{16} = M_{2} \otimes M_{8} and M_{24} = M_{2} \otimes M_{12}.
Paley construction
Paley construction is a method of constructing Hadamard matrices using finite fields. The Paley construction method uses quadratic residues in a finite field Z(p), where p is the power of an odd prime number. There are 2 cases. If p \equiv 1 \mod 4, then a Hadamard matrix of order 2*(p+1) can be constructed, and if p \equiv 3 \mod 4, then a Hadamard matrix of order (p+1) can be constructed. Let Q be the Jacobsthal matrix for a given odd prime power p.
Paley construction I:
If p \equiv 3 \mod 4, then
H=I+\begin{bmatrix}
0 & j^T\\
-j & Q\end{bmatrix}
is a Hadamard matrix of order (p+1). Here j is the all 1 column vector of length p and I is the (p+1)*(p+1) identity matrix.
Paley construction II:
If p \equiv 1 \mod 4, then the matrix obtained by replacing all 0 entries in
\begin{bmatrix}
0 & j^T\\
j & Q\end{bmatrix}
with the matrix
\begin{bmatrix}
1 & -1\\
-1 & -1\end{bmatrix}
and all entries ±1 with the matrix
\pm\begin{bmatrix}
1 & 1\\
1 & -1\end{bmatrix}
is a Hadamard matrix of order 2*(p+1)
You can read more about Paley construction here. We are yet to discuss how to find the Jacobsthal matrix Q. Let’s split the Jacobsthal construction also into 2 cases: (1) p is an odd prime, (2) p is the power of an odd prime. It is easy to see that we only need to solve case (1) to pass this subtask => 12 = (11+1) and 11 mod 4 = 3, 20 = (19+1) and 19 mod 4 = 3, 28 = 2*(13+1) and 13 mod 4 = 1. All of 11, 13 and 19 are odd primes.
For an odd prime p, the field under consideration is Z(p) and the elements of the field can be given by [0, 1, 2, …, p-1]. Now, to construct a Jacobsthal matrix we need to calculate the quadratic character χ(i), for all 0 <= i <= p-1. χ(0) = 0, χ(a) = 1 if a = b^2 for some non-zero finite field element b, and χ(a) = −1 if a is not the square of any finite field element. It is easy to see that χ(i) can be computed for all 1 <= i <= p-1 in \mathcal{O}(p^2).
Pseudo code:
for i = 0..(p-1): chi[i] = -1; chi[0] = 0; for i = 1..(p-1): chi[(i\*i) % p] = 1;
Now, the Jacobsthal matrix Q of order p can be constructed as : Q_{i,j} = χ((i-j+q)\bmod q). Note that, for an odd prime p, the Jacobsthal matrix is circulant (each row is obtained from the row above by cyclic permutation). Using this Jacobsthal matrix, we can construct the Hadamard matrix by Paley construction. This is sufficient to pass the second subtask.
Subtask 3
For this subtask, N <= 60. The only special case here is actually N = 52, where the Jacobsthal matrix construction needs to be performed under the field Z(p^2) instead of Z(p). 52 = 2*(5^2 + 1) and 25 mod 4 = 1. For all other values of N <= 60, the methods used in subtasks 1 and 2 will suffice to find the solution.
Now, let’s try to find the Jacobsthal matrix for a general case where p is the power of an odd prime. More specifically, p = q^m and q is an odd prime. We can see that Z(q^m) is an extension field of Z(q) obtained by adjoining a root of an irreducible quadratic. Different irreducible quadratics produce equivalent fields. We can write Z(q^m) as Z(q)[X] / (f(X)) for some irreducible polynomial f(X) in Z(q)[X] of degree m.
Let us assume that the irreducible quadratic is a_{m} * X^m + a_{m-1} * X^{m-1} + ... + a_{1} * X + a_{0}, and let t be any root of this polynomial => a_{m} * t^m + a_{m-1} * t^{m-1} + ... + a_{1}*t + a_{0} = 0. Using this, we can write the q^m elements of Z(q^m) as c_{m-1} * t^{m-1} + c_{m-2} * t^{m-2} + ... + c_{1} * t + c_{0}, where 0 <= c_{i} <= (q-1). Note that there may be several irreducible polynomials and we can choose any of them. All of them produce equivalent fields.
For example, let us consider the field Z(9). Let X^2 + X − 1 be an irreducible polynomial over the given field, and let t be any of it’s roots. We have (t^2 + t - 1 = 0) => (1). The 9 elements of Z(9) can be written as {(0*t+0), (0*t+1), (0*t+2), (1*t+0), (1*t+1), (1*t+2), (2*t+0), (2*t+1), (2*t+2)}. Now, lets take some element say (t+1) and try to square it. (t+1)^2 mod 3 = (t^2 +2*t + 1) = (-t + 1) + 2*t + 1 {from (1)} = (t + 2) mod 3. Therefore, χ(t+2) = 1 since it can be expressed as the square of some element from the field. Similarly, (t+2)^2 mod 3 = (t^2 +4*t + 4) = (-t + 1) + 4*t + 4 {from (1)} = (3*t + 5) = 2 mod 3. Therefore, χ(2) = 1.
We also infer here that on squaring any element of Z(q^m), (c_{m-1} * t^{m-1} + c_{m-2} * t^{m-2} + ... + c_{1} * t + c_{0})^2, we can reduce it to some other element of the field (d_{m-1} * t^{m-1} + d_{m-2} * t^{m-2} + ... + d_{1} * t + d_{0}) using the irreducible polynomial. We have shown this for m=2 (considering the field Z(3^2)). In fact, we’ll show later that for this problem we never have to go beyond m=2. For this subtask, N = 52 and p = 25 = 5^2. Here is a code snippet for m=2.
Pseudo Code:
List get_square_residues(q, a1, a0) {
/\*
(X^2 - a1\*X - a0) is the irreducible polynomial.
If 't' is a root, then t^2 = a1\*t + a0.
\*/
List chi(q\*q);
chi.fill(-1);
chi[0] = 0;
for (i = 0 to q-1) {
for (j = 0 to q-1) {
if (i + j == 0) continue;
/\*
We need to compute (i\*t + j)^2
= t^2 \* i\*i + t \* 2\*i\*j + j\*j
= (a1\*t + a0) \* i\*i + t \* 2\*i\*j + j\*j
= t \* (a1\*i\*i + 2\*i\*j) + (a0\*i\*i + j\*j)
\*/
r1 = (a1 \* i \* i + 2 \* i \* j) % q;
r2 = (a0 \* i \* i + j \* j) % q;
if (r1 < 0) r1 += q;
if (r2 < 0) r2 += q;
chi[q\*r1 + r2] = 1;
}
}
return chi;
}
Here, note that we are just indexing the element (t*r1 + r2) with (q*r1 + r2) so that we can represent all the q^2 elements in a single list easily. Again, this code is only for m=2 which is sufficient for solving this problem. Computing the quadratic residues for m>=3 is also fairly trivial as already explained and is left as an exercise to the reader.
There are several methods to compute the irreducible polynomial, but we only encounter Z(5^2) and Z(7^2) in this problem. We can simply use a pre computed Conway polynomial from here. The final step to solve this subtask is to compute the Jacobsthal matrix.
Pseudo code:
void fill(Q, base_i, base_j, q, m, chi) {
/\*
'Q' is the original Jacobsthal matrix that we want to fill.
'chi' array denotes the quadratic character and has length q^m.
(base_i, base_j) denotes the top left corner of the (q^m \* q^m) sub-matrix
that we want to fill in the current function call.
\*/
if (m == 0) {
// base case - We just need to fill a 1\*1 sub-matrix.
Q[base_i][base_j] = chi[0];
return;
}
for (i = 0 to q-1) {
for (j = 0 to q-1) {
block_no = (j - i + q) % q;
chi_new = chi.sublist(q \* block_no, q^(m-1));
// a.sublist(i, n) returns the sub-array {a[i], a[i+1], ..., a[i+n-1]}
fill(Q, i \* q^(m-1), j \* q^(m-1), q, m-1, chi_new);
}
}
}
We call
fill(Q, 0, 0, q, m, chi)
to fill Q. For a given p = q^m, we essentially treat it as q * q sub-matrices each of order q^{m-1}. We try to fill this in a circulant fashion, similar to the case where p is an odd prime. We do this recursively until all elements of the matrix Q are filled. We see that the time taken T(m) = q^2 * T(m-1). This gives us T(m) = (q^m)^2 = p^2. Therefore, the overall complexity is \mathcal{O}(N^2). This will pass the third subtask.
Subtask 4
This is the final subtask and N <= 100. Again, the only special case here is N=92. For all other values of N, we can use the methods used in the first 3 subtasks to generate the Hadamard matrices. For N=92, we can note that Paley construction cannot be used. We need to use some other technique.
Williamson construction
If there exist 4 matrices A, B, C and D, each of order n, such that they are all circulant, symmetric matrices (and hence commutative) and A^2 + B^2 + C^2 + D^2 = 4nI_{n}, then we can construct a Hadamard matrix of order 4*n in the following way.
More details about the construction can be found here. Since A, B, C and D are all circulant matrices, they can be represented by just the first row, and all subsequent rows can be obtained by a cyclic rotation of the previous row. There are ways to compute this, but by doing a bit of search you can find them online. 
Thus, we see that all the cases can be solved using the above methods and the complexity of all methods is \mathcal{O}(N^2).
P.S. This is a very interesting problem and can be solved in other ways too. If you have used any other method, feel free to mention it in the comments.
COMPLEXITY:
\mathcal{O}(N^2) per test case.
