radoslav11's blog

Lower bound on empty set is TL!? Or something like that.
By radoslav11, history, 9 years ago, In English

While solving Goodbye 2015, E i was getting TL on test 11. Now after the contest I decided to see what was the problem.

After some debugging I found that when you do lower bound on an empty set it gives TL:

http://mirror.codeforces.com/contest/611/submission/15127498 — AC
http://mirror.codeforces.com/contest/611/submission/15126396 — TL11

The only difference is if(s.size() == 0) break;

So I want to ask if there are similar issues with the std::set.

PS: This was a good lesson for me. Next time I wont try debugging one solution for 2 hours and will solve the other problems.

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

»
9 years ago, # |
← Rev. 3   Vote: I like it -12 Vote: I do not like it

.

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

    It actually will never be infinite. I've even added another way of breaking it: if the size of the set last time (last_sz) is equal to the current size, then I just break the cycle. I also debugged it and while doing so it turned out that after s.lower_bound({c[0], 0}) it the program didn't continue and just made this operation for infinite time.

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

If s is empty you try to erase s.end(). As I understand it's undefined behaviour.

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

    You're right. . .
    I feel so dumb now. But still I'll know this for next time. :/

    Thanks!

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

    But then should't it crash?

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

      Undefined behaviour means anything could happen. Anything. It could even print "I love pancakes" and then crash, and it would be still ok according to the documentation. But yes, crashing is what you would expect the most.

      → Reply