ZCO12003-Editorial

infinitepro · September 7, 2019, 9:37am

PROBLEM LINK:

Practice

Editorialist: Adithya Dsilva

DIFFICULTY:

SIMPLE

PREREQUISITES:

Ad-hoc, Greedy, Stack

PROBLEM:

You are given a well-bracketed sequence (consisting of () or [] brackets). You have to determine:

The maximum alternating depth of the sequence.
The alternating depth tells us the maximum number of times we switch between the two types of brackets when we have inner matched brackets enclosed within outer matched brackets. The alternating depth of ()[[[]]] is 1, alternating depth of ()([]) is 2, alternating depth of ([[()]]) is 3.
The maximum number of symbols between any pair of matched brackets (inclusive of the outer brackets) of type ().
The maximum number of symbols between any pair of matched brackets (inclusive of the outer brackets) of type [].

EXPLANATION:

Let us first start by finding the maximum number of symbols between any pair of matched brackets of type () and [].

Let x and y\space (y > x) be the indices of an opening bracket and its corresponding closing bracket in the array. The count of symbols between this bracket pair is

y - x + 1

which is inclusive of the outer brackets. The above equation can be verified trivially.

Thus, we can iterate through all the bracket pairs of type () and [], and find the maximum count of symbols over all the bracket pairs of a particular type.

But how are we going to find the index y of the closing bracket corresponding to a opening bracket at x? We use stacks here!
A nice article on stacks has been linked in the pre-requisites, which newbies ought to read before proceeding!

We are going to have 2 stacks RBrac and SBrac, where RBrac is for () type brackets, and SBrac is for [] type brackets. What do these stacks store exactly?

For every opening bracket that we encounter, we push the current index (aka the index of this opening bracket) into the respective stack.

On encountering a closing bracket, it’s corresponding opening bracket is the topmost element present in the respective stack at this point.

Proof by Reason

Notice that the topmost element in the stack is the most recent opening bracket that we have encountered (or I can say processed).
Since the sequence is well-bracketed, inner brackets have to be matched before the outer brackets are matched.

Thus, applying the properties of a well-bracketed sequence, we know that the topmost element in a stack corresponds to the closing bracket that we encounter.

Since the stack stores the index of the opening brackets, we have the value of x in this bracket pair. Also, the index of this closing bracket is y. Using this info, we can now determine the symbol count between this bracket pair, and subsequently find the maximum over all bracket pairs (of the same type ofc ).

A simple code for the above explanation would be as follows:

int maxR = 0; //maximum symbol count between () brackets
int maxS = 0; //maximum symbol count between [] brackets
stack<int> RBrac, SBrac; //Stacks for the opening brackets index

for(int x = 1; x <= N; x++){ //1 based indexing
	//Let the bracket at index x be `i`
	switch(i){ //Check which type of bracket it is
        case 1: //It is a ( bracket
            RBrac.push(x);
        case 2: //It is a ) bracket
            maxR = max(maxR, x - RBrac.top() + 1); //Eq as above
            RBrac.pop(); //Remove this bracket as it is matched!
        case 3: //It is a [ bracket
            SBrac.push(x);
        case 4: //It is a ] bracket
            maxS = max(maxS, x - SBrac.top() + 1); //Eq as above
            SBrac.pop();            
	} 
}
//Break has been ommited to keep the code clean!
//The maximum's are therefore maxR and maxS respectively

Now lets come back to finding the maximum alternating depth of the sequence. We proceed by using stack’s again!

Let us start by redefining the alternating depth of an opening bracket in a sequence.

The alternating depth tells us the maximum number of times we switch between the two types of brackets when we have inner matched brackets enclosed within outer matched brackets.

Let the alternating depth of an opening bracket be the number of times we switched between the two types of opening brackets (which enclose this opening bracket) before reaching this bracket. The alternating depth of an outermost bracket (a bracket without parents) is 1. A detailed explanation is given below.

Example

Let the bracket sequence be ([([](()))])

The alternating depth of the opening brackets in their order of their appearance is \{1,2,3,4,3,3\}.
I’m going to illustrate the alternating depth of the 5^{th} opening bracket in the above sequence. The nesting structure starting from the outermost bracket is as follows:

(\to[\to(\to(

where the last bracket above corresponds to the 5^{th} opening bracket. Since we switch from ( to [ to ( , the number of switches is 3. Thus the depth of the 5^{th} opening bracket is 3.

Thus, the alternating depth of a sequence is the maximum over the alternating depth of all opening brackets in the sequence!

If the parent of an opening bracket is of the alternate type, then there is a switch of bracket while moving from the parent to the current bracket. Thus the depth of this bracket is 1 more than the depth of the parent bracket.
If the parent of an opening bracket is of the same type, then the depth of this bracket is the same as the depth of the parent bracket.

An explanation (by example) has been given above!

Now, coming to the implementation. We make a stack AltDepth, where the topmost element corresponds to the depth of the most recent unmatched, opening bracket. The depth of an outermost bracket is 1 (bare case).

Now while iterating through the input, if we encounter an opening bracket, we check if the parent of this bracket is of the alternate type.

YES : The depth of this bracket is 1 more than the depth of it’s parent bracket. The depth of the parent bracket is stored at the top of AltDepth, since the topmost value in AltDepth represents the most recent unmatched bracket aka the parent bracket of the current sequence. Thus we add AltDepth.top() + 1 into the stack, which would then represent the depth of the most recent unmatched bracket.
NO : The depth of this bracket is the same as the depth of it’s parent bracket. Thus we add AltDepth.top() into the stack, which now represents the depth of the most recent unmatched bracket sequence.

On encountering a closing bracket, we simply remove the topmost element from AltDepth, as this bracket is no longer unmatched (so this bracket pair is no longer the parent of any other preceding brackets).

Thus, the maximum value that was present in the stack AltDepth determines the maximum alternating depth of the sequence!

Wait! How do we determine the parent bracket’s type? Simple. We check stacks RBrac and SBrac for the most recent opening bracket, which would be the parent bracket of the current bracket we are processing.

CODE SNIPPET:

int maxR = 0; //maximum symbol count between () brackets
int maxS = 0; //maximum symbol count between [] brackets
int maxDepth = 0; //maximum alternating depth of the sequence 
stack<int> RBrac, SBrac; //Stacks for the opening brackets index
stack<int> AltDepth; //Stack for the alt depth of the sequence

for(int x = 1; x <= N; x++){ //1 based indexing
	//Let the bracket at index x be `i`
	switch(i){ //Check which type of bracket it is
        case 1: //It is a ( bracket
            
            //Check parent bracket type by checking the type of the most 
            //recent opening bracket
            if(RBrac.top() < SBrac.top()) 
                AltDepth.push(AltDepth.top() + 1);
            else 
        		AltDepth.push(AltDepth.top());
            RBrac.push(x);
        case 2: //It is a ) bracket
            
            maxR = max(maxR, x - RBrac.top() + 1); //Eq as above
            RBrac.pop(); //Remove this bracket as it is matched!
            AltDepth.pop(); //Remove this depth as it is matched!
        case 3: //It is a [ bracket
            
			//Check parent bracket type by checking the type of the most 
            //recent opening bracket
            if(SBrac.top() < RBrac.top()) 
                AltDepth.push(AltDepth.top() + 1);
            else 
        		AltDepth.push(AltDepth.top());
            SBrac.push(x);
        case 4: //It is a ] bracket
            
            maxS = max(maxS, x - SBrac.top() + 1); //Eq as above
            SBrac.pop(); //Remove this bracket as it is matched!
            AltDepth.pop(); //Remove this depth as it is matched!
	}
    maxDepth = max(maxDepth, AltDepth.top());//Max depth in sequence
}

cout << maxDepth << maxR << maxS << endl;
//Remember to add spaces between the ouptut!
//Break has been ommited to keep the code clean!

TIME COMPLEXITY:

Since only one iteration is made through the entire array, the time complexity of the above code is

O(N)

MEMORY COMPLEXITY:

RBrac and SBrac combined can have at most \frac{N}{2} values (since there are exactly \frac{N}{2} opening brackets). AltDepth can also have at most \frac{N}{2} values in it. Thus the overall memory complexity is

O(\frac{N}{2} + \frac{N}{2}) = O(N)

SOLUTIONS:

Editorialists solution can be found here.

Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!

Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome editorial)

1
2
3
4
5

0 voters

Also don’t forget to up-vote this post if you liked it !

anon55659401 · September 8, 2019, 12:53pm

Your editorials are awesome as always

But I have a question for you : - Why do you put so much effort to write the ZCO editorials ? I mean there will be some reason ?

infinitepro · September 8, 2019, 1:43pm

Because I’ve been given the task of writing editorials for ZCO/INOI.

vijju123 · September 8, 2019, 2:15pm

Wow, really?

O.M.G.

Such pros