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.

()(
Answer: 0.

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

O(n) time complexity, O(1) memory complexity, the basic idea fits in 15 lines of code (maybe even 10)...

Are the answers in exanples the only solutions or are there maultiple ones!?

I made testing on computer and all tests have pass Ok
Please, say me what is 6 test?

New tricky test was added. All AC submits were rejudged. 31 authors lost AC. Thanks to Fyodor Menshikov, author of this test.

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

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;
}

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.

Why WA#8?

)()(  ->  ()() with only one cyclic shift

() 1

??
() ->0 ???