REMBAL Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jyothi Surya Prakash Bugatha
Tester: Jakub Safin, Satyam
Editorialist: Pratiyush Mishra

DIFFICULTY:

2231

PREREQUISITES:

Strings

PROBLEM:

A string consisting only of parentheses \verb+(+ and \verb+)+ is called a parentheses string. The balanced parentheses strings are defined recursively as follows:

  • An empty string is a balanced parentheses string.
  • If s is a balanced parentheses string, then \verb+(+s\verb+)+ is also a balanced parentheses string.
  • If s and t are balanced parentheses strings, then st (concatenation of s and t) is also a balanced parentheses string.

For a parentheses string, an operation on this string is defined as follows:

  • Choose any substring of this string which is balanced.
  • Remove this substring and concatenate the remaining parts.

Given a parentheses string S, find the minimum length of the string one can get by applying the above operation any number of times. Also find the minimum number of operations required to achieve this minimum length.

EXPLANATION:

The first observation that we can make is that on removing a balanced parenthesis from the string, it won’t affect other balanced parenthesis in the remaining string. So what we can do is remove all the balanced parenthesis from the string and then on the final string left, we can calculate the number of operations by counting the number of missing segments in it.

In order to implement it we can replace the string by a vector v, where

v[i] = \begin{cases} (i+1), \; if \; s[i] = ( \\ -(i+1), \; if \; s[i] = ) \end{cases}

Now we can take another vector, say res and loop through the vector v and for any index i, which has a closing bracket, i.e v[i] < 0, if we can find a corresponding opening bracket at index j, that makes string s[j...i], balanced, i.e we find res not empty and last element of res to be positive, we simply remove the last element of res, implying that substring s[j....i] is removed, otherwise we simply add v[i] to res

Thus in the end res would contain the indexes of the final string after removing all the possible balanced parenthesis from the original string.
The size of res would be the first part of the answer, i.e the length of the final string. As for the number of operations, we have the indexes of the characters of the final string, so we can just count the number of missing segments to get the second part of the answer.

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

1 Like
2

Please give some test cases for which my solution fails.
Link to my solution

3

Another possible solution:
Here is a reference link through which I was able to solve the first half of the problem. I calculated the number of non-overlapping ‘!’ that gave me the answer for the second half:
Click me :smile:

4

Shorter implementation using stack.

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

int main() {
  int t;
  for (cin >> t; t; t--) {
    string s;
    cin >> s;
    vector<pair<char, int>> stk;
    stk.emplace_back('$', -1);
    int n = s.size();
    for (int i = 0; i < n; i++) {
      if (s[i] == ')' && stk.back().first == '(') stk.pop_back();
      else stk.emplace_back(s[i], i);
    }
    stk.emplace_back('&', n);
    int ans = 0;
    for (int i = 0; i + 1 < (int) stk.size(); i++) {
      if (stk[i + 1].second != stk[i].second + 1) ans++;
    }
    cout << (int) stk.size() - 2 << ' ' << ans << '\n';
   }
  return 0; 
}
3 Likes
5

Hey @fireflake0987 :smiling_face: ,
Your code is failing for the TC

1
)(()())(((
Your output : 2 2
Correct output : 4 1

1
((()((())))())()((
Your output : -10 3
Correct output : 2 1

1 Like
6

dp+stack solution
https://www.codechef.com/viewsolution/64275440

similar problem for practice

1 Like
7

I want to ask that why can’t we use stack for this question ??

8

can you please explain ur logic?

9

Can anyone please give me some testcases where this code would fail.

10

Hey @imayank :smiling_face:
The Link you have provided says Internal Server Error.

11

If we keep removing balanced substring, in the end we will be left with unbalanced string that do not contain any balanced substring.
It is beneficial to remove longest balanced substrings.
We can find the indices of the final unbalanced string using stack. We pop, when top of stack is ‘(’ and current s[i] is ‘)’ as the cancel each other, otherwise we push(s[i]).

After that we need to count the number of consecutive indices i, j such that j - i > 1, as it was having some maximal balanced string in between.

1 Like
12

Hi, for the second test case, How is the correct output 2 1, we can do 2 operations to remove the balanced part, wouldn’t the remaining would be the last 2 “((”?

1 Like
13

Hey @trying_cpp :wave: ,
You are confused, format of output is minimum_length minimum_operation ,thus “((” is minimum length we get with removal of substring with 1 operation thus 2 1.

14

how 1 operation can you explain … its 2 operation needed to get it

15

1
((()((())))())()((
Here in one operation we can erase the substring 1 to 16(1 based index).and remaining string is “((” thus size of rem is 2 and operation 1.

16

why is my logic wrong ??
https://www.codechef.com/viewsolution/64566313