ParenthesesDiv1Easy | Topcoder Archive

Problem Statement

Correct parentheses sequences can be defined recursively as follows:

The empty string "" is a correct sequence.
If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
If "X" is a correct sequence, then "(X)" is a correct sequence.
Each correct parentheses sequence can be derived using the above rules.

Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".

You have a String s. You want to change it into a correct parentheses sequence.

You can only change the string using magic flips. In order to do a magic flip, you specify two 0-based indices L and R such that L <= R. The operation modifies the characters on indices from L to R, inclusive. First, the order of these characters is reversed. Then, each character is toggled to the opposite one. That is, each '(' in the specified range changes to a ')' and vice versa.

For example, suppose you have the string "((()". If you do a magic flip on the entire string (i.e., choosing L=0 and R=3), it first gets reversed to ")(((" and then all parentheses are toggled. Thus, flipping the string "((()" produces the string "()))".

Given s, find and report any sequence of at most 10 magic flips that changes s into a correct parentheses sequence. If there is no such sequence of magic flips, return the int[] {-1}. If there are multiple such sequences, you may return any of them. In particular, you are not required to find the shortest possible sequence of flips. The returned int[] should contain 2*F elements, where F is the number of flips you want to perform: for each flip, in order, first its L and then its R.

Definition

Class:: ParenthesesDiv1Easy
Method:: correct
Parameters:: String
Returns:: int[]
Method signature:: int[] correct(String s)
(be sure your method is public)

Constraints

s will contain between 1 and 1,000 characters, inclusive.
Each character in s will be '(' or ')'.

Examples

```
")("
```
```
Returns: {0, 0, 1, 1 }
```
The first flip has L=R=0. It changes the string to "((". The second flip has L=R=1. It changes that string to "()", which is a correct parentheses sequence.
```
"))))))(((((("
```
```
Returns: {0, 5, 6, 11 }
```
Here, the first flip changes the string to "((((((((((((" and then the second flip changes it to "(((((())))))". Note that {0,0,1,1,2,2,...,11,11} is not a valid solution. This sequence of flips produces a correct parentheses sequence (by flipping each character separately). However, this sequence consists of 12 flips and we are only allowed to perform at most 10 flips.
```
"))()())()"
```
```
Returns: {-1 }
```
This s has length 9. There is no correct parentheses sequence of length 9, so there can be no good sequence of flips.
```
")()((("
```
```
Returns: {0, 0, 3, 3, 5, 5 }
```
```
"()"
```
```
Returns: { }
```
This time we don't need to do anything.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.