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.



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.
            

With that we can solve the problem:

#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;
}