it's the case where count of '(' is greater than ')'. For example: (( or (() if you use the two-pointer method, then you have problems with the left pointer Tree for minimum is enough. Why WA#8? I algo had WA8. This test helped me: ())()))((()( Answer: 1 No, it is bad test if WA8, this test help me ()()())()( +1 Thank you! Edited by author 17.11.2011 20:40 I used an O(n*n) method and got TLE#9. Does anyone know of any O(n) method. I actually checked every cyclic shift to see if it is a valid expression. Of course there are exists O(n) algo. You just must to find 1 valid cyclic shift. And then check balance in it. Number of points with balance == 0 will be the answer to ploblem. There is another method - check number of points where minimal disballance is nonnegative (after checking that overall ballance is zero). What do you mean when saying "point" ?? What is "point" here ? Could you please give a clear description of this method ? I think,that your algo get TLE on new tests. Because, it's not diffucult crate test,where your program will do o(N^2). Exampel - 49999 times '(', 50000 times ')', 1 time ')'. My AC program find shift, not finding right bracket expression (it's O(N^2)), but by an other method ( n steps). Good luck =) Edited by author 21.04.2009 21:12 There is exist O(n*log(n)) solution. If the sequence s is of length n, consider the sequence ss, which will have length 2n. Now define l_i as the number of '(' in the first i characters of ss and r_i as the number of ')' in the first i characters of ss. Let d_i=l_i-r_i. We want to know if there are any numbers smaller than d_i in d_i, ... , d_{n+i}. Interval trees will give you O(n log n) algorithm, but there are even simpler algorithms that will give you an O(n) algorithm (Hint: d_i is continuous). 1) (())(())(()) =>3 2) (())(()))))(() =>0 3) )))(()(()))((( =>2 4) )))))((()))))((((((( =>1 5) )()()()()()()()(())( =>9 6) ))(()( =>1 try this test: (())() ans: 2 while((ch=getchar())!='\n') { if(ch==')') { ... } else { .... } printf("%i",(!K)*ans); } Finally, I found the way to solve it in O(n) (needs about 4 full string-checks). In journey to this solution i tried to imagine that i'm cutting brackets like '()'. And watching what I can get by cutting all this pieces. Looking on new sequence I understood what I need to shift to get right bracket-sequence. Here are some tests that helped me: )))(()(( ans: 1 (()(())) ans: 1 ())( ans: 1 ))(())())((()( ans: 1 Edited by author 27.07.2012 14:19 Are the answers in exanples the only solutions or are there maultiple ones!? What we do is we repeatedly move the last bracket to the start of the list. If we have brackets 1234 then we test 1234,4123,3412,2341. On example 1 it is: )(() , ))(( , ())( , (()) ; from which only the last option is OK. Thus the answer is one. Hope that helps. But, why in example №2 answer 2? sequence: )()( 1234 -> 4123 )()( ()() Answer must be 1. O(n) time complexity, O(1) memory complexity, the basic idea fits in 15 lines of code (maybe even 10)... I made testing on computer and all tests have pass Ok Please, say me what is 6 test? test with incorrect sequence, for example "((" must return 0 )()( -> ()() with only one cyclic shift Shift for 1 and shift for 3. i can't understand, can u explain it ? I have crash (access violation) on test #4. I can't imagine where this code can give a crash! Could you explain me where this stupid mistake is? #include<iostream> using namespace std; struct Node { char ch; Node *next; Node *prev; } *first=0,*last=0; int n=0; void add(char c) { ++n; if(!last) { first=new Node; first->ch=c; first->next=0; first->prev=0; last=first; } else { last->next=new Node; last->next->ch=c; last->next->next=0; last->next->prev=last; last=last->next; } } void cleanup() { while(first) { Node *p=first; first=first->next; delete p; } first=last=0; } void move() { Node *p=last; last=last->prev; last->next=0; first->prev=p; p->next=first; p->prev=0; first=p; } bool check_correct() { int balance=0; Node *p=first; while(p) { if(p->ch=='(') ++balance; else --balance; if(balance<0) return 0; p=p->next; } if(!balance) return 1; return 0; } int count() { int cnt=0,balance=0; Node *p=first; while(p) { if(p->ch=='(') ++balance; else --balance; if(!balance) ++cnt; p=p->next; } return cnt; } int main() { char c; while(cin.get(c)) { if((c=='(')||(c==')')) add(c); else break; } int i; bool b=0; for(i=0;i<n;++i) { b=check_correct(); if(b) break; move(); } if(b) cout<<count(); else cout<<0; cleanup(); return 0; } Well, I've rewritten this algorithm using STL, now I have TLE #11, but it's slow STL. But the main thing I found is that this algorithm is totally correct. So I just have to find a mistake in the code. Where it could be? On my tests everything works perfectly. Help, please! Edited by author 28.01.2009 20:22 Checking balance consumes O(n) time, you run it n times. So, your solution is O(n^2) -- of course, it's TL. New tricky test was added. All AC submits were rejudged. 31 authors lost AC. Thanks to Fyodor Menshikov, author of this test. The new test data contain input that doesn't end the line with a '\n'. My former submission got TLE only because it ends when getchar() == '\n', and I got AC again by changing it to gets() only. The test doesn't end with new line indeed. My rejudged solution (from AC to WA) used fgets() and failed just because of that. On this problem testset is wrong! This program got TLE#1: #include <cstdio> void main() { char c; while((c=getchar()!=EOF)) { while(c!='('&&c!=')'); } } I think that one end of line is not prohibited after brackets. Yes, there should be end of line in the end of each test. () 1 ?? () ->0 ??? "A string a is a cyclic shift of a string b if a and b have the same lengths and a consists of some _(possibly empty)_ suffix from b followed by a prefix from b." I dont understand ur explaining . Can U explain it(cyclic shift) with some examples "possibly empty" has been emphasised. so every expression is a cyclic shift of itself. () leads to two cyclic shifts: () and )(. Only () is valid bracket sequence, so the answer is 1. RT. #include<iostream> #include<string.h> using namespace std; int start,l,flag=1; char str[100010]; void init() { cin>>str; l=strlen(str); } int check(int a,int &now) { int i=a+1,count=1; if(str[a]==')') return 0; for(;i!=a;i++) { if(i==l) i=0; if(i==a) break; if(str[i]=='(') count++;else count--; if(count<0) {now=i+1;return 0;} } return 1; } void find() { int i,now; if(check(0,now)) {start=0;return;} for(i=1;i<l;i++) { if(str[i]=='(' && str[i-1]==')') if(check(i,now)) {start=i;return;}else i=now; } if(i==l) flag=0;return; } void solve() { int i,count=1,ans=0; if(flag==0) {cout<<0<<endl;return;} for(i=start+1;i!=start;i++) { if(i==l) i=0; if(i==start) break; if(str[i]=='(') count++;else count--; if(count==0) ans++; } cout<<ans<<endl; } int main() { init(); find(); solve(); return 0; } |
|