tenshi_kanade's blog

508D — Tanya and Password
By tenshi_kanade, 10 years ago, In English

I just want to make public my fascination towards this problem and recommend a tutorial to all the users. I loved solving this problem. It's a truly beautiful Eulerian Path problem in disguise.

It also helped me refresh my knowledge on the algorithm. I learned Eulerian Paths/Tours like 10 years ago when I first started at the USACO Gateway and then I rarely ever used it again. Now I googled it to refresh my memory, but I couldn't come upon any good implementations out there. There are a few, but all of them seem either overly complicated or inefficient. No other algorithm I found out there beats the beautiful recursive algorithm presented at the USACO Gateway.

For those not registered at USACO, you can view the tutorial here: Eulerian Paths/Tours Tutorial

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

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

A question: would you be able to solve the problem during the contest without the knowledge of Eulerian Paths ?

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

    I certainly don't know if there's another solution to the problem...

    But if you can come up with the idea of Eulerian Path during the contest all by yourself without knowing it beforehand, then yes, you could solve it.

    → Reply