Can anyone give me any suggestions to implement this problem(The statement):
I cannot understand how to implement “the maximum number of consecutive segments we can travel in any direction” constraint.The rest is simple calculate the number of paths(with holes) one can travel,which can be implemented via Dynamic Programming.
I guess you are going to implement dynamic programming starting from the start node. Every time you check for a valid path to a node from its neighbouring nodes, maintain two counters, one counting the cumulative distance traversed from left to right to reach that node and the second counter counting the cumulative distance traversed from up to down, your decisions on the collective paths would depend on whether the cumulative distance exceeds the threshold given as input.
That can also be implemented with DP, though a harder DP. You need to have a DP state as follows:
ways[r][c][p][dir] = number of ways to go from (r, c) to (R, C) if we have already moved p steps in direction dir.
Note that ways[R][C][p][dir] = 1, for all p and dir. i.e. there is only one way from (R, C) to itself.
Also, if p == d, i.e. you have already moved the maximum allowable steps in a direction, then:
ways[r][c][d][down] = ways[r][c][1][right] and
ways[r][c][d][right] = ways[r][c][1][down]
Which is to say, if you have come to (r, c) having moved the maximum steps in a given direction (down or right), your only possible path from here is to take one step in the other direction (right or down, respectively).
Otherwise, consider the situation: you are at segment (r, c), and you have moved p steps downwards already. There are two possible moves: right or down. If you move right, then the number of ways from there is ways[r][c + 1][1][right].
If you move down, then the number of ways from there is ways[r + 1][c][p + 1][down]. If you continue in the same direction, the number of consecutive segments in the same direction is incremented. If you change direction then it is reset.
So we have:
ways[r][c][p][down] = ways[r][c + 1][1][right] + ways[r + 1][c][p + 1][down].
Similarly you can get:
ways[r][c][p][right] = ways[r][c + 1][p + 1][right] + ways[r + 1][c][1][down].
The answer is given by ways[1][1][0][down] or ways[1][1][0][right]. (both are same)
Here is my code implementing this: http://pastebin.com/cYV3G8dW
Note that I consider 0 as right and 1 as down.
4 Likes
Wow 4 dimensional DP.
Can you help me with this problem (http://www.iarcs.org.in/inoi/2012/zco2012/zco2012-2b.php).
Please post the answer here (http://discuss.codechef.com/questions/57151/zco-dynamic-programming-problems?page=1#57307) .
Well it works, I submitted it on the server. Not very difficult to implement either
How did you came up with this sub-problem formula? Can you at least say how did you came up to these dimensions.I thought it to 3 dimensional,then realized(by reading your explanation) that the variable direction is also required. I cant ask you during the competitions so I need to know how did you came up with this.
Well, same as you, except that I also realized that you need direction… sorry, I don’t know how to explain that.
@pushkarmishra is there a better solution?
@superty Can you give me the pseudo-code of the problem( http://www.iarcs.org.in/inoi/2012/zco2012/zco2012-2b.php ) then, I am having difficulties in solving it.
It has a better solution O(n^2) . We deploy dp with graph-cutting.
Initialize first row and coloumn : Start filling dp[][]=1 from 0th node to (d-1)th node. Break in b/w if you encounter a blocked node. After initialization we enumerate nodes top to bottom and left to right. Then simply dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-d-1][j]-dp[i][j-d-1] . This forms the raw algorithm but care has to be taken managing negative values and in avoiding invalid calls (ofcourse)…
1 Like
Yeah am able to comment xD
this is exactly wt i did but my score is 20…
http://inoi15.discuss.codechef.com/questions/60844/changed-once-again-highwaybypassinoi-practice-server
This logic (and therefore, your program) fails on the following case:
5 2 2
1 1
1 1
1 1
1 1
1 1
The answer is 1. Your algorithm gives 0.
so how should i correct it…
I don’t think that algorithm can be modified to get it to pass, but maybe it can. You’re probably better off starting from scratch with an entirely different algorithm though.
Note that ways[R][C][p][dir] = 1, for all p and dir. i.e. there is only one way from (R, C) to itself.
Also, if p == d, i.e. you have already moved the maximum allowable steps in a direction, then:
ways[r][c][d][down] = ways[r][c][1][right] and
ways[r][c][d][right] = ways[r][c][1][down]
Don’t you think ways[r][c][d][down] = ways[r][c+1][right] and
ways[r][c][d][right] = ways[r+1][c][1][down]. A typo there!
@superty Shouldn’t ways[r][c][d][down] = ways[r][c+1][1][right] and ways[r][c][d][right] = ways[r+1][c][1][down] because that is what you have done in your solution and when we have reached max. allowable distance we need to move in the other direction i.e if we are moving down at[r][c] we will have to move to [r][c+1] and vice versa.
1 Like
Yeah, I guess that’s a typo !
Perforiming the below for case where d = max(R, C) - 1. Still having many wrong cases. Please help
int returnPath(vector<vector > data){
int R = (int)data.size();
int C = (int)data[0].size();
if(data[0][0] == 0)
return 0;
vector<vector<int> > arr(R,vector<int>(C,0));
arr[0][0] = 1;
for(int i=1;i<R;i++){
if(data[i][0] != 0)
arr[i][0] = arr[i-1][0];
}
for(int j = 1; j<C; j++){
if(data[0][j] != 0)
arr[0][j] = arr[0][j-1];
}
for(int i = 1;i<R;i++){
for(int j= 1;j<C;j++){
if(data[i][j] != 0){
arr[i][j] = arr[i-1][j] + arr[i][j-1];
}
}
}
for(int i = 0;i<R;i++){
for(int j= 0;j<C;j++){
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
return arr[R-1][C-1];
}