E - Cross Sum Construction Editorial by evima
Since \(M_{i,j}\) contributes \(2N-1\) times to the sum of the elements of \(S\), a necessary condition for the maximum score to be \(N^2\) is that the sum of \(X\) is a multiple of \(2N-1\). This condition is also sufficient. First, we show how to construct a solution in this case.
We consider how to make the sum for the \(i\)-th row and \(j\)-th column equal \(s_{i,j}\) for each \(i,j\). Let \(\mathrm{sum}\), \(r_i\), \(c_j\) be the sum of \(s_{i,j}\), the sum of \(s_{i,j}\) for the \(i\)-th row, the sum of \(s_{i,j}\) for the \(j\)-th column, respectively. Then, let \(M_{i,j} = -2 \mathrm{sum} + (2N-1)(r_i+c_j) - (2 N-1)(N-1)s_{i,j}\), and the sum for the \(i\)-th row and \(j\)-th column is \((2N-1)(N-1)s_{i,j}\). Thus, if the value of this formula is a multiple of \(2N-1\) and also a multiple of \(N-1\) (since \(2N-1\) and \(N-1\) are coprime, these conditions can be treated independently), the objective can be achieved by dividing it by \((2N-1)(N-1)\).
Since we are now considering the case where the sum of the elements of \(X\) is a multiple of \(2N-1\), the condition of being a multiple of \(2N-1\) is already satisfied.
The issue is the condition of being a multiple of \(N-1\), which is generally not satisfied, so we have to correspond the elements of \(X\) to \(s_{i,j}\) appropriately. If \(r_1,\ldots,r_N\) and \(c_1,\ldots,c_N\) are congruent modulo \(N-1\), the above formula will be a multiple of \(N-1\), so we will set \(s_{i,j}\) as such.
Hereafter, the subscripts start at \(0\), and if they are outside \([0,N)\), they stand for the counterparts that are congruent modulo \(N\).
If \(N\) is odd, let \(S_{i,j} = a_{-i+j} + b_{-2i+j}\), then the sum of any row and column is \(\sum a_i + \sum b_i\), and the condition is satisfied.
If \(N\) is even, let \(S_{i,j} = a_k + b_l\) similarly. First, rearrange \(a\) so that \(a_0\) and \(a_{\frac{N}{2}}\) are congruent modulo \(N-1\). Then, define \(k\) as follows.
\[ k = \begin{cases} -i+j & (-i+j \neq 0 \text{ and } -i+j \neq \frac{N}{2}) \\ \frac{N \times( i \bmod 2)}{2} & (-i+j = 0 \text{ or } -i+j = \frac{N}{2}) \end{cases} \]
To \(l=1,2,\ldots,N\), correspond the following pairs \((i,j)\).
- \((2 \lfloor \frac{l}{2}\rfloor + \frac{N \times( l \bmod 2)}{2} + x, 2 \lfloor \frac{l}{2}\rfloor+2x)\) for \(x=0,1,\ldots,\frac{N}{2}-1\)
- \((2 \lfloor \frac{l}{2}\rfloor + \frac{N \times( l \bmod 2)}{2} + x, 2 \lfloor \frac{l}{2}\rfloor+2x+1)\) for \(x=\frac{N}{2}, \frac{N}{2}+1,\ldots,N-1\)
Now, the condition is satisfied.
Proof
For each \(l\), it is clear that \(0,1,\ldots,N-1\) all appear once as \(i\). For \(j\), the period of \(0,2,4,\ldots\) is \(\frac{N}{2}\) when \(N\) is even, so \(0 \leq x \lt \frac{N}{2}\) cover odd \(j\) and \(\frac{N}{2} \leq x \lt N\) cover even \(j\). Thus, \(0,1,\ldots,N-1\) all appear once also as \(j\). Therefore, \(b_l\) contributes to each of \(r_1,\ldots,r_N,c_1,\ldots,c_N\) exactly once, eventually making them equal.
Furthermore, the values \(-i+j\) for \(x=0\) and \(x=N-1\) are \(0\) or \(\frac{N}{2}\) and equal. Let \(y\) be this value. Then, \(-i+j=y+x\) for \(0 \leq x \lt \frac{N}{2}\) and \(-i+j=x+y-(N-1)\) for \(\frac{N}{2} \leq x \lt N\), and \(-i+j\) will be congruent to each value from \(\frac{N}{2}+1\) through \(\frac{N}{2}-1\) once modulo \(N\). Additionally, when \(-i+j=0\) or \(-i+j=\frac{N}{2}\), \(k\) is defined to change according to the parity of \(i\), so \(0,1,2,\ldots,N-1\) all appear as \(k\). Therefore, for each \(l\), there is a correspondence from \(k\) to \(x\).
We also have a correspondence from each \((i,j)\) to \(l\). Repeating \((-2,-2)\) and \((-1,-2)\) from exactly one of \((i,j)\) and \((i,j+1)\) leads to \((i,j)\) corresponding to \(x=0\) for the two forms of \(l\). Since \((-1,-2)\) has period \(\frac{N}{2}\), it corresponds to exactly one of \(0\leq x \lt \frac{N}{2}\) and \(\frac{N}{2} \leq x \lt N\), which is the correspondence from \((i,j)\) to \(l\).
Since each \(l\) contains \((i,j)\) with \(k=0,1,\ldots,N-1\) and there is a correspondence from \((i,j)\) to \(l\), it follows that all \(a_k + b_l\) appear in the above construction.
The above construction achieves the maximum score of \(N^2\) when the sum of \(X\) is a multiple of \(2N-1\).
If the sum of \(X\) is not a multiple of \(2N-1\), after adjusting \(s_{i,j}\) to make them match modulo \(N-1\) by the above method, we can repeatedly add \(N-1\) to some \(S_{i,j}\) so that the sum will be a multiple of \(2N-1\) (since \(N-1\) and \(2N-1\) are coprime), achieving the maximum score of \(N^2-1\).
posted:
last update: