PROBLEM LINK:Author: 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 $(r1)$ 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[r1]} (d_0[r1][cnti]+1+c_0[2][r1][i]), \min_{0 \leq i \leq g[r1]} (d_1[r1][cnti]+m+z[r1][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 $cnti$ wedges from the first $r2$ rows, climb up from the first column and reach row $r1$, eat $i$ wedges from the $(r1)^{th}$ row, come back to the first column and then go up. 2_ Similar to 1. 3_ $ans[r][cnt] = \min (ans[r1][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][cnti] + 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 $r1$ rows. 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 $i1$ 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.
This question is marked "community wiki".
asked 24 Jan, 02:24

I have found that the reason for the NZEC was simply that the output buffer was too small. You can find the revised submission at https://www.codechef.com/viewsolution/22751148 where I have also changed some of the function names for clarity and added more explanatory comments. answered 02 Feb, 08:22

My solution requires only 1dimensional arrays, and fewer of them, and is I believe simpler. It requires 5 arrays each of length (k+1), with item 'i' (from 0 to k) containing either the minimum time to eat 'i' cheeses or the minimum time to reach a particular cell after eating 'i' cheeses. Together with each array is stored 'count' = the number of elements of the array which have been defined so far. The arrays are These arrays are instances of a class which contains functions for operating on arrays I now describe the main algorithm: Sort the cheeses into order, first by row, then by column. Loop for each row with cheese: If not the first row, add the number of cells from the previous row to 'left' and 'right'. If not the last row, the mouse may go on to the end of the row. AddMerge 'to_right' into 'right'. This is a longlived and persistent mouse. Some of the cheeses may take 30 years to eat, with a similar time for the journey between cheeses. It could well take 100000 years to eat all the cheeses. My solution is available at https://www.codechef.com/viewsolution/22702681 For some reason which I do not yet understand, it fails with NZEC for some cases. answered 02 Feb, 05:59
