You are not logged in. Please login at www.codechef.com to post your questions!

×

COMPILER - Editorial

7
2

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

EASY

PREREQUISITES:

AD-HOC

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:

Author's solution
Setter's solution

This question is marked "community wiki".

asked 12 May '14, 15:09

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 31 Jan '15, 23:56

roman28's gravatar image

4★roman28
1.6k71429


Can anyone tell me why this code gives WA?? link text

link

answered 12 May '14, 16:23

zitu_cuet's gravatar image

2★zitu_cuet
1
accept rate: 0%

1

Try this case:

1

<<><>>

Output should be 6

(12 May '14, 16:26) mukit_mkbs3★

Thanks got it!!! :P :P

(12 May '14, 16:34) zitu_cuet2★

can i get sometest cases want to figure out where i am getting wrong, comipler of codeshef was flashing WRONG ANSWER

link

answered 12 May '14, 17:39

gaurav_bhumika's gravatar image

1★gaurav_bhumika
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) betlista ♦♦3★

http://ideone.com/LjfGNp Can you help me where i m getting wrong thank you so much

(12 May '14, 19:04) gaurav_bhumika1★
1

combination of statements

char* a[500];
// ...
a[m][j]

is strange isn't it?

(13 May '14, 04:10) betlista ♦♦3★

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) gaurav_bhumika1★

Can anyone tell me why my this Pascal code was giving wrong ans but same implementation in C++ passed ?

link

answered 12 May '14, 20:49

ashish1610's gravatar image

4★ashish1610
4981716
accept rate: 22%

Can somebody please tell me the mistake that I did in this C code: http://ideone.com/HcmfNJ

Got a WA.. :'(

link

answered 12 May '14, 23:21

masif's gravatar image

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) betlista ♦♦3★

Thanks a lot!

(13 May '14, 01:07) masif1★

Hadn't understood the question clearly..

(13 May '14, 01:08) masif1★

Can anyone post a java implementation for this?

link

answered 13 May '14, 01:44

saopayne's gravatar image

1★saopayne
12
accept rate: 0%

(13 May '14, 02:54) betlista ♦♦3★

Incidentally a similar question was asked on forums a few month's back.

link

answered 13 May '14, 15:12

mjbpl's gravatar image

5★mjbpl
41927
accept rate: 6%

Can anyone tell which case i am leaving ?? Have tried many times but cant get it Accepted.

edit: http://www.codechef.com/viewsolution/3904670

link

answered 14 May '14, 13:38

subham_kumar's gravatar image

3★subham_kumar
61
accept rate: 0%

edited 14 May '14, 18:13

betlista's gravatar image

3★betlista ♦♦
16.9k49115225

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) betlista ♦♦3★

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

link

answered 14 May '14, 17:47

srinivasam's gravatar image

2★srinivasam
11
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) betlista ♦♦3★

why im getting WA for this. please help me with this thanks in advance!! http://www.codechef.com/viewsolution/3900904

link

answered 11 Jun '14, 10:25

grvana's gravatar image

1★grvana
152212
accept rate: 5%

try this test case <<>.The answer should be 0 , but ur code gives 2.

(11 Jun '14, 10:47) rishabh19942★

@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) betlista ♦♦3★

thanku got it :P

(16 Jun '14, 11:28) grvana1★

what do you mean by ad-hoc? ( one of prerequisites)

link

answered 11 Jun '14, 11:26

brobear1995's gravatar image

2★brobear1995
1561511
accept rate: 0%

ad hoc means something that is not known in advance

(01 Jul '14, 00:26) bug23123★

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!

link

answered 13 Jun '14, 13:51

ambarpal's gravatar image

5★ambarpal
1263
accept rate: 0%

@ambarpal:

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.

link

answered 13 Jun '14, 14:32

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 13 Jun '14, 14:37

http://www.codechef.com/viewsolution/4150026 .WA checked with all cases discused above .Thanks in advance

link

answered 28 Jun '14, 02:22

ajayrfhp's gravatar image

3★ajayrfhp
1
accept rate: 0%

For which test case am i getting WA ?. Please someone answer . my subbmission http://www.codechef.com/viewsolution/4167497 Thanks in advance

link

answered 30 Jun '14, 20:52

tcmandan's gravatar image

2★tcmandan
11
accept rate: 0%

edited 30 Jun '14, 23:46

What must be the output of ><<>> ........Should it be 0 or 4 ??

link

answered 31 Jan '15, 23:23

nickzuck_007's gravatar image

3★nickzuck_007
191622
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) nickzuck_0073★

Why do we need to calculate "ans=max(ans,i+1)"? We can just write "ans=i+1" which will also work.

link

answered 27 Apr '15, 14:41

newjeetu93's gravatar image

3★newjeetu93
1
accept rate: 0%

edited 27 Apr '15, 14:41

Answer is hidden as author is suspended. Click here to view.

answered 02 May '15, 12:06

bangga's gravatar image

0★bangga
(suspended)
accept rate: 0%

https://www.codechef.com/viewsolution/15906400 i dn know why i am getting WA please anyone suggest some edge cases .

link

answered 20 Oct '17, 20:57

shashank3112's gravatar image

3★shashank3112
52
accept rate: 0%

Can anyone tell me what's wrong with my code ?

https://ideone.com/PBWVXW

Thanks !

link

answered 18 Nov '17, 21:41

batman69's gravatar image

2★batman69
0
accept rate: 0%

Are these test cases correct ?

$ ./test < test.txt
6
4
0
0
2
6
4
$ cat test.txt
7
<><><><<<<>>>>
<<>>
><
><>
<><
<<>><<<<>>>>
><<>><<<>>>
link

answered 16 Feb '18, 13:04

on2k17nm's gravatar image

1★on2k17nm
11
accept rate: 0%

edited 16 Feb '18, 13:06

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

link

answered 16 Feb '18, 17:17

srihari_p's gravatar image

2★srihari_p
1
accept rate: 0%

include<iostream>

include<bits stdc++.h="">

include<string>

using namespace std; typedef unsigned long long int ull;

define F first

define S second

define nl printf("\n");

define pb push_back

define mp make_pair

define f(i,a,b) for(int i=a;i<b;i++)

define MOD 1000000007

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..

link

answered 20 Feb '18, 20:50

nirajsingh's gravatar image

2★nirajsingh
1
accept rate: 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?

link

answered 21 Feb '18, 22:15

azizxboy's gravatar image

2★azizxboy
1
accept rate: 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

link

answered 17 Mar '18, 22:00

itachi_157's gravatar image

2★itachi_157
11
accept rate: 0%

edited 17 Mar '18, 22:00

Can anyone tell me what is wrong with this solution? https://ideone.com/O4w7qo

link

answered 23 May '18, 20:26

exorust's gravatar image

0★exorust
1
accept rate: 0%

Can anyone help me with this code. Any suggestion is warmly welcomed,thankyou

link

answered 02 Jun '18, 13:25

kshreyans_1's gravatar image

2★kshreyans_1
1
accept rate: 0%

include<bits stdc++.h="">

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


link

answered 12 Jun '18, 00:15

baby_licious's gravatar image

2★baby_licious
1
accept rate: 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

link

answered 12 Jun '18, 19:13

verma_ankit484's gravatar image

4★verma_ankit484
1
accept rate: 0%

both author and setter has wrong ans. Check for ">><>" this. answer should be 2. but your solution shows, 0.

link

answered 28 Jun '18, 18:12

chirag1247's gravatar image

0★chirag1247
1
accept rate: 0%

Can anybody tell me where the mistake is in this code. I'm getting WA https://ideone.com/RDULCj

link

answered 07 Dec '18, 13:03

pratmambo's gravatar image

2★pratmambo
1
accept rate: 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

link

answered 04 Feb, 22:16

yogeshr's gravatar image

2★yogeshr
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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