Wednesday, January 28, 2015

Codeforces Round #288 Problem D - Tanya and Password

Problem Statement:

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;

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) {
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);
for(int i=0;i<N;++i){
cin >> edge[i];
int p = f(edge[i]);
int a = p/62;
int b = p%(62*62);
indeg[b]++;
}
source = -1; sink = -1;
bool foundsource = false;
bool foundsink = false;
for(int i=0;i<62*62;++i){
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;
}