Tutis's blog

Codechef Biteration #2 BIT2C complexity
By Tutis, history, 5 years 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

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

There were atmost 10 operators

→ Reply
»
5 years 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.

→ Reply