apoorv_01's blog

Help required in a Problem
By apoorv_01, history, 4 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply