Timosh's blog

The only FST in the contest?
By Timosh, history, 6 months ago, In English

At the end of today's contest after solving A-E, I was like "yay, finally, 2200+". But as system testing ended, my submission for D got FSTed (I still don't know why). Moreover, It seems like it's the only FST for problem D in the entire contest, which makes it even more disappointing. I don't know how to feel about this, maybe I invented new ways to fail system testing?

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

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

Lol I just wrote the same thing:P

→ Reply
»
6 months ago, hide # |
← Rev. 2  
Vote: I like it +12 Vote: I do not like it

that's weird cuz they said in an announcement that "In problems A-D, system tests are equal to pretests."

maybe it was a cosmic ray

→ Reply
»
6 months ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

As I know, there are some gaps between the environment of PT and ST. Danger optimization, undefined behaviour can change the result of execution between PT and ST(e.g. I got FST with Ofast)

→ Reply
»
6 months ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

Same, I got FST on problem B which left me extremely confused. Is this a new ragebait method?

→ Reply
»
6 months ago, hide # |
← Rev. 2  
Vote: I like it +30 Vote: I do not like it

The following part of your code is suspicious:

vi f(2e5 + 5);

because the actual limit of $$$n$$$ is $$$n \le 3 \cdot 10^5$$$.

Buffer overflow makes your program's behavior unpredictable, and it's possible that your code gave the correct answer in pretest by chance.

→ Reply
  • »
    »
    6 months ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    But I never used f in my code, the constraints on $$$n$$$ should not really matter

    → Reply
    • »
      »
      »
      6 months ago, hide # ^ |
       
      Vote: I like it +17 Vote: I do not like it

      Yeah, you are right! It turns out your code has more subtle buffer overflow.

      I tried to compile your code with extra checks(*) and found the line 117 has buffer overflow:

                  while (l < ind[i - 1].size() && ind[i - 1][l] < ind[i][j])
                                                            ^^^^^^^^^

      This can be triggered with the sample input — your code tries to access j = 1 (2nd) element of ind[i], which has only one element.

      (*) I always try to compile my code with the following flags (on Linux), to enable extra checks that detect out-of-bounds accesses, integer overflow etc.

      g++ -Wall -Wextra -O0 -ggdb -fsanitize=address,undefined \
  -D_GLIBCXX_DEBUG -D_GLIBCXX_SANITIZE_VECTOR X.cc
      → Reply
      • »
        »
        »
        »
        6 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Yeah, looks like it. I have no idea how that passed pretests. I changed j -> j-1, and now it's AC

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

        Thanks, your comment finally made me setup sanitizers. Are there any other flags you use? Maybe, -O2 for estimating the run time of your solution for tight cases?

        → Reply
        • »
          »
          »
          »
          »
          6 months ago, hide # ^ |
           
          Vote: I like it +3 Vote: I do not like it

          All the flags I currently use are listed above. I normally use -O0 to make debugging with gdb easier — this is sufficiently fast for small inputs. When I need to check performance with large inputs, I remove all those flags for checking and just use -O2. I have a tiny script that compiles a file with one of those sets of flags, so I don't have to copy-paste each of those flags manually and I can switch debug mode/performance mode easily.

          → Reply