Блог пользователя Tutis

Codechef Biteration #2 BIT2C complexity
Автор Tutis, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

There were atmost 10 operators

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +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.

→ Ответить