Problem Link:Difficulty:Simple Prerequisites:Dynamic Programming Problem:Little Elephant is coordinates (0, 0) of a NxM grid A. A[i][j] = 0 if there is no mouse in cell (i, j), else it is 1, if there is a single mouse. LE is scared of a mouse if he moves into a position (x, y) where the distance between himself and the mouse <= 1. Given that he needs to reach the bottom right corner of the grid (N1, M1), and that he takes only right/down moves, find the minimum number of mice he will be scared by along such a path. Explanation:In order to solve this, let us first make a visualization: each mouse casts a "shadow" of length 1 in all four directions. Thus, LE gets scared of a mouse iff his path passes through its "shadow". Note that if it passes through the mouse itself, then it would have had to come through some shadow, and further it would go through some shadow, so we can consider it as if it has passed through the shadow only. Thus, let us assume that we have a shadow grid, where shadow[i][j] = Number of mice that cast a shadow on cell (i, j). Finding the number of mice that LE is scared of, is then just summing up values of shadow!! Well, nearly that. The fact is, we are doublecounting. In case the path that LE takes crosses the same mouse's shadow more than once, we would be counting that shadow twice as if it had come from different mice. We should ensure that we subtract such "shadows" from our answer. When will we be doublecounting a single mouse's shadow? There are essentially just two cases. The above "Case 2" is as follows ("E" is the path taken by LE, M is the mouse location) In the above, you would count M's shadow once from top, once from right. Similarly, you could be in the following symmetric case as well: In this case also, you are counting M's shadow twice. You need to handle such double counting cases. But then, how would you handle it? How would you tell if you've "turned a corner" or not? This is where DP states help. Instead of most DP, which would have N x M type states, you should here keep N x M x 2 states, where the extra "2" tells you whether you have come from "up" or from "left". Given this, you will be able to tell where you have come from, and where to look for a doublecount mouse. Let DP[i][j][0] = Minimum number of scared mice with destination (i, j) assuming you came from the left, Pseudocode follows:
In the above DP calculation, we have Shadow[i][j]  Mouse[i][j] terms common to both. If we have come from the left, we need to consider a mouse above us when our previous move was from top. If we have come from the top, we need to consider a mouse to the left of us, when our previous move was from the left. The only remaining boundary cases are when there is/are mice on the points (0, 0) or (N1, M1), in which case we have removed our "double count" mice already when we haven't even doublecounted them, so we should add them back. Thus, the overall time complexity is O(N * M) per testcase. This was a rather beautiful problem, and although one approach has been described here in the Editorial, I'm sure a lot of people would have come up with their own interesting variations. Setter's Solution:Can be found here Tester's Solution:Can be found here
This question is marked "community wiki".
asked 19 Jun '13, 00:10
showing 5 of 7
show all

We can store the previous two directions in the dp state, and now simply check for each of the four cells , if in the previous two cells of the path it was already scared by the mouse in that cell and update. No case analysis needed for it and also simple to code. http://www.codechef.com/viewsolution/2262222 answered 19 Jun '13, 11:24

@upendra1234, The first is for DP[i][j][0], and the second for DP[i][j][1]. I'll explain one, and the other is symmetric. for DP[i][j][0], we have come from left. So thats like an "...EE" path. Further there are two cases, either we have come like in a line, or in an L. If we come in a line, then there is no "Case 2" mouse to consider. That is, "...EEE". Hence, we have DP[i][j1][0] only. If we come in an L, then: answered 19 Jun '13, 18:38

Awesome problem.... I solved it using BFS....... here is it: http://www.codechef.com/viewsolution/2259653 But, same code got WA when i used priority queue on same code...Don't know why ?? answered 20 Jun '13, 17:52

3 dimenstional solution of dynamic prog nice answered 21 Jun '13, 00:57

I used grid of set to keep track of mice which scared LE (instead of using direction..) but getting WA.. Cant figure out my mistake.. Please help.. tried in practice section too.. Submission : http://www.codechef.com/viewsolution/2307068 answered 01 Jul '13, 00:36

Some One please explain this case : I got that we are using DP[N][M][2] , basically to handle two cases one if we are passing through a corner than we are adding this left side mouse twice , and one if we are going to left > right then we are adding the current mouse twice , But i did not get this min(DP[i][j1][0], DP[i][j1][1]  Mouse[i1][j]) and min(DP[i1][j][0]  Mouse[i][j1], DP[i1][j][1]) Please explain . Happy Coding!!! answered 19 Jun '13, 10:18

Being a newbie, this was one of the most interesting problems I had ever solved. It was my first solution involving dynamic programming. Hats off to the problem setter @witua
Could you please explain more about dp part ? Why are you doing Shadow[i][j]Mouse[i][j] when we are not considering mouse itself. we have to consider its shadow.
@y07uc118: Well, if you say "when we are not considering mouse itself", do you mean that I should just sum up values of shadow along the path?
But that way, I would be counting the shadow caused by a single mouse twice (if LE's path crosses that mouse's different shadows twice along the way). I need to ensure that I subtract such cases. The Editorial's "Case 1" gets accounted for by subtracting Mouse[i][j].
@pragrame: yeah, i got that whenever i'll go through mouse i am counting it twice.one for incoming and one for outgoing. but how shadow[i][j]mouse[i][j] removing duplicates. suppose i have mouse at (i,j) ,(i1,j) ,(i,j1), (i+1,j) ,(i,j+1). so shadow[i][j]=4 and mouse[i][j]=1 here, (shadow[i][j]mouse[i][j]) what does it signify??
@y07uc118: I am confused too. Why are we subtracting mouse[i][j] when we hadn't considered it in shadow[i][j]. In fact, according to me, the dp state should be:
DP[i][j][0]=Shadow[i][j]+ min(DP[i][j1][0]Mouse[i][j1], DP[i][j1][1]  Mouse[i1][j])
DP[i][j][1]=Shadow[i][j] + min(DP[i1][j][0]  Mouse[i][j1], DP[i1][j][1]Mouse[i1][j])
Please correct me, if I am wrong!
@y07uc118: "shadow[i][j]  mouse[i][j]" signifies Add the shadows due to other mice that fall on square (i, j), and subtract the shadow caused by mouse (i, j) which you have counted earlier  in dp(i1, j) OR in dp(i, j1).
@desktop, well not quite, you will need to modify your dp slightly from that (even if you don't use mine):
DP[i][j][0]=Shadow[i][j]+ min(DP[i][j1][0]Mouse[i][j1], DP[i][j1][1]  Mouse[i1][j]  Mouse[i][j1])
DP[i][j][1]=Shadow[i][j] + min(DP[i1][j][0]  Mouse[i][j1]  Mouse[i1][j], DP[i1][j][1]Mouse[i1][j])
Does the above make sense?
excellent problem..