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: [SPOJ.com - Problem 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
Hey , do you mind telling me how you came to this : res=cnto/2+cntc/2+2*(cnto%2); ?
It will always left like )))))((((( (all closing and then all opening)
You can change half of closing to opening and half of opening to closing. If no of opening/closing is odd then two extra step to change both
)( → () → 2
))(( → ()() → 2
1 Like
thank you , is there anyway i can contact you ?