shiny_shine's blog

AtCoder taught me a lesson
By shiny_shine, history, 9 months ago, In English

Abstract

Never use reference value on std::priority_queue, otherwise it will be affected when you push in something "greater" than it. I lose my first chance to AK an ABC in this reason.

Detail

When I was solving D, I wrote this

while(q.size()){
    auto& [stp,t1,t2]=q.top();
    q.pop();
    auto& [drx1,dry1]=t1;
    auto& [drx2,dry2]=t2;
    if(t1==t2){
        printf("%d\n",stp);
        exit(0);
    }
    for(int i=0;i<n;i++){
        int nx1=drx1+dx[i],nx2=drx2+dx[i],
        ny1=dry1+dy[i],ny2=dry2+dy[i];
        if(max(nx1,ny1)>=n or min(nx1,ny1)<0 or s[nx1][ny1]=='#')nx1-=dx[i],ny1-=dy[i];
        if(max(nx2,ny2)>=n or min(nx2,ny2)<0 or s[nx2][ny2]=='#')nx2-=dx[i],ny2-=dy[i];
        if(vis[nx1][ny1][nx2][ny2])continue;
        vis[nx1][ny1][nx2][ny2]=true;
        q.push({stp+1,{nx1,ny1},{nx2,ny2}});
    }
}

It seems no flaw in it, but when I input

5
....#
#..#.
.P...
..P..
....#

it threw segmentation fault.

Then, I add some debug code

...
printf("%d %d %d %d\n",drx1,dry1,drx2,dry2);
fflush(stdout);
...
printf("%d\n",i);
fflush(stdout);
...
printf("%d %d %d %d\n",nx1,ny1,nx2,ny2);
fflush(stdout);

in it, and it put

2 1 3 2
0
2 2 3 3
1
3 2 4 3
2
-14220976 545 -15256416 545

before it ran into the segmentation fault.

I realized that the container did something like cumulative sum. It's not what I want.

Then, I deleted all the character & in my code and modified it to

while(q.size()){
    auto [stp,t1,t2]=q.top();
    q.pop();
    auto [drx1,dry1]=t1;
    auto [drx2,dry2]=t2;
    if(t1==t2){
        printf("%d\n",stp);
        exit(0);
    }
    for(int i=0;i<4;i++){
        int nx1=drx1+dx[i],nx2=drx2+dx[i],
        ny1=dry1+dy[i],ny2=dry2+dy[i];
        fflush(stdout);
        if(max(nx1,ny1)>=n or min(nx1,ny1)<0 or s[nx1][ny1]=='#')nx1-=dx[i],ny1-=dy[i];
        if(max(nx2,ny2)>=n or min(nx2,ny2)<0 or s[nx2][ny2]=='#')nx2-=dx[i],ny2-=dy[i];
        printf("%d %d %d %d %d\n",stp,nx1,ny1,nx2,ny2);
        if(vis[nx1][ny1][nx2][ny2])continue;
        vis[nx1][ny1][nx2][ny2]=true;
        q.push({stp+1,{nx1,ny1},{nx2,ny2}});
    }
}

and it put

0 2 2 3 3
0 3 1 4 2
0 2 0 3 1
0 1 1 2 2
1 3 2 4 3
1 4 1 4 2
1 3 0 4 1
1 2 1 3 2
2 4 2 4 3
2 4 1 4 2
2 4 0 4 1
2 3 1 3 2
3 4 3 4 3
3 4 2 4 3
3 4 1 4 2
3 3 2 3 3
4

it's the wrong answer.

I spend about 5 minutes to realize that priority_queue put the greatest element at the top, then I modified it a bit to

while(q.size()){
    auto [stp,t1,t2]=q.top();
    q.pop();
    auto [drx1,dry1]=t1;
    auto [drx2,dry2]=t2;
    if(t1==t2){
        printf("%d\n",-stp);
        exit(0);
    }
    for(int i=0;i<4;i++){
        int nx1=drx1+dx[i],nx2=drx2+dx[i],
        ny1=dry1+dy[i],ny2=dry2+dy[i];
        // fflush(stdout);
        if(max(nx1,ny1)>=n or min(nx1,ny1)<0 or s[nx1][ny1]=='#')nx1-=dx[i],ny1-=dy[i];
        if(max(nx2,ny2)>=n or min(nx2,ny2)<0 or s[nx2][ny2]=='#')nx2-=dx[i],ny2-=dy[i];
        // printf("%d %d %d %d %d\n",stp+1,nx1,ny1,nx2,ny2);
        if(vis[nx1][ny1][nx2][ny2])continue;
        vis[nx1][ny1][nx2][ny2]=true;
         q.push({stp-1,{nx1,ny1},{nx2,ny2}});
    }
}

then it finally put the correct answer.

Thanks atcoder_official for your lesson, and the easiest G ever that's also the first G I solved during the contest.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

it actually occurs to not only priority_queue but also other STL data structures like queue, deque, vector, map, ...

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 4   Vote: I like it +4 Vote: I do not like it

    UPD: What I mentioned below is actually wrong. Iterators, reference and pointers of STL container elements will not always work after structure modification due to special allocation logic to maintain mutable vector sizes. However, modifying the value of elements without pushing or popping in some linear dses like queue and vector is usable.

    For linear data structures like queue, deque, vector reference is guaranteed to work.

    The reason why it doesn't work for priority_queue and map is that they use data structures called balance trees and heaps, which does not support modification to arbitrary elements without modifying the structure.

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

      I actually don't think so, there was one time when I used a queue <vector <int>> and then used the reference of the front one after it'd been deleted. It was horrible and took me about an hour to realise it.

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

        then what do you expect from wild references

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

          meh, it was a long time ago when I was a newbie so I call it a lesson

          → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      For linear data structures like queue, deque, vector reference is guaranteed to work.

      That is not true: if you have something like std::vector<int> vec (1, 2); int &a = vec[0], then the reference a will point to garbage values once you push things to the back of vec (because at some point, the vector will exceed its capacity and will be reallocated).

      → Reply