### __.__'s blog

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

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.

• +19

 » 4 weeks ago, # |   -8 There were atmost 10 operators
 » 4 weeks ago, # |   +8 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.