Auto comment: topic has been updated by FelixArg (previous revision, new revision, compare).

Автокомментарий: текст был обновлен пользователем FelixArg (предыдущая версия, новая версия, сравнить).

handled cheaters very well :)

Handled cheaters very well :>

377959479

did anyone do B like this?

for(int i = 1; i <= n; ++i) {
        cout << i << " ";
    }
    for(int i = 1; i <= n; ++i) {
        cout << i << " " << i << " ";
    }
    for(int i = n - 1; i >= 1; --i) {
        cout << i << " ";
    }
    cout << n;

Holy smokes E is beautiful but also I have no idea how I could have seen that myself :(

Its me or C was too hard??

Is this right for F? It took me about an hour on D and I couldn't submit my code of F in time at last because the page got stuck while loading :(

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{int f,e;inline bool operator<(const Node &other) const{return e>other.e;}};
int n,a,b,l,c,u[19],v[19],z[150009],d[150009];
ll p;
vector<Node> g[150009];
map<int,int> m;
unordered_map<int,int> M;
priority_queue<Node> q;
bool vst[150009];
inline void f(int x){for(int i=2;i*i<=x;++i) if(!(x%i)){int o=0;while(!(x%i)) x/=i,++o;m[i]=max(m[i],o);}if(x>1) m[x]=max(m[x],1);}
void dfs(int i,ll x){
	if(i==l){++c,z[c]=x;return;}
	for(int j=0;j<=v[i];++j){dfs(i+1,x);x*=u[i];if(x>n) break;}
}
void dfs2(int i,int o,ll x,int r){
	if(r==l){if(x!=o) g[i].push_back((Node){M[x],max((int)x,z[i])/o}),g[M[x]].push_back((Node){i,max((int)x,z[i])/o});return;}
	while(1){dfs2(i,o,x,r+1);x*=u[r];if(x>n||p%x) break;}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>a>>b,f(a),f(b),p=a*b;
	for(auto x:m) u[l]=x.first,v[l]=x.second,++l;
	dfs(0,1);
	for(int i=1;i<=c;++i) M[z[i]]=i;
	a=M[a],b=M[b];
	for(int i=1;i<=c;++i){
		for(int j=0;j<l;++j) if(z[i]%u[j]==0){
			int o=z[i]/u[j],O=M[o];
			g[i].push_back((Node){O,u[j]}),g[O].push_back((Node){i,u[j]});
			dfs2(i,o,o,0);
		}
	}
	memset(d,0x3f,sizeof(d)),q.push((Node){a,0});
	while(!q.empty()){
		Node f=q.top();
		q.pop();
		if(vst[f.f]) continue;
		vst[f.f]=1,d[f.f]=f.e;
		for(Node &x:g[f.f]) if(!vst[x.f]) q.push((Node){x.f,x.e+f.e});
	}
	cout<<d[b];
	return 0;
}//a,b,c,d>=2 => max(ab,cd)>=max(a,c)+max(b,d)，否则不妨 ab>=cd,a>=c，则 b<=d，于是 ab<a+d => d>a(b-1) => cd>=2d>a*2(b-1)>=ab 矛盾

I don't know if I'm right, but another construction that works for B is: a b a b b a a b

Where distances from a, are:

2, 3, 1

And from b:

2, 1, 3

And maybe you have more settings if you figure out to swap the orders by keeping the "coherence" between the two interlinked distances. I'm not sure about that, though.

got this solution for B by mistake

    ll n;
    cin >> n;
    vector<ll> ans;
    for(ll i=1;i<=n;i++){
        ans.push_back(i);
    }
    for(ll i=1;i<=n;i++){
        ans.push_back(i);
    }
    for(ll i=2;i<=n;i++){
        ans.push_back(i);
    }
    ans.push_back(1);
    for(ll i=1;i<=n;i++){
        ans.push_back(i);
    }
    for(auto i: ans){
      cout<<i<<" ";
    }
    cout << endl;

;)

I have a question for the editorial of F.

My solution for B was

If n is even then: 1, 1, 2, 2, 3, 3, ..., n-1, n -1, n, n, 1, 2, 1, 2, 3, 4, 3, 4, ..., n-1, n, n-1, n

Else if n is odd then: n, 1, 1, 2, 2, 3, 3, ..., n-1, n-1, n, n, 1, 2, 1, 2, 3, 4, 3, 4, ..., n-2, n-1, n-2, n-1, n

But this dont work for n = 2 so i checked if n == 2 then output 1, 2, 1, 1, 2, 2, 1, 2

What I did for B was simple :

n, 1, 1, 2, 2 ... n-1, n-1, n, n, 1, 2, 3, ...n-1, n, 1, 2, 3, ... n-1

Worked like a charm!

PS: Dont hack me :(

I was only able to solve A and B

can someone explain me how to actually think for C problem

I hate horrible implement of D.

In D There is no need to prove that u can say NO if number of problematic index is >4 U can take a big number like 1000 and solution will still pass eg:

https://codeforces.me/contest/2233/submission/378004270

I have done problem C using Graphs. Lets represent each bracket as a node and draw undirected edge between '(' and ')'. It is always good to remove the node with max degree. By doing it k times we find the answer.

I rewrite my code 4 times for D :sob:

Another construction for B: Hardcode for n= 2,3 Rest of cases: Identity permutation, Identity permutation, Shifted identity permutation to the right, Shifted identity permutation to the left.

There is another way of showing the claim of E2 (also solve the whole problem):

For any positive integer sequence $$$A$$$ of length $$$N$$$ without duplicate, $$$A$$$ would be a permutation of $$$[1, 2, \ldots, N]$$$ if and only if $$$\sum\limits_{i = 1}^N A_i = \frac{N(N+1)}{2}$$$.

So the problem is reduced to finding the number of ways to permute strings so the sum is $$$\frac{N(N+1)}{2}$$$. Since this is the lower bound of the sum over any positive integer sequence without duplicate, we can relax the condition into minimize the sum and check if it is $$$\frac{N(N+1)}{2}$$$.

The only way to minimize it is to sort strings by frequency of $$$1$$$ bits. Which deduce the final solution in the editorial and also prove why we can permute strings with same number of $$$1$$$ bits arbitrarily.

377950426

My soln for B was eg. n = 3

"1 2 3" "1 2 3" "2 3 1" <-- (rotate by 1) "1 2 3"

My solution to B: Start with n=2 case, For n>2 — append all numbers 3...n to the right of each 1.

if (n == 2)
    {
        cout << "1 2 2 1 1 2 1 2\n";
        return;
    }
    else
    {
        string a = "1 ";
        for (int i = 3; i <= n; i++)
        {
            a += to_string(i) + " ";
        }
        string res = "";
        res = a + "2 2 " + a + a + "2 " + a + "2";
        cout << res << '\n';
    }

With a careful implementation, I solved F 378020300 using Dijkstra’s algorithm in $$$O(d(ab)^2)$$$.

Can it be hacked?

I thought C was DP? was anyone able to define a DP state which works in O(n^2)

Unfortunately I missed some of the cool observations for E2 and overkilled, my solution is follows:

Submission: 377991037

• Consider DP approach, where DP[d][mask] is number of ways of filling $$$d^{th}$$$ string whereas the previous strings are already filled. $$$mask$$$ denotes the strings which are already used up.

• One observation, if N is $$$2^{x} - 1$$$ , and with no duplicates, we can permute the strings in any order, Reason: re-arranging the strings in any order can never produce a number > N. So all numbers [1,N] occur.

Idea:

• First lets fix the top string, (0000...1111) we need to verify that the count of 0s, is correct here.

• Since any rearrangement of other strings would automatically handle (0000) guys, now the problem reduces to rearrangining the remaining strings such that those starting at (1111) are correctly handled. Similary to traversing a binary trie top down.

This is some text.

// this is code
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<set>
#include <queue>
#include<utility>
#define int  long long
using namespace std;
void solve() {
   int n;
   cin >> n;
   vector<int> ans(n*4);
   vector<int> dummy(n);
   for(int i = 0 ; i < n ; i++){
         ans[i] = i+1;
         dummy[i] = i+1;
   }
   for(int i = 0 ; i < n ; i++){
    ans[n+i] = dummy[i];
   }
   for(int i = 0 ; i < n ; i++){
    ans[3*n+i] = dummy[i];
   }
   reverse(dummy.begin(),dummy.end());
   reverse(dummy.begin()+1,dummy.end());
   for(int i = 0 ; i < n ; i++){
    ans[2*n+i] = dummy[i];
   }
   for(int i = 0 ; i < 4*n ; i++) cout << ans[i] <<" ";
   cout << endl;
}


signed main(){
    int t;
    cin >> t;
    while (t--) {
       solve();
    }   
    return 0;
}

an interesting one

In D, checking if the array is arranged correctly after a swap can be done in constant time

ll delta = 0;

// p1 and p2 are the positions to be swapped
if (p1 > 0 && a[p1] != a[p1 - 1]) delta++;
if (p1 < n - 1 && a[p1] != a[p1 + 1]) delta++;
if (p2 > 0 && a[p2] != a[p2 - 1]) delta++;
if (p2 < n - 1 && a[p2] != a[p2 + 1]) delta++;

swap(a[p1], a[p2]);

if (p1 > 0 && a[p1] != a[p1 - 1]) delta--;
if (p1 < n - 1 && a[p1] != a[p1 + 1]) delta--;
if (p2 > 0 && a[p2] != a[p2 - 1]) delta--;
if (p2 < n - 1 && a[p2] != a[p2 + 1]) delta--;

swap(a[p1], a[p2]);

// unique is the number of unique values in the array
// seg is the number of segments with only one value in the array
if (seg - delta == unique) {
    cout << "YES\n";
    return;
}

In the $$$O(n)$$$ editorial solution for problem C:

A closing bracket remains unmatched only if, at the moment it is processed, there were more closing brackets than opening brackets before it.

However, for a string such as )))(), the 5th character gets matched although there are more closing brackets that opening brackets proceeding it. I think what is true, instead, is that a closing bracket at index $$$i$$$ is not matched iff

We can then use that to prove that the total number of unmatched closing brackets is:

What's the definition of pref_open and suff_close in C? I didn't really understand.

During the open hacking phase, all non-mine submissions show Source: N/A, and clicking Copy also gives N/A. I can view my own submissions normally. I also tested old problem submissions, recent contest submissions, and different users. Same result: other users’ source is always N/A. The announcement says we should have access to copy any solution during the 12-hour hacking phase.

why question F is so vague and unclear ??

tried B for almost 1.5 hour after solving A, wasted 3 pages of my notebook to get an idea, failed horribly, how can i improve in these kinds of problems?

the shuffle method in B is really interesting — but how are we sure that it works within the given time limit? does there exist a way to calculate the time complexity of functions like these, averaged over a long number of trials, for example?

also, are all permutations generated by shuffle equally likely? how would the time taken change in case the function is biased towards certain permutations? sorry if the questions seem very noob

For problem B this worked for me. but no exact idea why. initially i was thinking of rotating by 1, then by n-1 but that didn't work so i thought may be rotate them by increasing value might work. but no idea how this actually works for all cases. how to prove that this will work always?

void solve() {
    ll n;
    cin >> n;
    vll a(4*n);
    vll v(n);
    for(int i = 1; i <= n; ++i) v[i-1] = i;
    ll k = 0, cnt = 1;
    for(int i = 0; i < 4; ++i){
        for(int j = 0; j < n; ++j) a[k++] = v[j];
        rotate(v.begin(), v.begin() + (cnt % n), v.end());
        cnt++;
    }
    print(a);
}

What is the rating system in educational rounds , why rating is not updated yet.

are ratings not updated yet??

Educational Codeforces Round 191 (Rated for Div. 2)

Straightforward solution for C

(The ones in the comments look daunting for newbies like me)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();

            String str = sc.next();
            char[] s = str.toCharArray();

            int bal = 0;
            int min_bal = 0;
            int min_ind = -1;

            for (int i = 0; i < n; i++) {
                if(s[i]=='(') bal++;
                else bal--;

                if (min_bal>bal) {
                    min_bal=bal;
                    min_ind=i;
                }
            }

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i <= min_ind; i++) {
                if(k>0 && s[i]=='('){
                    sb.append(1);
                    k--;
                }
                else
                    sb.append(0);
            }

            for (int i = min_ind+1; i < n; i++) {
                if(k>0 && s[i]==')'){
                    sb.append(1);
                    k--;
                }
                else
                    sb.append(0);
            }

            System.out.println(sb);
        }
    }
}

E is beautiful.

for C, can sb tell me where im wrong?

we map +1 to '(' and -1 to ')' and keep a prefix sum, now let e be, the last value of the prefix sum, and m be. the minimum value of the prefixes

now its obvious that max(e, 0) is the number of unmatched '('.

and we can say that the number of unmatched ')' is m because when we hit the minimum its obvious that we have atleast m, ')' unmatched on that prefix and therefor in the whole array, and if at any point there could be more unmatched, m would be lower, so could we say:

cost = n — |min(m, 0)| — max(e, 0)

now we can say that removing a '(' before m decreases both which in the end haas no effect and just wastes k. same reasoning for ')'.

so we try to remove as many ')' as possible, after m. my sol(WA'ed): 377987973

my reasoning seems logical but fails miserably in practice, and could i fix it somehow

Now that open hacking is over, I'll post my alternate solutions since I had an irrational fear of getting hacked

For A I used binary search because I was too lazy to derive the formula for using AI lol: 377924003

Now here's my alternate solution for C:

number of transition in F can be further reduced to around $$$10^7$$$ by observing either $$$p$$$ or $$$q$$$ is prime in optimal choices, since if

holds, then

So any pairing of two composite number can be decomposed into two "smaller" pairing without worsening the cost.

I hate this. Solution submitted with PyPy got hacked, but the same solution submitted with Python3 passes all tests.

i have a better solution for problem b: ~~~~~ void solve() { int n;cin>>n; vectora(4*n); if(n==2){ cout<<2 <<" "<< 1<<" "<< 1<<" " <<2<<" "<< 1<<" "<< 2<<" " <<2 << " "<<1<<endl; return; } int start=0; int m=4*n; int x=1; while(m && x<=n){ a[start]=x; a[start+1]=x; a[start+3]=x;

if(m==4) a[2]=x;
    else a[start+  6 ]=x;
    x++;
    m=m-4;

    start=start+4;


}
for(auto i:a){
    cout<<i<<" ";
}
cout<<endl;
return;

}

signed main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int t;
cin >> t;

while (t--) {
    solve();
}

return 0;

}

~~~~~

Can somebody help in Problem C, my logic for it:

I made a binary string using the bracket sequence given and counted the '(' which contributes to the cost and gave it 1 in string, and all others are 0,

then, by looking at this cost string, I choose the k characters from this, because only these characters will lower the cost,

and make an ans string from this cost string as: 378013633 but this comes out wrong,

Please correct me and how to solve C

I did this on b: ~~~~~ rep(i,1,n+1) cout<<i<<' '; rep(i,1,n+1) cout<<i<<' '<<i<<' '; rep(i,1,n) cout<<n-i<<' '; cout<<n; ~~~~~

a very easy construction for B:

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

int main() {
	int T; cin >> T;
	while(T--) {
		int n; cin >> n;
		queue<int> q;
		for(int i = 1;i <= n;i++)
			q.push(i);
		for(int i = 1;i <= 4;i++) {
			for(int j = 1;j <= n;j++)
				cout << q.front() << " ",
				q.push(q.front()), q.pop();
			for(int j = 1;j <= i;j++)
				q.push(q.front()), q.pop(); 
		} cout << endl;
	}
	return 0;
}

Okay so I did not figure out any of the methods for B, got stuck on B itself, but then found a random pattern that will always satisfy the property given in the problem. The pattern is as follows : 1 2 3 ... n | 2 3 4 ... n 1 | 2 3 4 ... n 1 | 1 2 3 ... n I added the divisions in the sequence for a better clarity in reading, and we can generalize the values of difference in positions for all the numbers, viz. equal to n-1, n and n+1 for i = 2 to n, and 2n-1, n, and 1 for i = 1.

The recursive method to solve this problem is something that should've struck me during the contest, but yeah next time.

Edit : I found a better method to logically get this pattern. Basically [1, 2, 2, 1, 2, 1, 1, 2] is a valid sequence for n = 2, and now we can observe for this that to go from size n to n+1 we simply add the new elements just after the previous largest elements. The properties remain valid as the largest differences grow at the greatest rate and thus the differences can never become equal.

I ended up solving C using a different O(n) greedy based on directly destroying matched pairs and maintaining active bracket structure rather than the pref_open + suff_close observation from the editorial.

I wrote up the idea here if anyone is interested:

https://codeforces.me/blog/entry/154439

378240026

I forgot that I registered for this contest, what a pity...

However, I've found a solution for B without the need to consider the parity of n.

for(int j=1;j<=4;j++){
    if(j==2){
        for(int i=1;i<=n;i++){
            cout << i << ' ';
        }
    } else {
        for(int i=2;i<=n;i++){
            cout << i << ' ';
        }
        cout << 1 << ' ';
    }
}

What could be the rating of problem D ?

guys i am unable to solve the problem d can anyone explain clearly . i have asked ai to explain but its sloppy explanation made my brain rot

It was harder than usual edu div2. But got 3 done anyhow

I completely missed the construction strategy for problem B, but it turns out that backtracking, albeit an overkill approach for this problem, works in the allotted time constraint. It helps that early placements of integers never fails and each placement can be validated in constant time before recursing.

Here is my solution: 379937279

An Intuitive Explanation: Thinking with the Balance Graph (2233C — Cost of a Bracket Sequence)

Instead of staring at algebraic formulas, let us visualize the string as a trajectory on a 2D plane:

• Start at (0, 0).
• For each character, if it is '(', move up by 1 (+1). If it is ')', move down by 1 (-1).

Here is the beautiful geometric insight that makes the O(n) solution trivial:

1. Why the Global Minimum (mn) represents Unmatched ')' When we scan from left to right, whenever the graph dips below its previous minimum, it means we have encountered more ')' than '(' can safely shield. Any '(' that appears AFTER a dip cannot save the ')' before it, because brackets can only match forward. Therefore, the global minimum (the lowest valley) represents the absolute bottleneck: the total number of inherently unmatched ')' in the string is exactly -mn. Since every unmatched ')' directly kills one potential pair, the maximum number of pairs we can ever form is bounded by: Max Pairs = total_close + mn.

2. The Magic Split Point (pos) Let 'pos' be the index where the graph hits this global minimum. By definition, 'pos' must be a ')' character. If we cut the string at 'pos', look at what happens to the two sides:

• To the left of 'pos': The graph ends at its absolute lowest point. This means every single '(' on the left has been completely consumed and paired up by the ')' on the left. There are no leftover '(' here; only a surplus of unmatched ')'.
• To the right of 'pos': The graph starts at its lowest point and can only go up relative to this baseline. This means every single ')' on the right will find a matching '(' on the right. There are no leftover ')' here; only a surplus of unmatched '('.

3. How to Minimize Pairs with k Deletions Our goal is to minimize the final cost (max pairs), which means we want to maximize the number of unmatched brackets.

• Left of 'pos': The surplus is unmatched ')'. To preserve this, we should greedily delete '(' from the very beginning. Deleting a '(' prevents it from absorbing a ')', keeping the valley deep.
• Right of 'pos': The surplus is unmatched '('. To preserve this, we should greedily delete ')' from the very end. Deleting a ')' prevents it from absorbing a '('.

This completely validates the greedy choice of 'pos' and the deletion strategy!

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    // Track the trajectory to find the lowest valley (global minimum)
    int c = 0, pos = 0, mn = 0;
    for (int i = 0; i < n; i++) {
        c += (s[i] == '(' ? 1 : -1);
        if (c < mn) {
            mn = c;
            pos = i + 1; // Split right after the lowest valley
        }
    }
    
    string ans(n, '0');
    // Left side: kill '(' from the front to maximize unmatched ')'
    for (int i = 0; i < pos && k; i++)
        if (s[i] == '(') ans[i] = '1', k--;
        
    // Right side: kill ')' from the back to maximize unmatched '('
    for (int i = n - 1; i >= pos && k; i--)
        if (s[i] == ')') ans[i] = '1', k--;
        
    cout << ans << '\n';
}

381280759--> My solution for C

An Intuitive Way to Look at the Problem

When I first looked at this problem, I couldn't really think about stack matching or prefix balances. Instead, I tried to understand how a balanced bracket sequence is actually formed.

Step 1: Looking at a single Regular Bracket Sequence

Consider any single Regular Bracket Sequence (RBS). If we scan it from left to right, there may be moments where we have seen more ) than (. These are the places where some closing brackets are temporarily “waiting” for opening brackets.

Similarly, if we scan from right to left, there may be moments where we have seen more ( than ). These opening brackets.

The important realization is this: A single RBS can only have its imbalance coming from one direction. It cannot simultaneously have unmatched ) on the right and unmatched ( on the left.

Why? Because if both kinds of unmatched brackets existed inside the same RBS, they would eventually match each other, meaning they were never truly unmatched in the first place.

So every RBS is either * right-heavy (extra ) while scanning left to right), or * left-heavy (extra ( while scanning right to left), but never both.

Step 2: What happens when multiple RBSs are placed together? Now imagine the entire string consists of several RBSs placed one after another. Suppose the first RBS is right-heavy. Then the next RBS can again be right-heavy.

Eventually, we encounter the first left-heavy RBS. Now comes the key observation: After the first left-heavy component appears, every RBS after it must also be left-heavy.

Why? Assume the opposite. Suppose after a left-heavy RBS, another right-heavy RBS appears.

The unmatched opening brackets from the left-heavy component and the unmatched closing brackets from the later right-heavy component would meet and form pairs. That means those two parts were actually connected and should have been considered one larger RBS instead of two separate ones.

This is a contradiction.

Therefore, the sequence of components looks like

Right-heavy Right-heavy Right-heavy ... Left-heavy Left-heavy Left-heavy

There can be only one transition from right-heavy to left-heavy. OR simply all being either Right-heavy only or Left-heavy only and no transition.

Step 3: Finding the transition

Now the implementation becomes straightforward. Left to Right Scan Maintain the balance. Whenever the balance becomes negative, record that index.

The last such position is stored as lastRightBracket This marks the end of the right-heavy region.

Right to Left Scan Again maintain the balance, but in reverse. Whenever the reverse balance becomes negative, record that index.

The last recorded position becomes lastLeftBracket This marks where the left-heavy region begins.

Step 4: Constructing the answer

Now the string naturally divides into three regions.

|---- Right-heavy ----|---- Middle ----|---- Left-heavy ----| 0 lastRight lastLeft n-1

Now simply choose brackets greedily.

• In the right-heavy region, pick opening brackets ( until we have selected k.
• In the middle region, continue picking any opening brackets (as this transition region is no heavy region i.e nothing outside of it can affect it) until we have selected k.
• In the left-heavy region, pick closing brackets ) until we have selected k.

Everything else is ignored.

This directly constructs the required answer.

Complexity

Both scans are linear.

• First scan: O(n)
• Second scan: O(n)
• Constructing the answer: O(n)

Overall complexity:

• Time: O(n)
• Space: O(n)

Final Thoughts

What I like most about this solution is that it didn’t come from memorizing a known trick or an algo.

Instead, it came from asking a simple question: “Where does the imbalance of each regular bracket sequence actually come from?”

Once I realized that every balanced component can only be imbalanced from one side, the existence of a single transition point became almost obvious.

From there, the implementation naturally followed with just two linear scans.

https://codeforces.me/contest/2233/submission/381280759-- My solution for C

An Intuitive Way to Look at the Problem

When I first looked at this problem, I couldn't really think about stack matching or prefix balances. Instead, I tried to understand how a balanced bracket sequence is actually formed.

Step 1: Looking at a single Regular Bracket Sequence

Consider any single Regular Bracket Sequence (RBS). If we scan it from left to right, there may be moments where we have seen more ) than (. These are the places where some closing brackets are temporarily “waiting” for opening brackets.

Similarly, if we scan from right to left, there may be moments where we have seen more ( than ). These opening brackets.

The important realization is this: A single RBS can only have its imbalance coming from one direction. It cannot simultaneously have unmatched ) on the right and unmatched ( on the left.

Why? Because if both kinds of unmatched brackets existed inside the same RBS, they would eventually match each other, meaning they were never truly unmatched in the first place.

So every RBS is either * right-heavy (extra ) while scanning left to right), or * left-heavy (extra ( while scanning right to left), but never both.

Step 2: What happens when multiple RBSs are placed together? Now imagine the entire string consists of several RBSs placed one after another. Suppose the first RBS is right-heavy. Then the next RBS can again be right-heavy.

Eventually, we encounter the first left-heavy RBS. Now comes the key observation: After the first left-heavy component appears, every RBS after it must also be left-heavy.

Why? Assume the opposite. Suppose after a left-heavy RBS, another right-heavy RBS appears.

The unmatched opening brackets from the left-heavy component and the unmatched closing brackets from the later right-heavy component would meet and form pairs. That means those two parts were actually connected and should have been considered one larger RBS instead of two separate ones.

This is a contradiction.

Therefore, the sequence of components looks like

Right-heavy Right-heavy Right-heavy ... Left-heavy Left-heavy Left-heavy

There can be only one transition from right-heavy to left-heavy. OR simply all being either Right-heavy only or Left-heavy only and no transition.

Step 3: Finding the transition

Now the implementation becomes straightforward. Left to Right Scan Maintain the balance. Whenever the balance becomes negative, record that index.

The last such position is stored as lastRightBracket This marks the end of the right-heavy region.

Right to Left Scan Again maintain the balance, but in reverse. Whenever the reverse balance becomes negative, record that index.

The last recorded position becomes lastLeftBracket This marks where the left-heavy region begins.

Step 4: Constructing the answer

Now the string naturally divides into three regions.

|---- Right-heavy ----|---- Middle ----|---- Left-heavy ----| 0 lastRight lastLeft n-1

Now simply choose brackets greedily.

• In the right-heavy region, pick opening brackets ( until we have selected k.
• In the middle region, continue picking any opening brackets (as this transition region is no heavy region i.e nothing outside of it can affect it) until we have selected k.
• In the left-heavy region, pick closing brackets ) until we have selected k.

Everything else is ignored.

This directly constructs the required answer.

Complexity

Both scans are linear.

• First scan: O(n)
• Second scan: O(n)
• Constructing the answer: O(n)

Overall complexity:

• Time: O(n)
• Space: O(n)

Final Thoughts

What I like most about this solution is that it didn’t come from memorizing a known trick or an algo.

Instead, it came from asking a simple question: “Where does the imbalance of each regular bracket sequence actually come from?”

Once I realized that every balanced component can only be imbalanced from one side, the existence of a single transition point became almost obvious.

From there, the implementation naturally followed with just two linear scans.

C is a beautiful problem , i li it!

js an A, yet I rewrote my code more than three times :sob:. Great problem!