SmallestRegular

SRM 786 · 2020-05-14 · by vivek1998299

SRM 786 · 2020-05-14 · by vivek1998299 · Brute Force

Show categories

Class Name: SmallestRegular

Return Type: int[]

Method Name: findLexSmallest

Arg Types: (string)

Problem Statement

A regular bracket sequence is a sequence of opening ("(") and closing (")") brackets such that it is possible to obtain a correct mathematical expression from it by inserting numbers and operators between the brackets. For example, the sequences "(())()" and "()" are regular bracket sequences while sequences such as ")()" and "(()" are not.

A string is said to be valid if for each of its non-empty prefixes the number of opening brackets >= number of closing brackets. For example, "((()()" and "(())" are valid strings but ")(" is not.

T[a..b] denotes the substring of T formed by characters at 0-based indices a through b, inclusive. E.g., if T = "qwertyuiop" then T[2..5] = "erty".

You are given a regular bracket sequence S of length N. Your goal is to change S into the lexicographically smallest regular bracket sequence possible. Below we define the meaning of an operation. You have to find any sequence of at most 300 operations that reaches your goal.

An operation looks as follows:

Choose a triplet of indices (a,b,c) such that 0 <= a <= b < c <= N-1 and that both substrings S[a..b] and S[b+1..c] are valid strings (as defined above).
Swap the substrings S[a..b] and S[b+1..c].

Lets say the number of operations you needed is X. Then return a int[] res with 3*X elements, where for i-th operation (a, b, c) we have res[3*i]=a, res[3*i+1]=b and res[3*i+2]=c respectively.

Notes

For the purpose of the lexicographic ordering of bracket sequences, the character '(' is smaller than the character ')'.
You are not required to minimize the number of operations. Any valid solution will be accepted.

Constraints

S will consist of characters '(' and ')' only.
S.length will be between 2 and 500, inclusive.
S.length will be even.
S will be a regular bracket sequence.

Examples

"((()()(())))"
Returns: {0, 3, 4, 0, 5, 6, 0, 6, 7 }

"()()()()(())"
Returns: {0, 1, 2, 0, 3, 4, 0, 5, 6, 0, 7, 8, 0, 8, 9 }

"(())"
Returns: { }

"()()((((())())))"
Returns: {0, 1, 2, 0, 3, 4, 0, 4, 5, 0, 5, 6, 0, 6, 7, 0, 7, 8, 0, 10, 11 }

"()()()(())()(())()"
Returns: {0, 1, 2, 0, 3, 4, 0, 5, 6, 0, 6, 7, 0, 9, 10, 0, 11, 12, 0, 12, 13, 0, 15, 16 }

150)

"(())"
Returns: { }

Here we can see that S is already lexicographically smallest.

151)

"(()())"
Returns: {1, 2, 3 }

Here after performing operation (1, 2, 3), we obtain S = "((()))" which is the lexicographically smallest S we can obtain.

152)

"()()()()"
Returns: {2, 3, 6, 2, 3, 5, 0, 1, 4 }

Here after preforming the first operation (2, 3, 6), we obtain S = "()()(())". Now after second operation (2, 3, 5), we obtain S = "()((()))". After third operation (0, 1, 4), we obtain S = "(((())))".

Submissions are judged against all 157 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SmallestRegular with a public method vector<int> findLexSmallest(string S) · 157 test cases · 2 s / 256 MB per case