ZCO12001-Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Editorialist: Adithya Dsilva

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greedy, Stack

PROBLEM:

You are given a well-bracketed sequence. You have to determine:

  1. The maximum nesting depth of the sequence along with the first opening bracket at this depth.
    The nesting depth tells us the maximum number of levels of inner matched brackets enclosed within outer matched brackets. The nesting depth of () and ()()() is 1, the nesting depth of (()) and ()(()) is 2 and the nesting depth of ((())) is 3.
  2. The maximum number of symbols between any pair of matched brackets (inclusive of the outer brackets) and the first position where this occurs – the position of the first opening bracket of this segment.

EXPLANATION:

\ast Outermost brackets refer to brackets which are not enclosed within any other bracket pair.

KEY OBSERVATIONS:

  1. An opening bracket ( at any index increases the depth of the sequence by 1
    Proof

    The depth of a bracket refers to the number of bracket pairs it is enclosed within (including itself, if its a ( bracket). Thus, any ( bracket has a depth of 1 + the depth of its parent bracket, as it’s enclosed within all the brackets its parent is enclosed within (+1 because the current ( bracket also contributes to the depth).

  2. A closing bracket ) at any index decreases the depth of the sequence by 1
    Proof

    Any bracket right after a ) bracket would mean its no longer enclosed within this corresponding bracket pair. But however it still is enclosed within all the brackets the former bracket was enclosed within (since we have come out of only 1 nesting). Thus the depth of this bracket is the depth of the previous matched bracket (which the current bracket is not enclosed within) - 1.

  3. If the depth at any point in the sequence becomes 0, it means that the next bracket is an outermost bracket in the sequence.
    Proof

    If the depth is 0, it means that every ( bracket has been matched by their corresponding ) bracket, implying that the next bracket is an outer-most bracket. This resets the depth and the count of symbols between outermost brackets.

  4. The count of symbols between outermost brackets is greater than the count of symbols between bracket-pairs inside the parent bracket.
    Proof

    An outermost bracket pair includes all the symbols enclosed by brackets nested inside it + 2 (since count of symbols within a bracket pair also includes these outer brackets)

Let us use the above points to find the solution. We are going to start with finding the Max Depth of the sequence.

  • Iterate through the array.
  • Depth refers to the depth of the current bracket in the sequence (remember we are iterating through the array).
  • Using points (1) and (2) from above, Depth++ when we encounter a ( and Depth-- when we encounter a ).
  • We maintain a variable max_Depth, that determines the maximum depth that we have found so far in the iteration.
  • Now, if Depth > max_Depth, we update max_Depth to value of Depth. We also update DepthLoc here to the current index in the iteration. DepthLoc refers to the location of the first bracket achieving this depth.
    Note the > and not \ge, as we want to find the first index that has max_Depth depth. Using the latter would result in returning the last index (if multiple indexes exist) with depth max_Depth.

The max depth is thus max_Depth and the first index is DepthLoc.

Similar approach can be used to determine the Max Count.

  • Iterate through the array.
  • Cnt refers to the count of symbols enclosed within the outermost brackets (or topmost parent brackets) of the current bracket.
  • From point (3) above, we realise that until the depth of a sequence becomes 0, Cnt keeps increasing by 1, for every bracket we iterate through. Thus, if Depth != 0, Cnt++.
    But if Depth == 0, what happens? It means we have crossed the closing bracket of the outermost opening bracket in the sequence, and are beginning with another outermost bracket. Thus Cnt is reset to 0.
  • max_Cnt is determined similarly, as done in determining max_Depth (Using a variable max_Cnt and using the > property).
  • How do we determine the first index, with max_Cnt symbols enclosed within? Simple! Every time we encounter an outermost ( opening bracket (when Depth == 0), we set a variable BracketStartIndex to this index.
    CntLoc can be used to determine the answer, and is updated similarly, like how DepthLoc was updated.

Using the above steps, we can determine the solution!

SOLUTION SNIPPET:

int N; cin >> N;
int Depth = 0, max_Depth = 0, DepthLoc = 0; //Depth variables
int Cnt = 0, max_Cnt = 0, CntLoc = 0;  //Count variables
int BracketStartIndex = 0; //Holds the outermost bracket in which,
						   //the current bracket is contained

for(int x = 1; x <= N; x++){
    if(!Depth){ //If Depth = 0.
        Cnt = 0; //Reset count. Refer point 3 above.
        BracketStartIndex = x; //This bracket is the outermost bracket
        					   //in the sequence to follow!
    }
    
    int i; cin >> i; //Input of current bracket in the sequence 
    
    Cnt++; //Increase count. Any bracket (opening or closing) adds
    	   //to the count of the outermost bracket.
    

    if(i == 1) Depth++;//If opening bracket, depth increases 
    else Depth--; //Else, depth decreases. Refer point 2.

    if(Depth > max_Depth){ //Depth is greater than prev known depth 
        DepthLoc = x; //Set current index as first index with this depth
        max_Depth = Depth; //Update max_depth value
    }
    
    if(Cnt > max_Cnt){ //Count is greater than prev known count
        CntLoc = BracketStartIndex; //Set outermost bracket in sequence 
        					 //as the first bracket with this count
        max_Cnt = Cnt; //Update max_Cnt value
    }
}

cout << max_Depth << DepthLoc << max_Cnt << CntLoc << endl;
//Remember to add spaces between each value in the output!

TIME COMPLEXITY:

Since only one iteration is made through the entire array, the time complexity of the above code is 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 :star_struck: editorial)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

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

23 Likes
2

Awesome, keep making these for recent problems too

1 Like
4

Thank you very much.This was an awesome editorial. Very well explained!

2 Likes
5

How can we find nesting depth by stack implementation ? I am able to do second part(Max brackets) but not the first with stack.

Here is my code( CodeChef: Practical coding for everyone ).

6

Perhaps I am a bit confused about the example. We are given:

20
1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 2 1 2 2

And we are told that the result should be:

2 4 6 9

But since our results are supposed to be 1 based, should not the max nesting depth begin at element 3? Thus shouldn’t the result be 2 3 6 9?

Or am I missing something?

7

Here’s my solution without using stack.

https://www.codechef.com/viewsolution/40496455

8

The bracket sequence when nesting depth is maximum starts at index 3 but we need to report the index where depth is maximum i.e. the most nested inner bracket which is at index 4, thus the answer is 2 4 6 9 and not 2 3 6 9

9

Really very nice editorial.
thank you so much, I really needed this explanation ( was stuck on this problem for more than 3 days)

1 Like
10

Can someone tell what’s wrong in my solution?
Solution Link

11

#include <bits/stdc++.h>
// #include ;
using ll = long long;
using namespace std;

#define endl “\n”

void solveTestCase()
{
ll N;
cin >> N;

char exp[N + 1];
exp[0] = -1;
int temp;

for (int i = 1; i <= N; i++)
{
    cin >> temp;
    if (temp == 1)
        exp[i] = '(';
    else
        exp[i] = ')';
}

std::stack<char> s;

int count = 0;
int count1 = 0;
int pos_count = 0;
int pos_count1 = 0;

int max_depth = 0;
int max_symbol = 0;

int max_depth_p = 0;
int max_symbol_p = 0;

int position = 0;

for (int i = 1; i <= N; i++)
{
    if (exp[i] == '(')
    {
        if (s.empty())
        {
            pos_count1 = i;
        }
        s.push(exp[i]);
        if (s.size() > max_depth_p)
        {
            max_depth_p = s.size();
            position = i;
        }

        count++;
        count1++;
    }

    else
    {
        s.pop();

        if (s.empty())
        {
            max_depth = max(max_depth, count);
            count = 0;
        }
        else
        {
            max_depth = max(max_depth, count);
            count = 1;
        }

        if (s.empty())
        {
            if (count1 > max_symbol)
            {
                max_symbol_p = pos_count1;
            }
            max_symbol = max(max_symbol, count1);
            count1 = 0;
        }
    }
}
cout << max_depth << " " << position << " " << 2 * max_symbol << " " << max_symbol_p << endl;

}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
solveTestCase();

return 0;

}

Can anybody tells what wrong with my solution ??

12

please tell mistake in my code

#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int a[n];
for (int i=0;n>i;++i){
cin>>a[i];
}
int m=0;
int k=0;
int p=0;
for (int i=0;n>i;++i){
if (a[i]==1){
m++;
if(m>k){
k=m;
p=i+1;
}
}
else {
m=0;
}
}
int d=0;
int dd=0;
int s=0;
int l=0;
int y=0;
int kkg=0;
int yy=0;
for (int i=0;n>i;++i){
if (a[i]==1){
if (dd==0){
yy=i+1;
}
d=d+1;
dd=dd+1;
}
else{
d=d-1;
dd=dd+1;
}
y=s;
if(d==0){
s=dd;
d=0;
dd=0;
if (s>y){
l=yy;
kkg=s;
}
}
}
cout<<k<<" “<<p<<” “<<kkg<<” "<<l<<endl;
}