BREAKBAL - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Jeevan Jyot Singh
Tester: Aryan Choudhary
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Greedy

PROBLEM:

Given a balanced parenthesis, find the minimum number of adjacent swaps to make the parenthesis unbalanced.

QUICK EXPLANATION:

For each prefix of the string (including the empty string), find the minimum number of adjacent swaps required such that the number of closing parenthesis is one greater than the number of opening parenthesis in the prefix.

EXPLANATION:

Getting WA? 
1
(((()))()()((())))

The correct answer to this test case is 3.

A parenthesis is unbalanced if any of the two conditions hold true:

  • The number of opening parenthesis in the string is not equal to the number of closing parenthesis.
  • The number of opening parenthesis is less than the number of closing parenthesis in any prefix of the string.

Since the string is initially balanced, the first condition can never be true.
Thus, we need to make adjacent swaps such that we get a prefix having more number of closing parenthesis than opening.

To make it unbalanced, just one extra closing parenthesis is sufficient in any prefix of the string.

While traversing the string, we keep a count of the number of opening ( open ) and closing parenthesis ( closed ) encountered yet. For each prefix (including empty string),
number of required closing parenthesis (x) = open - closed + 1.

The most optimal way to make the string unbalanced using the current prefix, is to add the next x closing parenthesis from the current position to the right of the current prefix.
The number of adjacent swaps required to bring the next x closing parenthesis to the right of the current prefix is a possible answer.

Why is this optimal?

  • For each prefix in the string, we can make the string unbalanced if the number of ‘)’ is greater than the number of ‘(’ in the prefix. Since the string is initially balanced, we need to bring ‘)’ from the suffix to the prefix using adjacent swaps. Adding each extra ‘)’ has an additional cost, thus we have to minimize the number of ‘)’ we add to the prefix, still making it unbalanced.

  • Suppose we need x ‘)’ to be added after prefix (1, i - 1). Let the positions of subsequent ‘)’ after position i -1 be b_1 < b_2 < … < b_x < … < b_m.
    Let us choose the first x values, i.e. {b_1, …, b_x}. If we replace any of these values b_i (i \leq x) by b_j (j > x), we need an extra (b_j - b_i) adjacent swaps. Thus, adding any ‘)’ other than the first x would increase the answer.
    The optimal way is to choose the next x ‘)’ for each prefix to make the string unbalanced.

  • In the above method, we are calculating the minimum swaps to make the string unbalanced by finding the answer for each prefix of the string and taking the overall minimum. A symmetric way is to calculate this for each of the suffixes and make the string unbalanced by adding an extra opening parenthesis to any suffix. That would result in the same answer.

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTION:

Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;

#define sync                               \
    {                                      \
        ios_base ::sync_with_stdio(false); \
        cin.tie(NULL);                     \
        cout.tie(NULL);                    \
    }
#define rep(n) for (int i = 0; i < n; i++)
#define rep1(a, b) for (int i = a; i < b; i++)
#define int long long int
#define mod 1000000007

int n;

void solve() {
    string s;
    cin >> s;

    n = s.length();

    vector<int> prefixSum;
    // i'th index stores the swaps required to bring first i ')' to the start (one by one)

    prefixSum.push_back(0);

    for (int i = 0; i < n; i++){
        if (s[i] == ')'){
            prefixSum.push_back(prefixSum.back() + i);
        }
    }

    int open = 0;
    int closed = 0;
    int ans = INT_MAX;

    for (int i = 0; i < n; i++){

        // For a prefix from 0 to i (i not included)
        int x = open - closed + 1; // no. of ')' we need to bring at index I

        // we do not have sufficient ')' in the right part to make a prefix unbalanced
        if (closed + x > n / 2){ 
            break;
        }

        // no. of swaps required to bring next x ')' to the front of string in the same order
        int frontCost = prefixSum[closed + x] - prefixSum[closed] - x * (x - 1) / 2; 

        // We need to shift x ')' from the positions {0,..,x-1} to the positions {i,..., i+x-1}
        int shiftCost = x * I;

        int totalCost = frontCost - shiftCost;
        ans = min(ans, totalCost);

        if (s[i] == '(')
            open++;
        else
            closed++;
    }
    cout << ans;
}

int32_t main()
{

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    sync;
    int t = 1;
    cin >> t;
    while (t--){
        solve();
        cout << "\n";
    }
    return 0;
}
4 Likes