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