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.

So to solve this problem, we need to represent each 2-letter string as a node, and for each 3-letter string s given, we connect node s[0],s[1] to node s[1],s[2], hence in essence each s acts as an edge. With this our goal is to find an eulerian path, and one of the O(N) technique is by using two stacks, consider the following pseudo code:

(This algorithm is called Hiezholzer's Algorithm)

Let S, T be stacks. Let A[u] be the adjacency information of node u. A[u].pop() will return the edge adjacent to u currently on top of stack A[u]. euler_path(u): while A[u] is not empty: e = A[u].pop() T.push(e) euler_path(e.v) while T is not empty: f = T.pop() S.push(f) if f == e: break Output: S will represent an eulerian path.

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <string> using namespace std; vector<vector<pair<int,int> > > adj; int indeg[62*62]; int vis[200005]; string edge[200005]; vector<int> S, T; int N; int source = 0, sink = 0; int f(string s) { int ret = 0; for(int i=0;i<3;++i){ ret *= 62; if(s[i] < 'A') { ret += s[i] -'0'; } else if(s[i]<'a') { ret += s[i]-'A'+10; } else { ret += s[i]-'a'+36; } } return ret; } void dfs(int u) { while(!adj[u].empty()){ int v = adj[u].back().first; int e = adj[u].back().second; adj[u].pop_back(); T.push_back(e); vis[e] = 1; dfs(v); while(!T.empty()){ S.push_back(T.back()); T.pop_back(); if(S.back() == e) break; } } } int main() { scanf("%d",&N); adj = vector<vector<pair<int,int> > >(62*62+3); for(int i=0;i<N;++i){ cin >> edge[i]; int p = f(edge[i]); int a = p/62; int b = p%(62*62); adj[a].push_back(make_pair(b, i)); indeg[b]++; } source = -1; sink = -1; bool foundsource = false; bool foundsink = false; for(int i=0;i<62*62;++i){ int outdeg = adj[i].size(); if(outdeg > 0 && !foundsource){ source = i; } if(outdeg - indeg[i] == 1) { if(foundsource) { printf("NO\n"); return 0; } source = i; foundsource = true; } else if(indeg[i] - outdeg == 1) { if(foundsink) { printf("NO\n"); return 0; } sink = i; foundsink = true; } else if(indeg[i] - outdeg != 0) { printf("NO\n"); return 0; } } if(foundsource != foundsink) { printf("NO\n"); return 0; } dfs(source); for(int i=0;i<N;++i){ if(!vis[i]) { printf("NO\n"); return 0; } } printf("YES\n"); bool flag = false; while(!S.empty()){ if(!flag){ printf("%s", edge[S.back()].c_str()); flag = true; } else { printf("%c", edge[S.back()][2]); } S.pop_back(); } printf("\n"); return 0; }