coding_weeb's blog

Strange bug in 877D — Olya and Energy Drinks
By coding_weeb, history, 8 years ago, In English

Here is the problem's link : http://mirror.codeforces.com/contest/877/problem/D

In this problem I used BFS to solve it. In my WA submission I choose to break when the distance from the origin of the cell I am traversing is smaller or equal to the distance of the point of the front of the queue plus 1. In my accepted solution I choose to break when the distance from the origin of the cell I am traversing is smaller or equal to the distance of the point of the front of the queue. But I can't understand why my first solution fail. Can anyone give me the explanation ?

Correct : http://mirror.codeforces.com/contest/877/submission/31687084 WA: http://mirror.codeforces.com/contest/877/submission/31686998

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

»
8 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

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

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

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

Undefined behaviour. xx + i can be greater than array size.

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

    I have already taken care of that situation by creating a border around the original array.

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

      Ah, sorry. Let k = 3, xx = 3, yy = 3, dist[3][3] = 5, dist[4][3] = 6, dist[5][3] = INF. This situation is possible, if you have already been in xx = 4, yy = 2 and dist[4][2] = 5. You have to change dist[xx + 2][yy], but with +1 your code breaks.

      → Reply