CHRECT - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY

CAKEWALK

PREREQUISITES

Ad Hoc

PROBLEM

You are given a grid of R rows and C columns. The rows are numbered from 1 to R from top to bottom. The columns are numbered from 1 to C from left to right.

You wish to move K times from the cell numbered (1,1) to the cell numbered (R,C). While moving, you are only allowed to go down or right.

Additionally, there is a value written on each of the cells. This value is originally 0 for all the cells. As you move from (1,1) to (R,C), the value on the cells you touch is incremented by one. This is done for all the cells you touch in your journey, except the first and the last cells.

Of course, since you have K journeys, it is possible that some cells have a value higher than 1, since you touch them in multiple journeys. Let N be the largest value among all the cells after you have completed K journeys.

You wish to optimize your journeys such that the value of N that you will calculate at the end of the K journeys is as small as possible.

QUICK EXPLANATION

First, notice that if we transpose the grid, meaning - we play the game on a grid of C rows and R columns instead - the answer doesn’t change. If it isn’t obvious to you why that is, consider how any unique path from the original grid will map to a unique path on the transposed grid by replacing all the “right” moves by “down”, and replacing all the “down” moves by “right”.

This means that without loss of generalization, we can assume that R ≤ C. Now, we can split the solution into two cases.

EXPLANATION

R = 1

In this case, each journey is equivalent to going in a straight line. Thus, all the cells except (1,1) and (1,C) will have the value K at the end of K journeys.

There are two cases to consider here. If C = 1 or 2, then there are no intermediate cells whose values will be incremented. Thus, the answer will be 0 in such cases. For all larger C, the answer is K.

R > 1

It is immediately apparant that in each of your journeys, your first step will be either on (1,2) or (2,1). Hence one of these cells will have a value of ceil(K/2) and the other floor(K/2).

If you split your journeys into the following two types, you can be assured that no other cell will have a value higher than ceil(K/2).

  1. Go right from (1,1) to (1,C). Then, go down from (1,C) to (R,C).
  2. Go down from (1,1) to (R,1). Then, go right from (R,1) to (R,C).

Thus, the answer must be ceil(K/2).

The following method returns the right value.

smallestN(R,C,K)
    if R > C then swap(R,C)
    if R = 1 AND C ≤ 2 then return 0
    if R = 1 then return K
    return ceil(K/2)

As evil as they come, the setter and tester for this problem left the limits of the problem small enough to tease the possibility of a solution based on maximum flow. I wonder whether you fell for it :wink:

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes

We need to check no of paths going through cells (1,2) and (2,1) only as they are the closest and will be traversed more than any cells.So answer was to evenly distribute it among the two cells with S minimum possible.

if k%2==0,then S= k/2;
if k%2!=0 then S= k/2 +1 ;

:smiley:

1 Like

Suppose cells (1, 1) and (R, C) were also included. Then, these would contain k stones, no matter how we travel. Because, these cells are must-go-to cells.

Now, the cells that will be travelled second-largest number of times, will be the ones immediately next to these. (1, 2) and (2, 1) in case of cell (1, 1), and (R, C-1) or (R-1, C) in case of (R, C). We need to equally distribute, so that maximum value is minimized, which is integer part of (K+1)/2.

Of course, special cases like when R=1 or when C=1 has to be handled specially.

Link to my AC solution: http://www.codechef.com/viewplaintext/2326845

Hi,

I jus could not solve this problem … :frowning: :frowning:

As we need to take the routes K times such that value of N is minimized, why cant we take a same particular route K-1 times and a different route 1 time alone , so that the minimum value that we get is 1 …?

I am unable to understand the solution … some one please please please explain me what’s wrong with my understanding…

Hello @frompondy,

Note that you wish to minimize the value but that is done globally, if you had a value of 1 and other of K-1, you would have a very high value (K-1) on a given cell, which, according to the problem is not wanted… To minimize the global value of K you need to “alternate” between the cells which are adjacent to the beginning cell…

Try to read editorial carefully…

Best regards,

Bruno

2 Likes

Thanks a ton for your reply Bruno :slight_smile: … Now I get the solution … But one thing is still troubling me … The problem statement reads
“At the end of all the K journeys, let the number
of stones, in the cell with the maximum number of stones, be equal to S. Chef wants to know what is the smallest possible value for S.” … Here no where is it mentioned that we need to minimize the value globally … It just asks for the “smallest value of S” … Could you please guide me to line in problem statement which says that the global value should be minimized … plzzz … thanks for ur time once again …

@gamabunta…sir i followed the logic exactly and still getting WA. Can you help me out, or anybody else. Plzz. Below is what I have done.

http://www.codechef.com/viewsolution/4346381