@vivek1_007 According to your third solution, which uses some sort of a BST, can you please provide the proof why the solution will fit in TL supposing all the values of K are distinct ?
why is the code showing TLE…plz explain…link to code --> https://www.codechef.com/viewsolution/13750899
please explain the condition (prefix > prev)in offline solution. What is its significance.
Can anyone tell me any test case for which my code is failing. I have used sorting and binary search and I tried all combinations of test cases I could think of and all are passing. I got a WA for this code - https://www.codechef.com/viewsolution/13767521 . Any help is welcome. Thanks
I have followed 1-based indexing, so you will get 4 as the answer. But, the actual answer is N-i-1, because we are doing an extra iteration. So, you get the answer to be 3. Just updated it.
Can anyone please explain why am i getting TLE in my code.
https://www.codechef.com/viewsolution/13706936
I have used suffix sum instead of prefix.I have tried running many test cases but have not been able to spot the problem. I am getting a WA.
https://www.codechef.com/viewsolution/13765159
Can anyone please point out what’s the problem in my solution?
Are there any special test cases we need to consider for the online solution? We use the same approach in our submission (for Java); we also test with our own test cases and it’s seemed ok. But the submission is still WA. Here is our code: link text. Thank you in advance.
I think observation 2 is incorrect. Consider the following case:
Snake lengths: [1,2,3,6,7,9,10,21]
Queries: [10,21]
In the case of query one, K=10, 4 snakes are killed.
In the case of query two, K=21, none of the snakes is killed.
I used merge sort and binary search in my code, still I was getting Time Limit Exceeded error
My code
@victor_arsenal, I have run your program against my test files and it gives exactly the same output as my own program, which got AC.
wow, strange. When I submitedt it in the contest, it returned WA. Anyway, thank you very much.
@sharmarahul
liscut and lisrem dont get updated in 3rd case since k1>snakelist[i] for every i
hope it helps
@vivek1_007 In Online Solution, could you please explain why you defined prefix sum as
presum[x]=presum[x−1]+(109−l[x])
instead of
presum[x]=presum[x−1]+l[x]
In case of offline solution how to find largest element smaller than K value of current query which we are processing?
As requested, here is a video editorial on this:
Snackdown: SNAKEEAT - Video Editorial
We use the binary search approach here to solve the problem.
Cheers! 