jac_nikola's blog

MLE while using comparator
By jac_nikola, history, 3 years ago, In English

PROBLEM LINK

MY CODE LINK

I'm getting MLE on submitting this solution. I suspect it has to do something with the comparators that I've used. I found some relevant information here.

Please help me figure out where exactly it's getting wrong. Thank you.

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

If two elements are equal the comparator should always return 0.

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

    And yeah this. https://codeforces.net/blog/entry/70237

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

    I tried doing that but it's giving me incorrect result on the sample, whereas my previous comparator logic was working fine. Could you please tell how the comparator should look like according to you?

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

      You can refer to my submission

      https://codeforces.net/contest/1551/submission/123565021

      Here check the test function, pardon me for a messy template.

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

      The problem is whenever the if statement's condition evaluates to false, the return value is independent of the order of a and b, i. e. cmp(a, b) == cmp(b, a). Consider for instance the strings "aab" and "ab". cmp1 will always return 1, violating the asymmetry property of comparators. This is UB and can lead to all sorts of internal error in the library.

      → Reply