Complexity analysis for backtracking problems with pruning

Правка en1, от Ahmad_Elsagheer, 2016-06-27 19:48:18

Hello,

Sometimes I encounter problems and can't come up with a solution better than backtracking. Even my backtracking solution, I can't analyze its time complexity. So, I try implementing it, see the worst case and find my intuition is true. Here are two of them, if someone can help me to prove why it should pass the time limit.

Problem 1: UVa 10506 — The Ouroboros problem. link, solution

Problem 2: UVa 165 — Stamps. link, solution

Thanks!

Теги backtracking, pruning, complexity

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Ahmad_Elsagheer 2016-06-27 19:48:18 946 Initial revision (published)