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

Автор Ahmad_Elsagheer, история, 8 лет назад, По-английски

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!

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

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

It happened with me too in 2-3 questions in the past,I just memoize with the help of map and my code gets accepted.

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

The first problem actually doesn't need backtracking. You can implement an euler cycle algorithm on the graph where each node is one of the $$$n^m$$$ strings, minus the last digit. So you have a graph with $$$n^{(m-1)}$$$ nodes, each with $$$m$$$ outgoing edges. For example, $$$ (223) \overset{1}{\rightarrow} (231) $$$ is an edge.

Then, each string of the problem has a one-to-one correspondence with an edge. And the "ouroboros" is an euler cycle on this graph. code, similar problem