I have gone through the editorial for the problem at ZCO12003 Problem - CodeChef but after understanding the logic behind the solution when I finally came to the implementation part I was simply stuck, really stuck. I couldn’t handle out of bound cases and things like that, so I couldn’t implement the idea given in the editorial (even thought the editorial is really good, it is my implementation skill that isn’t so good). Can anyone provide their code for this problem, it is highly appreciated if the code is well commented (makes it easier for a beginner like me to understand the stuff)?
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
ll solve(){
int n;
cin>>n;
int seq[n];
for(int i=0;i<n;i++){
int a;
cin>>seq[i];
switch(seq[i]){
//I'm actually changing the numbers to use bitwise operations easily
//to significantly shorten the code
//the ones digit shows the type, and the twos digit tells me whether it is opening or closing
case 1:
seq[i]=0;
break;
case 2:
seq[i]=2;
break;
case 3:
seq[i]=1;
break;
case 4:
seq[i]=3;
break;
}
}
vector<int> depths;
//stores the depths of the unclosed brackets
//eg,
//(([[[()(( will be 2,3,2. The already paired brackets are removed.
int type;
//The type of bracket needed for a switch to increase alternation
int ans1=1;
for(int i=0;i<n;i++){
if(depths.size()==0){
type=(seq[i]^1);//We need the opposite of the starting bracket
depths.pb(1);//We have just one open bracket
continue;
}
if(seq[i]==type){//We found it
type^=1; //Now we need the other type
depths.pb(1);//We add this to our depths
ans1=max(ans1,(int)depths.size());//Check if this is the largest
continue;
}
if(seq[i]==(type^3)){//If it's closing the bracket that is currently open
depths[depths.size()-1]--;//remove one from it as it found a pair
if(depths[depths.size()-1]==0){//All are over so go back to the previous depth
depths.pop_back();
type^=1;//We also need the other one again
}
continue;
}
if(seq[i]==((type^1))){//Another one that is not needed is opened
depths[depths.size()-1]++;
}
}
int last[2]={0};//The last time the bracket of type i was opened at 0 depth
int depth[2]={0};//The current depth of type i
int maxdist[2]={0};//The answer for type i
//It will always be at a 0 depth because the brackets at depth 1 will be strictly
//inside a bracket of depth 0.
for(int i=0;i<n;i++){
if(seq[i]&2){//If it's a closing bracket
if(--depth[seq[i]&1]==0){//if the depth for this type became 0
maxdist[seq[i]&1]=max(maxdist[seq[i]&1],i-last[seq[i]&1]+1);
//Check if this one is the largest
}
}
else{
if(depth[seq[i]]==0){//If it's opening at depth=0
last[seq[i]]=i;//We set this as the opening bracket
}
++depth[seq[i]];
}
}
cout<<ans1<<" "<<maxdist[0]<<" "<<maxdist[1]<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
2 Likes
Thank you 