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

Help required in a Problem
Автор apoorv_01, история, 4 года назад, По-английски

I recently solved this problem using a simple backtracking algorithm. I thought it should give me TLE as the time complexity goes upto O(9^m) where max value of m = 1000, but it gave me AC. Can anyone explain me why?

Problem My Code

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

Many states are not calculated because they are invalid. You may write a program giving random test data to show how many times "recurse" runs for.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The time complexity is hard to say. You may consider it is O(9^m*a), while a is a very small number, like 10^(-900). I think it very difficult to make it TLE.

→ Ответить