Блог пользователя javacoder1

NEED HELP IN CODEFORCES GRAPH PROBLEM
Автор javacoder1, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← 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.net/contest/242/submission/12684561

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
  • »
    »
    9 лет назад, # ^ |
    ← 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)]++;

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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.

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 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.

→ Ответить