aka.Sohieb's blog

Complexity of a Back-tracking solution
By aka.Sohieb, history, 8 years ago, In English

I was trying to solve this problem 27E - Number With The Given Amount Of Divisors, it was said in the editorials that this is a dynamic programming problem,

but i tried to solve it using only back tracking with pruning and i got AC 19429925.

could anyone tell what is the complexity of this solution?! or how to measure the complexity of bt solutions in general?!

thanks in advance :)

  • Vote: I like it
  • +7
  • Vote: I do not like it

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

1) Look at maximal possible depth of recursion for each divisor. They don't go so deep, and this is upper bound.

Some calculations

2) The main speed-up is if (divs <= n) statement because n <= 1000 and therefore divs cannot be greater than nine, which is reached only when we take each of the divisors once.

In general it's very hard to give some good upper bound for backtracking solutions like that and all you can do is to say: "OK, we have these rough estimates that are not so helpful, let's add some optimisations and hope that this'll give us AC".

→ Reply