Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### .__.'s blog

By .__., history, 10 months 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.

 » 10 months 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.