@admin, @likecs, is anything going to happen here?
I do not see how this:
I guess that the problem (and test
data) actually requires that sequence
B should preserve all the relative
sizes for each index pair
can be derived from problem statement… Moreover, I bet, during AUG18 most people who submitted greedy algorithm and got AC - they didn’t question their own solution(they got AC, you know) and just moved on to next problems. It can’t be justification of incomplete problem statement.
I just picked and tested some of AC solutions from top 30 aug18 finishers, all they look wrong and fail on these ‘counterexamples’ - you can easily check it yourselves using following input:
3 2 1 1
4 3 1 2 1 2
and if you get following response from any solution:
it is wrong answer. I don’t think how this whole situation is ok.
Besides to @acmonster and @buda have already pointed to these very flaws in editorial solution. I as well developed greedy algorithm at first during the contest but on first WA(bug in implementation), after more thorough thinking, I discovered similar ‘counterexamples’ myself. So that essentially made problem harder obviously and I ‘postponed’ it(and it turned out I never returned back to it during the rest of contest).
IMHO, either this problem should be removed from every contestant’s score or entire aug18-long should be unrated. Because It feels like bad precedent.
Am I missing any specific rules for such cases?
PS: how many people doe usually verify problem statements and solutions? Looks like this was missed even by ‘tester’.