COMPILER - Editorial

ad-hoc
compiler
easy
editorial
may14

#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*=='<': 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


#2

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


#3

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


#4

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


#5

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

Got a WA… :’(


#6

Can anyone post a java implementation for this?


#7

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


#8

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

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


#9

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


#10

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


#11

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


#12

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!


#13

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


#14

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


#15

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


#16

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


#17

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


#18

Terima kasih dan salam kenal.
codechef Link

code Link


#19

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


#20

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

Thanks !