Help with spoj question- https://www.spoj.com/problems/ANARC09A/

I am getting wrong answer for this submission:

Code
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define endl "\n"
#define INF 1e9+7
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define all(x)	x.begin(),x.end()
#define fileopen freopen("input.txt", "rt", stdin);
#define fileclose freopen("output.txt", "wt", stdout);
#define Fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define hash visited.max_load_factor(0.25);visited.reserve(512)

using namespace std;

int main()
{
    Fio;
    int ptr=0;
    while(1)
    {
        ptr++;
        string str;
        cin>>str;
        if(str[0]=='-')
        {
            break;
        }

        vll st;
        ll stable=0;
        int cnt=0;

        for(int i=0;i<str.size();i++)
        {
            if(str[i]=='{')
            {
                st.pb('{');
                cnt--;
            }
            else
            {
                cnt++;
                if(!st.empty())
                {
                    st.pop_back();
                    stable++;

                } 
                       
            }
            

        }
        cout<<ptr<<". "<<abs(cnt/2)+(str.size()-2*stable-abs(cnt))<<endl;


    }
    

    
}

Question: [https://www.spoj.com/problems/ANARC09A/]

Logic: I am initially finding the total number of stable pairs and also keeping track of cnt which tells me about the braces which are yet to be balanced. if cnt is negative or positive, its straightforward. if its 0, then I am applying (size-2*stablepairs-cnt). This gives me number of }{ basically.

Can anyone help me with the corner case I am missing or flaw in the logic?

Your sol will not be visible if you share link.

Code
#include <bits/stdc++.h>
using namespace std;

#define lld long long int 

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=0;
    while(1)
    {
        t++;
        char s[2001];
        scanf("%s",&s);
        if(s[0]=='-')
        break;
        else
        {
            stack <char> stk;
            stk.push(s[0]);
            for(int i=1;s[i]!='\0';i++)
            {
                if(s[i]=='}')
                {
                    if(stk.size()>0&&stk.top()=='{')
                    stk.pop();
                    else
                    stk.push('}');
                }
                else
                stk.push('{');
            }
            int res=0,cnto=0,cntc=0;
            while(stk.size()!=0)
            {
                char ch=stk.top();
                stk.pop();
                if(ch=='{')
                cnto++;
                else
                cntc++;
            }
            res=cnto/2+cntc/2+2*(cnto%2);
            cout<<t<<". "<<res<<"\n";
        }
    }
}
1 Like

I am unable to see your solution with that link. I am pasting my solution here, in case it is of any use.
The stack β€˜st’ here stores the β€˜{’ character, and pops it out when the stack is non empty and the input character is β€˜}’. In case the character is β€˜}’ and the stack is empty, I stored the number of such β€˜}’ in the variable β€˜unParent’. Finally if the stack is non empty this means there are some β€˜{’ characters at the end of the string s which could not find a β€˜}’ to partner with, so if they are even, the can partner among themselves in n/2 operations, else if they are odd, the odd one can make paur with one of the unParent’ed β€˜}’. Same goes for the β€˜}’, which do not have a partnering β€˜{’ left in the string.

Code
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

int solve(string s){
	
	stack<char> st;
	
	int unParent=0;
	
	int ops=0;

	for(int i=0; i<s.size(); i++){
		
		if(s[i]=='{'){
			st.push('{');
		}
		else{
			if(st.size()!=0){
				st.pop();
			}
			else{
				unParent++;
			}
		}
	}
	
	
	if(unParent!=0){
		
		ops = ops + (unParent/2);
		
		if(unParent%2){
			ops+=2;
		}
		
	}

	if(!st.empty()){
		int sz = st.size();
		ops = ops + (sz/2);
	}
	return ops;
}

int main(){

    int t=1;
    
    while(1){
    	string s;
    	cin >> s;
    	if(s[0]=='-'){
    		break;
		}
		cout << t<<". " << solve(s) << endl;
		t++;
	}
}
1 Like

i have updated my code. please check it out. thanks

I have done something similar. I have updated the code, check it out.

For }}{{ it should be 2. Your code is giving 4. See my code

1 Like

ohh right, will check it out. thanks