Editorial for WC '15 Contest 4 S3 - Coded Paper
Submitting an official solution before solving the problem yourself is a bannable offence.
We are given a by
matrix of numbers and want to maximize their sum by replacing any number of rectangular regions on the matrix with other rectangles, each of which has just the number
written on it. For the first subtask where
, we can manually generate every possible configuration of rectangle placements. For the second subtask where
, we can do some kind of brute force to find the answer (possibly using backtracking to repeatedly place rectangles of all possible sizes in all possible configurations).
For an answer that gets full marks, let's first consider the simple case in which is non-negative. In this case, there's no benefit to using larger cardboard rectangles – they might as well all be
by
squares to maximize the number of numbers we can replace. In particular, we should just greedily cover every cell with value
less than
.
When is instead negative, dynamic programming is required. Let
be the maximum possible sum of values in the first
columns, where
is an integer between
and
describing the state of any ongoing cardboard rectangles. In particular, the following possibilities exist at any column
:
– No ongoing rectangles
– Ongoing height-
rectangle in row
– Ongoing height-
rectangle in row
– Ongoing height-
rectangles in both rows
– Ongoing height-
rectangle spanning both rows
is computed by considering each possible previous rectangle state
(between
and
), and maximizing the value of:
sum of visible cells in column
given the rectangles described by
number of new rectangles being started going from state
to
.
This requires some case analysis of the possible rectangle states and the transitions between pairs of them.
The final answer is stored at case of the last column, where there are no ongoing rectangles. The time complexity of this algorithm is
.
Comments