Codeforces Round #288 Problem E - Arthur and Brackets

Problem Statement:
508E - Arthur and Brackets

Solution:
The problem statement in my opinion is not exactly clear. It should have been stated that the "corresponding closing bracket" must be the first available closing bracket closest to the open bracket, i.e. the a pair of brackets should not be intertwining with other pair of bracket, as demonstrated below:
( [ ) ]      /* not a valid bracketing */

With that the problem is more manageable. Let D[i][j] is set to 1 if we can build the required bracketing using i-th to j-th constraints. Then we have:
D[i][j] = OR of all k [ D[i+1][i+k] AND D[i+k+1][j] ].



This means that, if we focus on opening bracket i, we have choices of placing its closing bracket in \([l[i], r[i]]\). between this opening and closing bracket, there must be k number of pairs of opening and closing bracket. Therefore, we need to check whether D[i+1][i+k] AND D[i+k+1][j] is 1 (i.e. whether we can build the required structure using (i+1)-th to (i+k)-th constraints, place it in between opening and closing bracket of i, and then start checking whether we can build the required structure using (i+k+1)-th to j-th bracket). The whole algorithm will run in \(O(N^3)\).

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

int N;
int D[603][603];
int L[603], R[603];
int path[603][603];

void print_ans(int i, int j) {
    if(i>j)return;
    if(i==j){
        printf("()");
    } else {
        int m = i+path[i][j];
        printf("(");
        print_ans(i+1,m);
        printf(")");
        print_ans(m+1,j);
    }
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d%d",&L[i],&R[i]);
    }
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            D[i][j] = 0;
            path[i][j] = -1;
        }
    }
    for(int i=0;i<N;++i){
        D[i][i] = (L[i]==1);
        D[i+1][i] = 1;
    }
    for(int len=1;len<N;++len){
        for(int i=0;i<N;++i){
            int j = i+len;
            if(i+len >= N) break;
            D[i][j] = 0;
            for(int m=L[i];m<=R[i];++m){
                if(!(m%2))continue;
                int k = (m-1)/2;
                if(i+k+1>j+1)continue;
                int cur = D[i+1][i+k] & D[i+k+1][j];
                if(cur){
                    D[i][j] = cur;
                    path[i][j] = k;
                    break;
                }
            }
        }
    }
    if(D[0][N-1]) {
        print_ans(0,N-1);
        printf("\n");
    } else {
        printf("IMPOSSIBLE\n");
    }
    return 0;
}