Editorial for Mock CCC '18 Contest 2 J5/S3 - A Coloring Problem
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.
Author:
Let us start by temporarily ignoring the constraint that a square being blue forces squares to its left to be blue.
Each column now has a certain range of blue squares that are permitted to be present.
If we add back in that constraint, we note that the number of blue squares must be nonincreasing as we go from left to right.
We can therefore maintain a DP where our state is (column, number of blue squares in this column) and we can only transition to states where the number of blue squares does not increase.
Naively implemented, this is but can be optimized to
with prefix sum arrays.
The bounds were set such that 64-bit integers were required.
Comments