Editorial for DMOPC '15 Contest 1 P5 - Lelei and Dragon Scales


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.

Author: cheesecake

Using a 2-D prefix sum array, we can calculate the total number of scales in any rectangle in \mathcal{O}(1). For a rectangle with its top left corner at (a,b) and its bottom right corner at (c,d), we can use inclusion-exclusion to see that the total number of scales = prefix[c][d] - prefix[a][d] - prefix[c][b] + prefix[a][b].

Brute forcing all possible rectangles gives us an \mathcal{O}(W^2 \times H^2) solution, which will give us 50\% of the points. To get 100\%, we need to make the insight that since all cells have a non-negative number of scales, we only need to consider the number of scales in the rectangle with maximum length with each possible width.

Time Complexity: \mathcal{O}(W \times H \times \min(W, H))


Comments

There are no comments at the moment.