__.__'s blog

By __.__, history, 4 weeks ago, In English,

Can someone explain or prove, why calculating all possible values for every interval doesn't get TLE?

I think it should be $$$O(n!)$$$.

My solution.

Problem link.

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

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

There were atmost 10 operators

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Ur complexity isn't $$$O(N!)$$$. Infact if u observe the pattern a bit, you'd find that it's complexity never gets multiplied by factor greater than 4 on increasing N by 1. It's pretty much less than $$$O(4^N)$$$ as well, and it's found out to be roughly O(Catalan Number). For more details, u should check the last part of it's official editorial. Ur solution is the DP solution.