I was solving this question https://mirror.codeforces.com/contest/1132/problem/F using the editorial's method. ↵
Only difference is, I was using iterative dp rather than recursive dp. ↵
↵
My submission https://mirror.codeforces.com/contest/1132/submission/114519575 ↵
Copy pasted editorial submission https://mirror.codeforces.com/contest/1132/submission/114519641↵
↵
I thought N=500 will give TLE in a O(N^3) solution, however it passed and in less time than the editorial's solution which I think is in O(N^2).↵
↵
Why is it so?↵
Also, is the editorial solution really O(N^2) or am I wrong?↵
What should be the constraints on N to pass a O(N^3) solution as a general rule of thumb?
Only difference is, I was using iterative dp rather than recursive dp. ↵
↵
My submission https://mirror.codeforces.com/contest/1132/submission/114519575 ↵
Copy pasted editorial submission https://mirror.codeforces.com/contest/1132/submission/114519641↵
↵
I thought N=500 will give TLE in a O(N^3) solution, however it passed and in less time than the editorial's solution which I think is in O(N^2).↵
↵
Why is it so?↵
Also, is the editorial solution really O(N^2) or am I wrong?↵
What should be the constraints on N to pass a O(N^3) solution as a general rule of thumb?
