What is the upper bound on N to pass a O(N^3) solution?

Revision en2, by aryan57, 2021-04-29 13:11:18

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English aryan57 2021-04-29 13:11:18 7
en1 English aryan57 2021-04-29 13:10:47 717 Initial revision (published)