### javacoder1's blog

By javacoder1, history, 5 years ago, ,

Hey i was trying to solve King's Path on codeforces http://codeforces.com/problemset/problem/242/C but i am getting wrong answer on test 10; my code: http://codeforces.com/contest/242/submission/14186492

Can anyone point my mistake? Thanks.

• -8

 » 5 years ago, # |   0 Many of the solutions that i saw involved traversing the columns in a row to mark them elgible for being visited but this may time out if adequate tests are provided as their difference can be as large as 10^9
 » 5 years ago, # |   0 Auto comment: topic has been updated by javacoder1 (previous revision, new revision, compare).
 » 5 years ago, # | ← Rev. 3 →   0 BFS/DFS through matrix. But, since total number of fields is 10^5 it will clearly pass time. You don't need to traverse through whole matrix, mark rows and columns that you can visit (I used map). It will increase overall complexity, but it is more than enough.You can check my code: http://codeforces.com/contest/242/submission/12684561
•  » » 5 years ago, # ^ |   0 I tried to use dijkstra algorithm to figure the shortest path from source to end.I need someone to find a bug in my code so that it works.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Also your solution required iterating from start of a column to end but since no information is given about their difference we just can't iterate. Answer being less than 10^5 doesn't imply that the difference can't be as large as 10^9. Point me if i am wrong. this line: scanf ("%d%d%d", &red, &poc, &kraj); for (int i=poc;i<=kraj;i++) allow[make_pair(red, i)]++;
•  » » » 5 years ago, # ^ |   0 'Total length of all given segments doesn't exceed 10^5'. When we sum iterations of all these for loops, this sum cannot exceed 10^5, and that's the whole point.
 » 8 months ago, # |   0 the segments can be separated. e.g: 1 4 & 7 9. Your code will make all the cells between 1 and 8 allowed while 5 and 6 are not.
•  » » 8 months ago, # ^ |   +8 I think OP probably doesn't care anymore...
•  » » » 8 months ago, # ^ |   0 True, but I suffered with the same bug so I and a friend helped me find it out so I had to celebrate with the internet LOL