Show us some solution please!
Why would you ever swap the order of [Author,Tester] => [Tester,Author]?
Can someone tell what is the complexity of my code , I feel it is the same as required and gives TLE.
Solution
Nice joke about “easily finish under 10 seconds”.
Here’s author’s code from editorial, submitted in practice: link
can someone tell me if the Tester2 is based on knuth optimization?
Try to solve it using a Divide and Conquer approach, this is another kind of dynamic programming optimization that runs in O(KNlogN), and here’s my solution that runs in 6.90 s
PD: You can read about it here
http://www.codechef.com/viewplaintext/7298688
I coded the solution after going through editorial(but it is top-down approach).I could pass first sub-task only.Can someone figure out what optimization i have to do to my code to pass other sub-tasks.I think I have taken care of trick mention in editorial.Plz help !!
added tester’s and author’s solutions
same here.
Got it , precedence can make you cry! . Morover use memset over simple loop to fasten up your code!!
Bad constant?
Hm… that’s sad actually if you get the correct, but can not implement it properly. Where could I improve?
Try to submit NKlog(A) code from editorial, you’ll be surprised
What exactly is the problem with the NKlogA solution from the editorial?
On the testing server, all test files were passing under 8 seconds. Author’s solution was only for first 2 subtasks. it was wrongly uploaded here. the correct solutions are up now. Try submitting tester2’s solution.
Tried tester1, it works 8.3 on maxtest. Far from TL*0.5 I agree that getting TL because of bad implementation why AC is possible is a contestant’s fault, but that’s definitely not “easily finish” Looking at other comments in this topic - I am not the only one who thinks this way.
And what was the point about “try tester2’s”? It is complitely different solution, based on Knuth optimization; it has nothing to do with NKlogA.
Hello, sorry for reviving this old thread. I was trying this question using divide and conquer optimization but it fails one test case in the largest and I am confused on how to try to further optimize it… My code is pretty straight forward and clean, please have a look at it. Is there something I can try to optimize my code. Or should I go with Knuth optimization as mentioned?
Thank you
Can anyone help in debugging the code? TLE !!
https://www.codechef.com/viewsolution/90228825
Here I find another solution with a similar code but pass-
https://www.codechef.com/viewsolution/86862907