getting TLE using binary search and sorting,but i havent store the query result in array and check again for previous encountered query in array thats why i am getting tle?
What do you mean by online and offline solutions?
2 Likes
can you provide some examples of offline solution ?
Hi, I tried similar approach. Tried some test cases all passed.
Can you give me some test case for which my solution is failing?
https://www.codechef.com/viewsolution/13767521
@jeetu86044 As mentioned in my comment Mo’s algorithm almost always involve offline solutions.
Question – DQUERY
Explanation for mo’s algorithm and a bit of offline queries is given in this blog.
2 Likes
@grajesh you sorting the array repetively for each test in loop for(p=0;p<q;p++).Instead sort the array outside the loop only one time .Hence your solution has time complexity O(q*(nlogn+n))
well i guess u missed to mention that if there are repeatative elements , for eg consider a series of 11 13 13 13 14 and query being 14 then binary search will retutn the mid 13 instaed of the 13 b4 14, so u need to take care of that according to your soln…
hen binary search again on the prefix difference sum array (which will give the number of snakes to be fed to snakes in [prev+1, cur] to make their length at least K) in the region [1, cur]
can someone explain me more clearly this point
What’s wrong with my python code…Any kind of a help is most welcomed
https://www.codechef.com/viewsolution/13774246
@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 ?
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 - CodeChef: Practical coding for everyone . Any help is welcome. Thanks
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.
@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]