Codeforces Round #288 Problem D - Tanya and Password

Problem Statement:
508D - Tanya and Password

Solution:
An interesting graph problem, with a very insightful idea. This post is more for my self reference, but you are welcome to learn from this too.

Most of us can straight away realize that this is a graph problem, but I think what makes the problem very interesting is the choice of nodes and edges that works for this problem. If we represent each of the 3-letter string as a node, then we are presented with a NP problem of finding a hamiltonian path in the graph. However, if we represent each string as an edge instead, the problem is reduced to finding an eulerian path for which O(N) solutions exist! A very subtle and insightful problem design.