Practice

SIMPLE

# 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 editorial)

• 1
• 2
• 3
• 4
• 5

0 voters

Also donâ€™t forget to up-vote this post if you liked it !

22 Likes

Awesome, keep making these for recent problems too

1 Like

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

2 Likes

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( https://www.codechef.com/viewsolution/31999820 ).

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?

Hereâ€™s my solution without using stack.

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

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

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

Can someone tell whatâ€™s wrong in my solution?

#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 ??

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;
}