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:
2
4 6
3 2 1 1
6 12
4 3 1 2 1 2
and if you get following response from any solution:
1
2
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’.
@acmonster you correct that the current statement doesn’t have the proof for binary search. Even the method for finding k-compressed array will be wrong. The framing of the english statement based on my idea for the question couldn’t be framed correctly by me. As per your comments (which are posted in the editorial), the correct statement should have been:
“B should preserve all the relative sizes for each index pair (i, j) such that |i - j| <= K. In other words, if A[i] < A[j], we should have B[i] < B[j]; if A[i] = A[j], we should have B[i] = B[j], etc”
If this, the editorial is exactly in lines with what you said. I apologise if someone faced the similar situation during the contest.
I implemented a brute force implementation during the contest which was almost same as the basic idea mentioned in the editorial i.e. updating number at given index and finding min in a given range.
I was targeting the first two sub-tasks at that moment.
However, even after spending quite a bit time on it, it gave me selectively wrong answer. I am posting my last solution here. Any help will be appreciated. Thanks.
can anyone explain what’s wrong with following codes? I have checked codes many times but I could not figure out what causes my codes to causing SIGSEGV error.
You might want to change your custom comparator function. Particularly, if (a.first == b.first) . Because of it, your program might have been entering in an infinite loop and due to which you got TLE even for small input. Its behaviour is unpredictable so probably this is the reason you got another WA. Change it and try running it again and see if you can get all your test cases passed. See here for more on this: c++ - Why will std::sort crash if the comparison function is not as operator <? - Stack Overflow
Linear time is taken to traverse for each k, which can be reduced to logarithmic time if we use binary search for maximum k upto which sum<=s hold… thus reducing one N to logN
I came up with this approach as well. What did you do to handle cases like [10, 30, 30, 20, 10], K = 1? Also, the expected complexity for this in my case was O(n^2 * lg(n)), since I was rebuilding my DAG for each K. Did you pass the last subtask with just the optimization on the value of S?
I retained the DAG for each incremental value of k and then just added the newest 0, 1 or 2 dependencies. Maintaining the dependencency list and eliminating the non-essential dependencies was key to getting this solution to work within the time constraints. I may have oversimplified my explanation a bit. For each list element I had what I called a “dependency” list, where the element in question must be greater than any element in the dependency list; and also an equivalency list, where the element in question must be greater than or equal to every element in the equivalency list.
Also note that in the K = 2 case, though we have A[1] = A[3] in the original sequence, we can achieve a smaller sum only if we choose to assign different values to B[1] and B[3]. This shows that the greedy algorithm mentioned in the solution is not optimal.
Hey @acmonster , if we assign B_1 and B_3 different values, then doesn’t point 2 of the question get violated? It says that if there are X elements smaller than A_i in that range, then this must be same for B_i as well.
For your sequence, there is 1 element smaller than A_1 in range [1,3], but 2 elements smaller than B_1 in range [1,3] which I feel make your sequence invalid. Can you please have a look?
