Editorial for DMOPC '17 Contest 3 P5 - Picnic Planning


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: r3mark

Let (i, j) denote the j^\text{th} square in the i^\text{th} row of the park.

Let dp1[i][j] be the sum of l^l for all rectangles where (i, j) is the bottom right corner of the rectangle. Let dp2[i][j] be the sum of w \cdot l^l for the same rectangles. Let h[i][j] be the smallest number such that (i-h, j) is blocked or outside the grid. Let k be the largest number smaller than j such that h[i][k] \le h[i][j]. To find this k for each (i, j) in amortized \mathcal O(1), a stack may be used.

Consider a rectangle which has its bottom left corner before or at the k^\text{th} column and bottom right corner at (i, j). Then this is a unique rectangle with its bottom right corner at (i, k) with its right side stretched to the j^\text{th} column. The length of this rectangle remains unchanged but its width increases by a certain amount, specifically j-k. As such, the sum of l^l for rectangles with their bottom left corner before or at the k^\text{th} column is dp1[i][k] and the sum of w \cdot l^l is dp2[i][k]+(j-k) \cdot dp1[i][k].

Now consider the rectangles with their bottom left corner after the k^\text{th} column and bottom right corner at (i, j). Since k is the largest number smaller than j such that h[i][k] \le h[i][j], any rectangle with height from 1 to h[i][k] and width from 1 to j-k can have their bottom right corner at (i, j) and still fit. In fact, these are all the rectangles with their bottom left corner after the k^\text{th} column and bottom right corner at (i, j). The sum of l^l and w \cdot l^l in this case can be computed in \mathcal O(1) if the sum of 1^1+2^2+\dots+n^n for all 1 \le n \le \max(M, N) has been precomputed.

To compute the final values of dp1[i][j] and dp2[i][j], take the sum of the corresponding results found in each case. So using this dp relation, all dp1 and dp2 values for a single row can be computed in \mathcal O(N). All the dp values can be computed in \mathcal O(MN).

To find the sums of all lw(l^l+w^w), perform this algorithm and then rotate the grid and repeat the algorithm. The final answer is the sum of all the dp2 values.

Time Complexity: \mathcal O(MN)


Comments

There are no comments at the moment.