LCC/Moose '20 Contest 4 S3 - Deep Brackets

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Max loves balanced bracket sequences, and things that are deep. Thus, he decided to put the two together and create a deep bracket sequence. Unfortunately for him, the balanced bracket sequence he was given for his birthday is not very deep. Can you help him make it deeper? We define a flip to be an operation where you change a ( to a ) or vice versa. Max wants you to demonstrate the minimum number of flips he must execute to make his bracket sequence have depth at least K. Note that the sequence may become unbalanced after the intermediate flips.

A bracket sequence is balanced if you can match every open bracket ( with a closed bracket ) that comes later in the sequence.

We define the depth of a bracket sequence to be the maximum number of nested bracket pairs. For example, the sequence ((()(()))) has depth 4 because ((()(()))) is 4 nested bracket pairs, and you cannot nest more than 4.

Input Specification

The first line of input contains an integer N\ (1 \leq N \leq 2\cdot 10^5), N is even, and K\ (1 \leq K \leq \frac{N}{2}).

The next line of input contains a balanced bracket sequence of length N.

Output Specification

On one line, you are to output F: the minimum number of flips you must make for the balanced bracket sequence to have depth at least K.

On the next line, you are to output F integers, the i^\text{th} integer being the i^\text{th} bracket you flip. If there are multiple solutions, you are to print the lexicographically least. If F=0, this line is blank (still print a line though).

Subtask 1 (10%)

N \leq 20

Subtask 2 (90%)

No further constraints.

Sample Input

10 5

Sample Output

4 5 7 9


There are no comments at the moment.