I do think the test cases are weak. Here’s my O(n^3) code that passed. CodeChef: Practical coding for everyone
for me the longest task required .43 seconds while my
[1] is in java.
I tested my code for different inputs and the maximum time it took for 1000 elements and single test
case was 0.16 seconds on my local computer.
[1]: https://www.codechef.com/viewsolution/10802927Mine took just 0.08 sec for the longest task… coded in C… underlying algorithm i devised although is of complexity O(n^3)…
I managed to device one algorithm which in most of the cases could use the pre-calcualted values from the table… so. the inner most for loop comes not often…
However its not fully dynamic programming… but most of the part resembles dynamic programming…
To put it into clearly… its some kind of mixture of dynamic programming with less contribution of backtracking…
According to CodeChef, the longest task required 0.64 seconds.
Thanks for the tip about -O2! However, while my code is now under one second for one test case, when I add five test cases that are the same, it now takes about five seconds to complete, so I think CodeChef did not have a subtask with five test cases and all test cases having N=1000 and same elements each time.
Can’t comment on that. I would suggest you to not run the code on your computer but some IDE like code.hackerearth.com or maybe codechef IDE. This is because the runtime in a PC is determined by various factors, like background processes, etc. After running on an online IDE, note the time. This time will be more close to the real codechef time.
I find many parts of your code a bit weird. For instance, you typedef’d long long to “test_cases”? ._.
That’s a good idea! I ran it on CodeForces and it told me it took 3010 milliseconds against this subtask, so I should’ve TLEd. Yours, however, only took 186 milliseconds.
Interesting. Thanks for sharing!
At first, my algorithm was similar to this (O(N^3) all of the time) and it also did not pass in C. However, I have also seen O(N^3) all of the time solutions pass AC and I think the reason they pass is because they are simpler than most solutions, which means they have a low constant, and because they use the STL, which is very optimized.
@mightymercado No, I did typedef long test_cases and typedef long num so I could differentiate between variables that hold numbers and the test_cases numTestCases variable. I also did typedef long long num_nums because num_nums is the answer type for the number of disjoint intervals. I do this typedef stuff a lot because it makes it easier to keep track of my variables.
How to provide it?>
let me paste it over here
I thik you couldn’t get the underlying algorithm i used by having a look at my code…
but i will paste my code here…
kishu_invain_1 and kishore1… both are same…
actually… when i was participating in july long challenge i was in that account… now as having two accounts is against code of conduct of codechef…i informed it to codechef help desk…
seems that… mine is the fastest solution for this problem 
could be done in just O(n^2) time using dynamic programming…
ofcourse, i used dynamic programming with a little bit of backtracking viz could be removed if we are clever enough…
now i found an algorith of O(n^2) complexity… @noble_mushtak