NeverSayNever's blog

Problem :Aurthur and Brackets
By NeverSayNever, 10 years ago, In English

Hello all ,

I have written this code for the problem Aurthor and Brackets link but don't know why i am getting MLE on 9th test case . Can anyone help me please ..

My code .. 

#include 
using namespace std ;


#define MAXN 605 
#define sc(c) scanf("%d",&c)
#define pr(s) printf("%d\n",s) 


int DP[MAXN][MAXN],Pos[MAXN][MAXN],N,L[MAXN],R[MAXN] ;
string ans ;

int solve(int start,int end){
	int &ret = DP[start][end] ;
	if(end < start){
		ret = 1 ;
	} 
	if(end == start){
		if(L[start] > 1){
			ret = 0 ;
		}else{
			ret = 1 ;
			Pos[start][end] = start ;
		}
	}
	if(ret != -1){
		return ret ;
	}
	ret = 0 ;
	for(int i=L[start];i<=R[start];i++){
		if(i%2){
			if(solve(start+1,start+i/2) && solve(start+i/2+1,end)){
				ret = 1 ;
				Pos[start][end] = start+i/2 ;
			}
		}
	}
	return ret ;
}

void construct(int s,int e){

	if(s > e){
		return ;
	}
	ans += '(' ;
	int mid = Pos[s][e] ;
	construct(s+1,mid) ;
	ans += ')' ;
	construct(mid+1,e) ;
	
}
int main(){

	sc(N) ;
	for(int i=1;i<=N;i++){
		sc(L[i]);
		sc(R[i]) ;
	}
	memset(DP,-1,sizeof DP) ;
	if(solve(1,N)){
		construct(1,N) ;
		cout << ans << endl ;	
	}else{	
		printf("IMPOSSIBLE\n") ;
	}
	return 0 ;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You miss line:

return DP[start][end] = ret ;
→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is infinite recursion and access violation because start can become more than N. if start= 500 and i= 500 then start+i/2+1 =750, 750> MAXN.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

submit code like this one:

int solve(int start, int end)
{
   while (isOnStack[start][end])
     ;;;;;;;;;;;;;;//Time Limit
   isOnStack[start][end] = true;

   // add this line before each `return res;`
   isOnStack[start][end] = false
}
→ Reply