Practice

Contest

Simple

# Pre-requisites:

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 (N-1, M-1), 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 double-counting. 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 double-counting a single mouseâ€™s shadow?

There are essentially just two cases.
Case 1: You pass through the mouse yourself. Then you are clearly counting itâ€™s shadow for when you come near the mouse, as well as when you go away from it!
Case 2: You turn a corner, and count the shadow of the mouse opposite that corner twice.

The above â€śCase 2â€ť is as follows (â€śEâ€ť is the path taken by LE, M is the mouse location)

``````
...
...
...EE
...ME
.....

``````

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:

``````
...
...
..EM..
..EE..
......

``````

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 double-count mouse.

Let DP[i][j][0] = Minimum number of scared mice with destination (i, j) assuming you came from the left,
and DP[i][j][1] = Minimum number of scared mice with destination (i, j) assuming you came from the top.

Pseudocode follows:

``````
//Assuming Shadow[i][j] = 0 for all i, j
for(i = 0; i < N; i++)
for(j = 0; j < M; j++)
if(Mouse[i][j] == 1)
//check you don't exceed the grid here

doDP()
DP[0][0][0] = DP[0][0][1] = Shadow[0][0] - Mouse[0][0]
for(i = 0; i < N; i++)
for(j = 0; j < M; j++)
//ensure everything is "within the grid" while computing
DP[i][j][0]=Shadow[i][j]-Mouse[i][j] + min(DP[i][j-1][0], DP[i][j-1][1] - Mouse[i-1][j])
DP[i][j][1]=Shadow[i][j]-Mouse[i][j] + min(DP[i-1][j][0] - Mouse[i][j-1], DP[i-1][j][1])
output min(DP[N-1][M-1][0], DP[N-1][M-1][1]) + Mouse[0][0] + Mouse[N-1][M-1]

``````

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 (N-1, M-1), in which case we have removed our â€śdouble countâ€ť mice already when we havenâ€™t even double-counted them, so we should add them back.

Thus, the overall time complexity is O(N * M) per test-case.

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

21 Likes

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][j-1][0], DP[i][j-1][1] - Mouse[i-1][j])

and

min(DP[i-1][j][0] - Mouse[i][j-1], DP[i-1][j][1])

Happy Coding!!!

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

3 Likes

@upendra1234,
[Comment is too short for this, so Iâ€™m posting as â€śanswerâ€ť]

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][j-1][0] only.

If we come in an L, then:
`E? EE`
So if there was a mouse at â€ś?â€ť, we would be double counting itâ€™s shadow. The bottom right E is (i, j), so the â€ś?â€ť, where we need to check for a mouse is at (i-1, j). Hence, we say, â€śCome from (i, j-1), through the top, and substract a possible doublecount of the mouse at (i, j-1)'s shadowâ€ť.

2 Likes

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 ??

3 dimenstional solution of dynamic prog
nice

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

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

1 Like

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].

1 Like

Thanks @pragrame

@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) ,(i-1,j) ,(i,j-1), (i+1,j) ,(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][1]=Shadow[i][j] + min(DP[i-1][j][0] - Mouse[i][j-1], DP[i-1][j][1]-Mouse[i-1][j])

Please correct me, if I am wrong!

Me too done the sameâ€¦
http://www.codechef.com/viewsolution/2216445

1 Like

@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(i-1, j) OR in dp(i, j-1).

@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][j-1][0]-Mouse[i][j-1], DP[i][j-1][1] - Mouse[i-1][j] - Mouse[i][j-1])

DP[i][j][1]=Shadow[i][j] + min(DP[i-1][j][0] - Mouse[i][j-1] - Mouse[i-1][j], DP[i-1][j][1]-Mouse[i-1][j])

Does the above make sense?

Nicely explained @pragrame !!!Got it!

excellent problemâ€¦