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.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Subtracting
from each square allows us to think of the problem in terms of modulo-
arithmetic.
- Since addition is commutative in modulo-
arithmetic, we can see that the order in which we select squares doesn't matter.
- Let
denote the number of times square
is selected, and let
denote the initial value of square
. Then we want:
- Assume for a moment that
and that we wanted (for some
):
- Then we have a system of
linear equations in
variables, which we could solve using Gaussian elimination.
- It turns out that Gaussian elimination works over any field (which includes modulo-
arithmetic), so we can use the same method to solve our problem! Just perform all operations of the Gaussian elimination modulo
.
- Performing a division
modulo
is the same as multiplying
by the modular multiplicative inverse of
modulo
, which can be computed with the Euclidean algorithm.
- All
can be taken modulo
, 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
.
Comments