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.
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? 
Hi @vijju123, the problem statement was updated and it now counts the number of numbers “smaller than or equal to” A[i] and B[i].
@vijju123
Moreover, under the “smaller than” version of the problem that you referred to, we can still construct a counter-example of A = (3, 4, 3, 2, 1), whose 1-compressed sequence is (1, 4, 3, 2, 1) (with sum 11), and whose 2-compressed sequence is (1, 3, 2, 2, 1) (with a smaller sum of 9).
Oh! I missed the statement update. Sorry, and thanks for telling that :). I will forward your concern to @mgch to have a look.
Thanks for letting me know this.
2 Likes
@acmonster ohh sorry!.. {1 1 1 1 1} is 0 compressed sequence…yes you are right, then we cannot use binary search then.