×

# COMPILER - Editorial

Author: Bruno Oliveira
Tester: Sergey Kulik
Editorialist: Lalit Kundu

EASY

# PROBLEM:

Given a bracket sequence, print the length of largest prefix that is a regular bracket sequence.

# EXPLANATION:

A regular bracket sequence is defined as follows:
1. S="" is regular.
2. S="<" + S1 + ">" is regular, if S1 is regular.
3. S=S1 concat S2 is regular, if S1 and S2 are regular.

If S is regular bracket sequence, for any i, number of closing brackets in S[0,i] should not exceed number of opening brackets. Also, if number of opening brackets is equal to number of closing brackets in S[0,i], S[0,i] is a regular bracket sequence.

def check(s):
t=0,ans=0
for i=0 to N-1:
if s[i]=='<': t++;
else:
t--;
//Now, if t=0, means, the string s[0,i] is valid.
if t==0: ans=max(ans,i+1)
else if t<0: break   //string s whole is invalid.
print ans


Complexity: O(N).

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

4★roman28
1.6k71429

 0 Can anyone tell me why this code gives WA?? link text answered 12 May '14, 16:23 1 accept rate: 0% 1 Try this case: 1 <<><>> Output should be 6 (12 May '14, 16:26) Thanks got it!!! :P :P (12 May '14, 16:34)
 0 can i get sometest cases want to figure out where i am getting wrong, comipler of codeshef was flashing WRONG ANSWER answered 12 May '14, 17:39 1 accept rate: 0% 1 You assume, that max input length is 100, why? See the second test case - http://ideone.com/Xxe1sf (answer is not 4 for sure) (12 May '14, 17:59) http://ideone.com/LjfGNp Can you help me where i m getting wrong thank you so much (12 May '14, 19:04) 1 combination of statements char* a[500]; // ... a[m][j]  is strange isn't it? (13 May '14, 04:10) Actually, i used to work on Turbo c++ and it used to work on it. and also i am new to codeshef. But Yes It seems strange, http://ideone.com/ObhNFA, its working now but , time limit exceed, but i m trying to develop better logic. (13 May '14, 12:40)
 0 Can anyone tell me why my this Pascal code was giving wrong ans but same implementation in C++ passed ? answered 12 May '14, 20:49 498●1●7●16 accept rate: 22%
 0 Can somebody please tell me the mistake that I did in this C code: http://ideone.com/HcmfNJ Got a WA.. :'( answered 12 May '14, 23:21 1★masif 1 accept rate: 0% for input 1 <<>  your code returns 2, but correct is 0 http://ideone.com/ALp6VO (13 May '14, 00:21) Thanks a lot! (13 May '14, 01:07) masif1★ Hadn't understood the question clearly.. (13 May '14, 01:08) masif1★
 0 Can anyone post a java implementation for this? answered 13 May '14, 01:44 1★saopayne 1●2 accept rate: 0% Mine is here - http://www.codechef.com/viewsolution/3815607 (13 May '14, 02:54)
 0 Incidentally a similar question was asked on forums a few month's back. answered 13 May '14, 15:12 5★mjbpl 419●2●7 accept rate: 6%
 0 Can anyone tell which case i am leaving ?? Have tried many times but cant get it Accepted. answered 14 May '14, 13:38 6●1 accept rate: 0% 16.9k●49●115●225 Your code is not working on ideone, can you fix it? http://ideone.com/1AnFUY I used your last submission in practice... (14 May '14, 18:15)
 0 Please give a test case where my code fails for compilers and parsers [http://www.codechef.com/viewsolution/3876116] the above link is the code where i had written in java answered 14 May '14, 17:47 1●1 accept rate: 0% You was kind of lucky, your code is not working on ideone I had to change Scanner s = new Scanner(System.in); String str = s.nextLine();  to //Scanner s = new Scanner(System.in); String str = rea.nextLine();  and the code returns 0 4 0 for input from problem statement http://ideone.com/UyDMNu , can you fork it and fix it on ideone? (14 May '14, 18:11)
 0 why im getting WA for this. please help me with this thanks in advance!! http://www.codechef.com/viewsolution/3900904 answered 11 Jun '14, 10:25 1★grvana 152●2●12 accept rate: 5% try this test case <<>.The answer should be 0 , but ur code gives 2. (11 Jun '14, 10:47) @rishab why so coz <<> last two brackets are matching which is the case with the official test case of <>>> which gives 2 as output. plz clarify it :( (11 Jun '14, 11:52) grvana1★ you should output the length of the longest prefix http://en.wikipedia.org/wiki/Substring#Prefix (11 Jun '14, 12:29) thanku got it :P (16 Jun '14, 11:28) grvana1★
 0 what do you mean by ad-hoc? ( one of prerequisites) answered 11 Jun '14, 11:26 156●1●5●11 accept rate: 0% ad hoc means something that is not known in advance (01 Jul '14, 00:26) bug23123★
 0 Can someone provide a solution for the same above problem if the word prefix was removed. I am getting considerable difficulties in doing this version. Eg. for <<<<<<<<> output:2 , for <><><<<<<<<<<> output:4. My problem is that how do we track whether the new contiguous sub sequence extends the previous one or not. As in <<>><<>> output:8 but for <<>><<<>> output:4. Please help! answered 13 Jun '14, 13:51 5★ambarpal 126●3 accept rate: 0%
 0 you can solve the problem using divide and conquer approach with a segment tree. At each node of the segment tree, store the following 5 variables: l -> the maximum positive sum from right end li -> the index at which the maximum sum is achieved r -> the minimum negative sum from left end ri -> the index at which this minimum sum is achieved b -> longest perfect bracket sequence in the interval So, for a node N, the best can be calculated as the maximum of b values of the children, or taking the joint of the r value of the right child and l value of the left child. if mod of l of left child is less than mod of r of right child, then just find the index in the right child where the prefix sum is equal to -l. similar procedure if mod of r is smaller than mod of l. this is work in NlogN. answered 13 Jun '14, 14:32 1.3k●15●65●81 accept rate: 4%
 0 http://www.codechef.com/viewsolution/4150026 .WA checked with all cases discused above .Thanks in advance answered 28 Jun '14, 02:22 3★ajayrfhp 1 accept rate: 0%
 0 For which test case am i getting WA ?. Please someone answer . my subbmission http://www.codechef.com/viewsolution/4167497 Thanks in advance answered 30 Jun '14, 20:52 2★tcmandan 1●1 accept rate: 0%
 0 What must be the output of ><<>> ........Should it be 0 or 4 ?? answered 31 Jan '15, 23:23 191●6●22 accept rate: 14% ANswer for ><<>> should be 0 (01 Feb '15, 00:06) damn_me3★ Why so ?? I can see that I have valid string of length 4 here (01 Feb '15, 18:37)
 0 Why do we need to calculate "ans=max(ans,i+1)"? We can just write "ans=i+1" which will also work. answered 27 Apr '15, 14:41 1 accept rate: 0%
 0 https://www.codechef.com/viewsolution/15906400 i dn know why i am getting WA please anyone suggest some edge cases . answered 20 Oct '17, 20:57 5●2 accept rate: 0%
 0 Can anyone tell me what's wrong with my code ? https://ideone.com/PBWVXW Thanks ! answered 18 Nov '17, 21:41 2★batman69 0 accept rate: 0%
 0 Are these test cases correct ? $./test < test.txt 6 4 0 0 2 6 4$ cat test.txt 7 <><><><<<<>>>> <<>> >< ><> <>< <<>><<<<>>>> ><<>><<<>>>  answered 16 Feb '18, 13:04 1★on2k17nm 1●1 accept rate: 0%
 0 def check(s): t=0,ans=0 for i=0 to N-1: if s[i]=='<': t++; else: t--; //Now, if t=0, means, the string s[0,i] is valid. if t==0: ans=max(ans,i+1) ------> I can see there is no use of max function here as i always more than max every time t==0, so simple ans=i+1 is sufficient. else if t<0: break //string s whole is invalid. print ans answered 16 Feb '18, 17:17 1 accept rate: 0%

# include<string>

using namespace std; typedef unsigned long long int ull;

# define fastscan ios_base::sync_with_stdio(0); cin.tie(NULL);

int main(int argc, char const *argv[]) {

long int t;
cin>>t;

while(t--){
string s;
cin>>s;
ull len=s.length();
stack<char> st;
ull run=0;
for (ull i = 0; i < len; ++i)
{
if(s[i]=='<'){
st.push('<');
run++;
}
else if(s[i]=='>' && !st.empty()){
st.pop();
run++;
}
else{

break;
}

}
cout<<run<<endl;
}

return 0;


}

//Anybody tell me whats wrong in this code..

1
accept rate: 0%

 0 I have implemented this algorithm in Go and tried to run it but getting a time limit exceed error. But the same algorithm I've implimented in Python3 and run it and it accepted. Is Go compiler not well implemented? answered 21 Feb '18, 22:15 2★azizxboy 1 accept rate: 0%
 0 Could anyone please tell me what I am missing in my code? Getting WA. Have attached my own test cases. https://ideone.com/6HQabT answered 17 Mar '18, 22:00 1●1 accept rate: 0%
 0 Can anyone tell me what is wrong with this solution? https://ideone.com/O4w7qo answered 23 May '18, 20:26 0★exorust 1 accept rate: 0%
 0 Can anyone help me with this code. Any suggestion is warmly welcomed,thankyou answered 02 Jun '18, 13:25 1 accept rate: 0%

# define ll long long int

using namespace std;

int main() { ll t; cin>>t; while(t--) { //ll cnt=0; stack <char> s; string s1; cin>>s1; ll n=s1.size(); if(n==1||s1[0]=='>') { cout<<0<<endl; continue;="" }="" int="" i="0;" ll="" cnt="0,res=0;" while(s1[i]!="\\0" )="" {="" if(s1[i]="='&lt;')" {="" s.push(s1[i]);="" cnt++;="" }="" else="" if(s1[i]="='">') { s.pop(); } if(s.empty()) { res+=cnt; cnt=0; } i++; } cout<<res*2<<endl;

}
return 0;


}

what is the prob with my code ?? i have checked most of the testacases all are passing still am getting wa. please help me with testcases

1
accept rate: 0%

 0 Solved it using stack Take a counter c=0 and a summing variable like sum=0 when '<' comes push into stack When '>' comes, check when a pair closes(means top of stack should be '<') increment the counter and after that pop one'<' from stack and check if stack is empty add 2*c to the sum also check if the stack is already empty and '>' comes break your loop of string and print sum Rest is your implementation of code you can check my code link text answered 12 Jun '18, 19:13 1 accept rate: 0%
 0 both author and setter has wrong ans. Check for ">><>" this. answer should be 2. but your solution shows, 0. answered 28 Jun '18, 18:12 1 accept rate: 0%
 0 Can anybody tell me where the mistake is in this code. I'm getting WA https://ideone.com/RDULCj answered 07 Dec '18, 13:03 1 accept rate: 0%
 0 can someone please tell me what's wrong and why it does not get submitted successfully when it gives correct answer to the test case given in the problem. code : https://ideone.com/H6AA9w answered 04 Feb, 22:16 2★yogeshr 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×968
×100
×20

question asked: 12 May '14, 15:09

question was seen: 8,913 times

last updated: 04 Feb, 22:16