justHusam's blog

Strange runtime error in the sort comparison function
By justHusam, history, 9 years ago, In English

Today I was solving this problem 632C - The Smallest String Concatenation.

The judge's response for this code 18114819 was Runtime error on test 8.

Then I changed only the last line in the sort comparison function (comp function) from (return true) to (return false) (code: 18114847), and the judge's response was Accepted.

Does anyone have an explanation for that?

Thank you.

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

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

Your comparator returns 1 for comp(a, a) which is incorrect.

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

1800+ guy asking this... Well, I have an explanation in just four letters!

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

    Thank you for your high morals.

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

    LOL!! You're participating for more than 5 years and still violet!!

    Why so harsh? It's one of trickier technical details.

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

      I'm violet because I'm not able to solve hard problems. Everyone has their limits in different areas and it can't be fixed. From the other side, everyone is able to read a language manual. When I use a function, I read its docs. And you? The topicstarter doesn't. He didn't even try to find it in Google or Stackoverflow.

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

        I will surprise you but ability of understanding manuals and efficient googling is also a skill one can be good or bad at it. For example, I am at most cyan at both :). Even if it is possible that I will be able to find an answer in Google I often choose to ask somebody, because a friend will probably understand me better than Google.

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

      Well. I have an explanation in just three letters!

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

Becuase std::sort is using operator < as a parameter, it is incorrect to use function which returns true in case of equality. This might sometimes end up in an RE. Not sure when exactly, but in most cases it will.

→ Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

The comparator function must meet the requirements of Compare concept i.e if comp(a,b) = true then comp(b,a) must return false and vice versa . Runtime error can occur in case where you have used <= or >= in your custom comparator function . hope you got it

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

    After 4 years I would hope he got it too...

    → Reply