DMPG '17 S6 - Brackets, Braces, and Boxes - DMOJ: Modern Online Judge

DMPG '17 S6 - Brackets, Braces, and Boxes

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 1.4s

Memory limit: 256M

Author:

k_53P

Problem types

Molly was experimenting with bracket strings, when she made a mistake and accidentally changed some of the characters. Now, she needs your help to fix her bracket sequence.

To begin, here are Molly's definitions:

A bracket string consists of the following six symbols: ()[]{}. The characters ([{ are considered left brackets, and )]} are considered right brackets.
There are three distinct matching pairs: (), [], and {}. Within each pair, the left bracket must be paired with the right bracket.
A string is considered valid if every left bracket can be paired with a distinct right bracket such that the left bracket appears to the left of the right bracket, and the string inside of the matching pair is either empty or valid. For example, valid sequences could be (), ({}[[]()]), or ()[]{}{[()]} whereas invalid sequences would be ({)}, ((([]) and }{.

Currently, Molly has a bracket string (either valid or invalid), and would like you to change exactly $K$ ~K~ symbols at distinct positions, and create a valid string. However, you are not allowed to change a left bracket to a right bracket, or a right bracket to a left one. If it is impossible to create a valid bracket string, output impossible instead.

Constraints

Subtask 1 [20%]

$N, K \le 20$ ~N, K \le 20~

Subtask 2 [30%]

$K \le 1$ ~K \le 1~

Subtask 3 [50%]

No additional constraints.

Input Specification

On the first line, there will be the integers $N$ ~N~ and $K$ ~K~. On the second line will be the original string of length $N$ ~N~.

For all cases, $2 \le N \le 200\,000$ ~2 \le N \le 200\,000~, and $N$ ~N~ is even; and $0 \le K \le N$ ~0 \le K \le N~.

Output Specification

On a single line, print either a valid bracket string of length $N$ ~N~ with $K$ ~K~ characters different from the input string, or impossible.

Sample Input 1

2 2
()

Sample Output 1

[]

Sample Input 2

4 2
({)}

Sample Output 2

({})

Sample Input 3

6 2
(((]]]

Sample Output 3

impossible

Comments

0

Ninjaclasher commented on June 6, 2017, 1:12 a.m.

If the bracket string is already valid, do you have to change it so it stays valid, or can you just output the inputted string?

1

wleung_bvg commented on June 6, 2017, 1:51 a.m.

You have to change exactly K characters