Show all threads Hide all threads Show all messages Hide all messages |
WA7 | Parassat Kyzyrkanov | 1574. Mathematicians and brackets | 14 Jul 2023 12:24 | 1 |
WA7 Parassat Kyzyrkanov 14 Jul 2023 12:24 it's the case where count of '(' is greater than ')'. For example: (( or (() |
wa19 | 👑TIMOFEY👑 | 1574. Mathematicians and brackets | 1 Nov 2022 11:07 | 1 |
wa19 👑TIMOFEY👑 1 Nov 2022 11:07 if you use the two-pointer method, then you have problems with the left pointer |
You can use a segment tree for brace balance checking | Levon Oganesyan | 1574. Mathematicians and brackets | 24 Aug 2020 13:08 | 1 |
Tree for minimum is enough. |
Why WA#8? | Chernov Andrey [Vladimir SU] | 1574. Mathematicians and brackets | 24 Aug 2020 00:32 | 5 |
Why WA#8? Chernov Andrey [Vladimir SU] 13 Oct 2007 15:43 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 |
O(n) | jagatsastry | 1574. Mathematicians and brackets | 28 May 2018 18:30 | 7 |
O(n) jagatsastry 24 Nov 2007 13:29 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. Re: O(n) Victor Barinov (TNU) 24 Nov 2007 20:36 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. Re: O(n) Denis Koshman 16 Jul 2008 21:00 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 ? Re: O(n) Oleg Strekalovsky [Vologda SPU] 21 Apr 2009 14:00 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 Re: O(n) Zayakin Andrey[PermSU] 21 Aug 2010 01:33 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). |
WA #33 | Dmitri Belous | 1574. Mathematicians and brackets | 21 Oct 2017 19:40 | 1 |
WA #33 Dmitri Belous 21 Oct 2017 19:40 |
Some tests | Felix_Mate | 1574. Mathematicians and brackets | 5 Dec 2015 17:44 | 1 |
1) (())(())(()) =>3 2) (())(()))))(() =>0 3) )))(()(()))((( =>2 4) )))))((()))))((((((( =>1 5) )()()()()()()()(())( =>9 6) ))(()( =>1 |
If u have WA#13 | Vladimir Plyashkun [USU] | 1574. Mathematicians and brackets | 21 Feb 2014 21:30 | 1 |
try this test: (())() ans: 2 |
O(n) C Accepted 0.031 108 КБ | Sunnat | 1574. Mathematicians and brackets | 13 Nov 2012 18:19 | 1 |
while((ch=getchar())!='\n') { if(ch==')') { ... } else { .... } printf("%i",(!K)*ans); } |
Some tests | MOPDOBOPOT (USU) | 1574. Mathematicians and brackets | 27 Jul 2012 14:16 | 1 |
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 |
I can't understand the exaples | ONU_Latysh | 1574. Mathematicians and brackets | 9 Feb 2012 16:58 | 3 |
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, O(1) memory | vlyubin | 1574. Mathematicians and brackets | 8 Feb 2012 08:05 | 1 |
O(n) time complexity, O(1) memory complexity, the basic idea fits in 15 lines of code (maybe even 10)... |
why 6# | Mamont | 1574. Mathematicians and brackets | 15 Jan 2011 01:14 | 2 |
why 6# Mamont 25 Sep 2009 23:51 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 |
example 2 why 2? | Catalin Pol | 1574. Mathematicians and brackets | 21 Sep 2009 22:59 | 3 |
)()( -> ()() with only one cyclic shift Shift for 1 and shift for 3. i can't understand, can u explain it ? |
What is test #4 (crash on it) and mistake in the code? | virus | 1574. Mathematicians and brackets | 19 Sep 2009 06:24 | 2 |
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. |
WA#14 | r1d1 | 1574. Mathematicians and brackets | 30 Aug 2009 07:39 | 1 |
WA#14 r1d1 30 Aug 2009 07:39 |
Problem 1574 "Mathematicians and brackets" has been rejudged (+) | Sandro (USU) | 1574. Mathematicians and brackets | 5 May 2009 10:10 | 4 |
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. |
To admins! | OpenGL | 1574. Mathematicians and brackets | 1 Feb 2009 11:34 | 3 |
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. |
example 3 why 1? | marius dumitran | 1574. Mathematicians and brackets | 16 Jul 2008 21:01 | 5 |
"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. |
Why WA #11? | prtest | 1574. Mathematicians and brackets | 21 Mar 2008 15:21 | 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; } |