Editorial for ICPC NAQ 2016 I - Primonimo - DMOJ: Modern Online Judge

Editorial for ICPC NAQ 2016 I - Primonimo

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Subtracting $1$ $1$ from each square allows us to think of the problem in terms of modulo- $p$ $p$ arithmetic.
Since addition is commutative in modulo- $p$ $p$ arithmetic, we can see that the order in which we select squares doesn't matter.
Let $x_{i,j}$ $x_{i, j}$ denote the number of times square $(i, j)$ $(i, j)$ is selected, and let $v_{i,j}$ $v_{i, j}$ denote the initial value of square $(i, j)$ $(i, j)$ . Then we want: $\displaystyle v_{i,j} + \left(\sum_{k=1}^n x_{k,j} + \sum_{k=1}^m x_{i,k} - x_{i,j}\right) \equiv p-1 \pmod p$ $v_{i, j} + (\sum_{k = 1}^{n} x_{k, j} + \sum_{k = 1}^{m} x_{i, k} - x_{i, j}) \equiv p - 1 (\mod p)$
Assume for a moment that $x_{i,j} \in \mathbb R$ $x_{i, j} \in R$ and that we wanted (for some $K \in \mathbb R$ $K \in R$ ): $\displaystyle v_{i,j} + \left(\sum_{k=1}^n x_{k,j} + \sum_{k=1}^m x_{i,k} - x_{i,j}\right) = K$ $v_{i, j} + (\sum_{k = 1}^{n} x_{k, j} + \sum_{k = 1}^{m} x_{i, k} - x_{i, j}) = K$
Then we have a system of $n \times m$ $n \times m$ linear equations in $n \times m$ $n \times m$ variables, which we could solve using Gaussian elimination.
It turns out that Gaussian elimination works over any field (which includes modulo- $p$ $p$ arithmetic), so we can use the same method to solve our problem! Just perform all operations of the Gaussian elimination modulo $p$ $p$ .
Performing a division $a/b$ $a / b$ modulo $p$ $p$ is the same as multiplying $a$ $a$ by the modular multiplicative inverse of $b$ $b$ modulo $p$ $p$ , which can be computed with the Euclidean algorithm.
All $x_{i,j}$ $x_{i, j}$ can be taken modulo $p$ $p$ , which means that, if there is a solution, it will not use more moves than allowed by the problem statement.
Some care has to be taken when there are multiple solutions, or no solutions, as described by the Rouché-Capelli theorem. For the case of multiple solutions, it suffices to set all free variables to zero.
Time complexity is $\mathcal O(n^3 m^3)$ $O (n^{3} m^{3})$ .

Comments

There are no comments at the moment.