javacoder1's blog

NEED HELP IN CODEFORCES GRAPH PROBLEM
By javacoder1, history, 9 years ago, In English

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

Can anyone point my mistake? Thanks.

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by javacoder1 (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.net/contest/242/submission/12684561

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply