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!!!
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.
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.
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.
Finaly, everything is clear! Thank you very much for answering my question))
You can also view gym submission if you become a coach(which you are already eligible). Just enable coach mode at the gym section.
I didn't know that. Thanks.
Yes, I wrote a program that takes care of this, but my AC solution doesn't take care of this
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.
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.
a<b<c<a is not transitive but answer isn't 0 0 0. It has 3 answers: abc bca and cab.
E: Oh, I see. You can have non-transitive but have answer. This case is even harder than no answer.