I have seen several solutions of July Challenge 13 CHEFRECT. In every solution what people have done is checked for the edge cases and then gave the general answer as (k+1)/2. Could anyone explain how this works?
umm… its simple… the first step taken by the chef is either (0,1) or (1,0) … so therefore…in any case, the maximum no. of stones would be either of these positions… and in order to minimise the total no. of stones in a particular move, he would take them one after the other, in each complete walk.
if the no. of walks is odd/even , the no. of stones collected, would be in accordance… (k/2 or (k+1)/2)…
don’t forget the corner cases as well …
@harsh_agarwal, your doubt is correct and it works like this :-
no of possible paths through M cells is (M-2)+1.
no of possible paths through N cells is (N-2)+1.
Total no of possible paths is (M-2)+(N-2)+1.
where,M and N were column size and row size given in the input.
Now,you need to maximize the value of S= maximum no of stones possible in a cell.
If you visualize,clearly you can see that the chef has to traverse either cell (1,2) or (2,1) for every possible path it takes.That means maximum no of stones possible in a cell can be in cell (1,2) or (2,1) only.
So if we evenly distribute the K journeys among this two cells then we can get value of S.
For example,if K=70 then if we do even distribution among these two cells,then no of stones in (1,2) or (2,1) = K/2;
If K= 41,then we cant do even distribution among two cells (1,2) and (2,1),so one cell will contain one stone more than another so S = K/2 + 1 either in cell (1,2) or (2,1).
PS: Whole point of cracking the question is to concentrate just on two cells (1,2) and (2,1) in the whole N*M grid.