Codeforces Rockethon 2015 Problem D1/D2 - Constrained Tree

Problem Statement:
513D2 - Constrained Tree

Solution:
Can a problem be interesting and yet frustrating? The answer turns out to be a loud and painful Yes.. Spent 8 hours just to get this right :/

Btw the editorial to this problem is sufficiently comprehensible hence I would suggest you to read the official editorial instead of this one if you haven't done so. Otherwise, you might benefit from this :)

You are supposed to construct a tree out of a given set of relationships between the nodes on the tree, such that the pre-order and in-order labelling of the nodes agree on each other. That is a pretty confusing semantic in my opinion. And they have recursive definition.



Pre-order labelling is the labelling you get if you start recursing from the top of the tree using DFS (hence we get root-left-right ordering), while in-order labelling is done by doing a recursive printing as follows: Let T be current subtree; printTree(T.left); print(T.root); printTree(T.right); (hence we have left-root-right ordering).

To solve the problem, we need a recursion, and we need to keep track of just the right states. Let i be the root node of the current subtree S being considered, and let v be the target vertex that we want to include in this subtree S. In the beginning we will start from state (1, n). Let Construct(i, v) be the procedure that build S, using minimum possible nodes, and in the end of the procedure, returns the index of the node with highest value.

For each node i, let L[i] be the ranges of vertices that must be placed on the left side of i, and R[i] be the ranges of vertices that must be placed on the right side of i. If L[i] and R[i] is both empty, we can recurse on any side of S without problem. Otherwise, if one of them is not empty, we can recurse on the non-empty side, hence we does not violate the constraints.

Now let's focus on the case where both of them are non-empty, we must have L[i] = [left[0], left[1]] while R[i] = [right[0], right[1]]. Firstly we construct the left side of the tree by calling Construct(i+1, left[0]), which will return m, the highest node in that tree. We must have m < right[0], or otherwise we have violated some constraints. Next we recurse on the right hand side Construct(m+1, max(right[1], v)). Notice the max(right[1],v), since we want to include all the nodes required for the current tree.

The base case will be when i and v is equal, and i has both L[i] and R[i] empty, in which we will have i is the sole node of the tree.

Here is an implementation:

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <iostream>
using namespace std;


int R[1000003][2], to_left[1000003], to_right[1000003], L[1000003][2];
vector<int> S;
int N, C;
bool ok;

// build a subtree, rooted at i and contains vertex to
// returns the largest element in the subtree
int build(int i, int to) {
    if(!ok)return -1;
    
    if(!to_right[i] && to_left[i]){
        int m = build(i+1, max(to, L[i][1]));
        S.push_back(i);
        return m;
    }
    if(!to_left[i] && to_right[i]){
        S.push_back(i);
        return build(i+1, max(to,R[i][1]));
    }
    if(!to_left[i] && !to_right[i]) {
        if(i==to){
            S.push_back(i);
            return i;
        }
        S.push_back(i);
        return build(i+1, to);
    }
    if(to_left[i] && to_right[i]){
        int m = build(i+1, L[i][1]);
        if(m>=R[i][0]){
            ok = false;
            return -1;
        }
        S.push_back(i);
        int n = build(m+1, max(R[i][1], to));
        return n;
    }
}

int main(){
    int u,v;
    string type;
    scanf("%d%d",&N,&C);
    for(int i=1;i<=N;++i){
        R[i][0] = N+1;
        L[i][0] = N+1;
        R[i][1] = 0;
        L[i][1] = 0;
    }
    ok = true;
    for(int i=0;i<C;++i){
        scanf("%d%d",&u,&v);
        cin>>type;
        if(v <= u) {
            ok = false;
            break;
        }
        if(type == "RIGHT"){
            R[u][0] = min(R[u][0],v);
            R[u][1] = max(R[u][1],v);
            to_right[u] = 1;
        }
        else {
            L[u][0] = min(L[u][0],v);
            L[u][1] = max(L[u][1],v);
            to_left[u] = 1;
        }
    }
    build(1, N);
    if(ok){
        for(int i=0;i<N;++i){
            if(i!=0)printf(" ");
            printf("%d",S[i]);
        }
        printf("\n");
    } else {
        printf("IMPOSSIBLE\n");
    }
    return 0;
}