PROBLEM LINK
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).
- Go right from (1,1) to (1,C). Then, go down from (1,C) to (R,C).
- 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 
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
… Now I get the solution … But one thing is still troubling me … The problem statement reads