can someone explain the k-compress part of the question…thanks in advance
“for each valid i, if there are exactly X numbers smaller than or equal to Ai in the subsequence Amax(1,i−K),…,Amin(N,i+K), then there must be exactly X numbers smaller than or equal to Bi in the subsequence Bmax(1,i−K),…,Bmin(N,i+K).”
Managed to optimize my brute-force approach and solve it without segment tree.
Time and space complexity remains the same as that of this editorial.
Binary search was the key in solving this problem.
My solution: https://www.codechef.com/viewsolution/19673140
2 Likes
I was able to solve all test cases during the competition with a completely different approach. The problem reminded me of software dependencies and I started looking at directed acyclic graphs and found that they fit this application fairly well. I sorted the list elements into a topological order where repeated elements were all given the same value. This is definitely similar to your grouping step in the editorial solution. For k = 0, each compressed element is given a value of 1. I then iterated through the values of k from 1 to N. For each incremental value of k, and each list element, there are at most 2 new “dependencies.” For example, at k = 0, each element must be greater than or equal to at most 0 elements. At k = 1, each element must be greater than or equal to at most 2 elements. At k = 2, each element must be greater than or equal to at most 4 elements, etc. … After each iteration of k, I found the max of the dependencies and incremented or equivalated as necessary. I did have an issue with solving the test cases for the largest values of N within the time constraints, but this was solved by recognizing that if S > ((N * (N + 1) / 2 ), then the result should be N + 1. That was my basic approach, but there was some optimization code to remove unnecessary dependencies, ones which would be resolved by other dependencies with a higher topological order. This was definitely a tough one, the comments section was full of frustrated and angry people, I was among them for a long time.
1 Like
I think that the solution is incorrect, since the cost of the K-compressed sequence is not monotonic in K. Here is a simple counter-example.
Consider sequence A = (2, 1, 2, 3, 4). One can verify that one of its 1-compressed sequences is (2, 1, 2, 3, 4) itself, which has a cost of 12. However, one of its 2-compressed sequence is (3, 1, 2, 2, 3), which, in fact, has a lower cost of 11.
3 Likes
@acmonster I didn’t get what you are trying to say…we want to find the k compressed sequence with lowest sum so 1-compressed sequence with minimum sum for {2 1 2 3 4} is {1 1 1 1 1} with minimum sum of 5 while 2 compressed sequence with minimum sum is {3 1 2 2 3} with sum 11. Why are u comparing any random k compressed sequence?
Hi @byomkeshbakshy, you might want to check that the 1-compressed sequence with minimum sum for (2, 1, 2, 3, 4) is (2, 1, 2, 3, 4) itself, not (1, 1, 1, 1, 1). This shows that the minimum sum of K-compressed sequence is not necessarily non-decreasing in K.
@likecs Please help me with this solution… What can be test cases It may be failing upon?
https://www.codechef.com/viewsolution/19759987
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