COMPILER - Editorial

editorial
, , , ,
1

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

7 Likes
2

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

3

Try this case:

1

<<><>>

Output should be 6

1 Like
4

Thanks got it!!! :stuck_out_tongue: :stuck_out_tongue:

5

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

6

You assume, that max input length is 100, why?

See the second test case - http://ideone.com/Xxe1sf (answer is not 4 for sure)

1 Like
7


Can you help me where i m getting wrong
thank you so much

8

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

9

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

Got a WA… :’(

10

for input

1
<<>

your code returns 2, but correct is 0

11

Thanks a lot!

12

Hadn’t understood the question clearly…

13

Can anyone post a java implementation for this?

14

Mine is here - http://www.codechef.com/viewsolution/3815607

15

combination of statements

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

is strange isn’t it?

1 Like
16

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.

17

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

18

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

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

19

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

20

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?