aryan57's blog

What is the upper bound on N to pass a O(N^3) solution?
By aryan57, history, 4 years ago, In English

I was solving this question https://codeforces.me/contest/1132/problem/F using the editorial's method.
Only difference is, I was using iterative dp rather than recursive dp.

My submission https://codeforces.me/contest/1132/submission/114519575
Copy pasted editorial submission https://codeforces.me/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?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aryan57 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Both of the solutions are O(N^3). The only reason your is faster because it has better constants then recursive solution.

As per my experience N=500 is usually the upper limit for 0(N^3) to work.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

One important thing to notice is that the time limit is 3 secs for that problem, so O(N^3) would easily pass as operations would be less than 3e8

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

It depends a lot from the task. Maybe $$$500$$$ for some recursive dp, maybe $$$5000$$$ for matrix multiplication by modulo $$$2$$$.

My implementation of bit matrix multiplication fits in $$$0.9s$$$ on CF with $$$N = 5000$$$.

→ Reply