MMC - Editorial

PROBLEM LINK:

Practice
Contest

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.

1 Like

My solution requires only 1-dimensional 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

‘result’ = the minimum time to eat ‘i’ cheeses

‘left’ and ‘right’ = the minimum time to reach the left and right edges of the current row after eating ‘i’ cheeses

‘to_right’ and ‘to_left’ = the minimum time to reach the current cell while working along the current row after eating ‘i’ cheeses

These arrays are instances of a class which contains functions for operating on arrays

‘Add’ adds a time to all elements

‘AddCheese’ adds a cheese. When a cell is visited the mouse may or may not eat the cheese there. For each ‘i’ > 0, a[i] is set the minimum of a[i] and a[i-1] + time to eat this cheese. A new element is added to the end of the array.

‘Merge’ merges another array ‘b’ into this array ‘a’. For each element ‘i’ where both a and b are defined, a[i] is set to the lower of a[i] and b[i]., For elements where only ‘b’ is defined, a[i] is set to b[i].

‘AddMerge’ adds a time to each element of ‘b’ before merging into ‘a’, without changing the contents of ‘b’ itself.

I now describe the main algorithm:

Sort the cheeses into order, first by row, then by column.

Build an array of rows with cheese.

Initialise ‘result’ to contain 1 element = 0 (no time to eat no cheese).

Initialise ‘left’ and ‘right’ to contain 1 element = time to reach first and last cell on first row with cheese.

Loop for each row with cheese:

If not the first row, add the number of cells from the previous row to ‘left’ and ‘right’.

Copy ‘left’ to ‘to_right’.

Loop for each cheese in this row:

Move to next cheese. Add time = number of cells from previous cheese or from start of row to ‘to_right’.

Add this cheese to ‘to_right’.

Merge ‘to_right’ into ‘result’

If not the last row with cheese, from here the mouse may return to the start of the row. AddMerge ‘to_right’ into ‘left’.

If not the last row, the mouse may go on to the end of the row. AddMerge ‘to_right’ into ‘right’.

If not the first row, the mouse may move along the row from right to left. Work along the row from right to left in a similar way.

This is a long-lived 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 CodeChef: Practical coding for everyone
For some reason which I do not yet understand, it fails with NZEC for some cases.

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 CodeChef: Practical coding for everyone where I have also changed some of the function names for clarity and added more explanatory comments.

2 Likes