LEMOUSE - Editorial

Problem Link:

Practice

Contest

Difficulty:

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:


fillShadows(N, M, Mouse[][])
//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
				Shadow[i-1][j]++
				Shadow[i][j-1]++
				Shadow[i+1][j]++
				Shadow[i][j+1]++
	return Shadow;
	
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

16 Likes

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

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

Please explain .

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

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

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?

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

Nicely explained @pragrame !!!Got it!

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

excellent problem…