jac_nikola's blog

By jac_nikola, history, 4 weeks 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

»
4 weeks 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).

»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
  • »
    »
    4 weeks 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
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You can refer to my submission

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

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

    • »
      »
      »
      4 weeks 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.