PROBLEM LINK:
Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi
PREREQUISITES:
DP
EXPLANATION:
Let’s start with defining a few arrays and dp arrays:
1_ d_0[r][cnt] is equal to the minimum time required to eat cnt cheese wedges from the first (r-1) rows and getting to the first column of the r^{th} row.
2_ d_1[r][cnt]: similar to d_0 except you need to get to the last column of the r^{th} row.
3_ ans[r][cnt] is equal to the minimum time required to eat cnt cheese wedges from the first r rows.
4_ c_0[1][r][cnt] is equal to the minimum time required to start from the first column of the r^{th} row and go to the right and eat cnt of the cheese wedges on the r^{th} row.
5_ c_0[2][r][cnt] is equal to the minimum time required to start from the first column of the r^{th} row and go to the right and eat cnt of the cheese wedges on the r^{th} row and get back to the first column.
6_ c_1[1][r][cnt] is the same as c_0[1][r][cnt] except that it’s for the last column.
7_ c_1[2][r][cnt] is the same as c_0[2][r][cnt] except that it’s for the last column.
8_ z[r][cnt] is equal to the minimum sum of cnt cheese wedges from row r.
9_ g[r] is equal to the number of cheese wedges on row r.
Alright, now we’re done with definitions. The answer to the problem would be stored in ans. So all that’s left is to calculate these arrays. Here we go through them one by one and explain how you can calculate them:
1_ d_0[r][cnt] = \min(\min_{0 \leq i \leq g[r-1]} (d_0[r-1][cnt-i]+1+c_0[2][r-1][i]), \min_{0 \leq i \leq g[r-1]} (d_1[r-1][cnt-i]+m+z[r-1][i]). If we ignore the rows with no cheese on them, the complexity of this part would be O(K^2).
The first part of the min function above is for the case where we eat cnt-i wedges from the first r-2 rows, climb up from the first column and reach row r-1, eat i wedges from the (r-1)^{th} row, come back to the first column and then go up.
The second part is for the case where we do the same thing as the first case, except that we climb up to row r-1 from the last column.
2_ Similar to 1.
3_ ans[r][cnt] = \min (ans[r-1][cnt], \min_{1 \leq i \leq g[r]} (d_0[r][cnt - i] + c_0[1][r][i]), \min_{1 \leq i \leq g[r]} (d_1[r][cnt-i] + c_1[1][r][i])). If we ignore the rows that don’t have any cheese on them, the complexity of this part would be O(K^2).
The first part of the min function above is for the case where we take the wedges from the first r-1 rows.
The second part is for the case where we climb up to the r^{th} row from the first column and eat i wedges from the row.
The third part is for the case where we climb up the r^{th} row from the last column and eat i wedges from the row.
4_ The answer depends on the position of the rightmost cheese wedge we eat on this row. Let’s loop over this rightmost cheese. Assume that the wedges on row r are numbered from left to right. Assume the rightmost wedge we eat is the i^{th} one. It’s easy to see that if we want to eat cnt wedges, it’s best to eat the cnt wedges with minimum t amongst these i wedges. This observation gives us the following solution:
Let i be the rightmost cheese wedge we eat. Sort the first i wedges and set c_0[1][r][cnt] = \min (c_0[1][r][cnt], pt[cnt]) where pt is the partial sum array over the sorted cheese wedges. Note that since we have the sorted array for the first i-1 wedges, the sorting can be done in O(i). Hence, this part of the solution runs in O(g[r]^2), which leads to the overall complexity of O(K^2) over all rows.
5_ Similar to 4.
6_ Similar to 4.
7_ Similar to 5.
8_ To calculate z[r][cnt], we can sort the cheese wedges on row r based on t(the time required to eat a wedge). Then, z[r][cnt] would be equal to the sum of the first cnt t s. If we ignore the rows that have no cheese on them, this array can be calculated in O(K \times log(K)).
The total complexity of this solution is O(K^2). Refer to the setter’s solution to see the implementation.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.