Fred_Flintstone's blog

By Fred_Flintstone, history, 7 years ago, In English

Hi codeforces!

I was solving this problem: 100685J - Just Another Disney Problem and I solved it using c++ sort() (submission: 29823860), however I got WA and I was very confused as to why. Later I tried the same but using stable_sort() (submission: 29824442) and surprisingly I got AC. In the statement it says that "for every two of them he likes one of them more than another one" meaning that they have each different "beauty", thus stability is useless. I'd be very grateful if someone could explain me why my first submission failed, it's driving me crazy, I even wrote my first blog because of that!!!

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

I can't view your submissions. Could you upload them somewhere like ideone or pastebin? And possibly also show us the details of the testcase that failed.

What comes to my mind is that you may get WA for exceeding query limit or for asking to compare element with itself.

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

    WA submission: https://pastebin.com/UFQ2MfBB AC submission: https://pastebin.com/ka1x2Jrw Thank you for replying, I haven't realize you can't see my submissions, however I also can't see the testcases.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      It seems to me that I can view gym solutions only if I solved the problem myself.

      I have checked your code on random array and the normal sort version exceeds 10000 queries, while stable_sort one fits in the limit (at least for the testcase I generated). I have uploaded them on ideone. See stable_sort version and sort version. At the bottom they output number of queries.

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

        Finaly, everything is clear! Thank you very much for answering my question))

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        You can also view gym submission if you become a coach(which you are already eligible). Just enable coach mode at the gym section.

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

          I didn't know that. Thanks.

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

Note that preferences could be non-transitive. You should output desired order of all lapms or report Jafar that it doesn't exist.

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

    Yes, I wrote a program that takes care of this, but my AC solution doesn't take care of this

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

      You were lucky/weak tests. std::stable_sort comparator has the same requirements as std::sort. They both require cmp to be transitive. If comparator doesn't match the requirements anything can happen program might crash, it may give wrong result or it may give the result that you expected. Just because you get AC doesn't mean that solution is correct or even a correct program. It might give WA with an input that is not included in test set or even when using different compiler or implementation of standard library.

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

        AC on stable_sort means that the non-transitive case is not present, since the required answer is n zeros in that case and Fred_Flintstone's code doesn't print n zeros in any case. This further means that there is no problem in the comparator being non-transitive and there is no undefined behavior involved.

        So no, AC doesn't mean that code is correct in terms of the statement, but it proves that non-transitivity is not the reason of difference between sort and stable_sort.

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

          a<b<c<a is not transitive but answer isn't 0 0 0. It has 3 answers: abc bca and cab.

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            In the last line [...] or N zeros if such permutation doesn't exist

            E: Oh, I see. You can have non-transitive but have answer. This case is even harder than no answer.