DISCUSSION FOR LEMOUSE

Please elaborate the explanation on LEMOUSE JUNE CHALLENGE 2013.

This is basically a dynamic programming problem. You start from the bottom right of the board ie. A[n-1][m-1] and work towards A[0][0].

The following is the logic that I used. There may be other ways to do this problem

Essentially you need to keep track of two 2D matrices.
The first one will keep track of how many mice scare little elephants if they travel through a point [i][j]. Lets call this table as “DP”
The second one keeps track of where we go from a point [i][j] such that it minimizes the number of mice that scare little elephants. Lets call this table as “PATH”

  1. At each position [i][j], we check if there are mice above and to the left. Lets denote this number as L. Hence L = a[i-1][j] + a[i][j-1]

  2. Now, we do not need to consider a[i][j], a[i+1][j], a[i][j+1]. Because they have already been considered because we are doing dynamic programming from bottom to top. Except in following cases,

  3. Suppose after [i][j] you go to [i+1][j] and then in turn it goes to [i+2][j], then A[i][j+1] will never be considered. Hence you need to consider that.

  4. Suppose after [i][j] you go to [i][j+1] and then in turn it goes to [i][j+2], then A[i+1][j] will never be considered. Hence you need to consider that.

  5. Or you can go in any direction because afterwards any path leads to minimum. Here you can consider min(A[i][j+1], A[i+1][j])

  6. Hence to remember where we “came from”, we use the table PATH and use this to determine best path bottom to top.

  7. Then we take the minimum of the DP[i+1][j] and DP[j+1][i], check where each of them “came from”/“go to”, add A[i+1][j] or A[i][j+1] accordingly. Add L to both of them and then put DP[i][j] as the minimum of these both values.

  8. The final answer should be in DP[0][0]. Also you must perform bounds/range checking wherever appropriate.

Hence the time complexity is O(n * m)

Check my solution which uses this idea http://www.codechef.com/viewsolution/2217911

2 Likes

my solution was pretty much the same. Only thing was instead of dp[][] I used up[][] and left[][] which tracks the minimum coming from each direction. (e.g. up[i][j] ~= min(left[i+1][j], up[i+1][j])

I’m not sure if this made it easier to code or not. I got W/A first try since I forgot to take into account mouses at A[n-1][m-1], A[n-2][m-1] and A[n-1][m-2]

@bhambya everyboy has used dynamic programming for this question.I wnted 2 ask can this be solved using bfs coz i tried and was getting correct answers but i got repeated tle’s.I used the same concept in bfs also as yours but i don’t know why i got tle…your solution was i can say by far the simplest to understand in dynamic programming…Thanks a lot!.

If you use BFS or DFS, you will reach same [i][j] multiple times. So basically the time complexity becomes exponential , since you are essentially enumerating all 2^N paths.
This is exactly why we use dynamic programming. We remember (memorize) the previous result at [i][j] so we do not have to calculate it again.

Maybe BFS combined with memoization can pass TLE.

Ok.now i got why i got tle …thnx a lot for the explanation will keep that in mind.

what if we use bfs with priority queue where each state is composed of coordinates of the cell, number of mice scared the elephant till now, n a visited[n][m] which tells what mice scared the elephant till now.

I tried this way but I got wrong answer. Where could be the mistake in that?

You probably counted some A[i][j] twice. You have to make sure that you consider each A[i][j] exactly once. This is explained nicely in the editorial.

That’s y I used a visited[n][m] to tell me which mice I visited till now in each step. visited was a part of the node itself so at each state I have a different visited array. Here is the link to the solution: http://www.codechef.com/viewsolution/2247209

I also use dynamic programming to compute F[n-1][m-1] from F[0][0] = T[0][0] + T[1][0] + T[0][1] where T is the input matrix. When i compute F[i][j] i use formula:

D[i][j] = Vertical mean that the optimal path to (i, j) has previous cell is (i-1, j)

F[i][j] is min of these values:

F[i-1][j] + T[i][j-1] + T[i][j+1] + T[i+1][j], if D[i-1][j] == Vertical

F[i-1][j] + + T[i][j+1] + T[i+1][j], if D[i-1][j] == Horizontal

F[i][j-1] + T[i-1][j] + T[i+1][j] + T[i][j+1], if D[i][j-1] == Horizontal

F[i][j-1] + + T[i+1][j] + T[i][j+1], if D[i][j-1] == Vertical

Here is my solution: http://www.codechef.com/viewsolution/2283362
I got WA although i successfully compare some of my results with correct solutions from other users
Can any body tell me (or just show me some of tests that make my solution incorrect) why i got WA??? I am totally a newbie and this is the first time for me on codechef :slight_smile:

u have to consider the case when the number of mice from both upper and left cells are equal.

timepass123: can you explain it in detail? I have just found that at the cell (i, j) there are 2 possible previous cells and may be expand at most 3 mice (not count the mouse at (i, j) because the previous cell has already done it)

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