FWIW, I also thought binary search would be useful here upon seeing the problem, but then wrote a brute-force solver and found counterexamples. Oneās intuition can be misleading.
In the editorial, it is written to check whether the ranges of the identical elements coincide with each other, but it does not give the criteria for coinciding ranges. Example: For a = [2, 3, 4, 3] and k = 1, the range of the 3 at index 2(assuming 1 based indexing) is [1, 3] and that for the 3 at index 4 is [3, 4]. But both of these can be mapped to different values. So, to check whether the ranges for 2 indices i and j (i < j) for a given value of k overlap or not, we need to check j - i <= k, and not i + k <= j - k.
In the example above, the optimal compression for k = 2 is [1, 2, 3, 1], while using the wrong condition it comes out to be [1, 2, 3, 2]. My solution with the wrong condition passed all but the last test file.
I doesnāt look to me like the described greedy solution works. I also had the intuition that something like that would work (e.g. āall equal values in A that are within each otherās range will be the same in Bā) but I managed to disprove all of these intuitions that I had.
For example, for A = [1, 1, 2, 2] and K = 1, the setterās solution computes B = [1, 1, 2, 2], but in fact, B = [2, 1, 1, 1] with a smaller sum of 5.
So I wonder if someone can explain a correct algorithm to compute the K-compressed sequence in O(nlgn) time.
2 Likes
@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:
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.
Can anyone please help me to debug my code of this problem 
My code- link
I am getting WA on the last 3 test cases.
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.
Hereās my submission: CodeChef: Practical coding for everyone
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.
link to my solution - https://www.codechef.com/viewsolution/19877450
Can anyone please explain the fault in my codeā¦I have given this question a lot of time still no improvment ;
@likecs could you help??
Can anybody plz tell why I am getting wrong answer in the very last test case ???
I am stuck at it for too long !!
Any help will be appreciated ā¦
Thanks in advance !
Please tell me your B array for the input
1
20 2
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6
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
Google more to find out about it.
at what value of k
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
1 Like
Iāve also observed this but couldnāt come out with a solution during the contestā¦ sure itās another way to solve this problem.
I Changed, But didnāt work 
Also, Thank you for your time which you give it.
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?
Oh yeah, sorry, for k=9.
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.
This approach mandates that k is iterated through from 1 to N, so the binary search approach isnāt possible here.