ICPC NAQ 2016 D - Brackets

View as PDF

Submit solution

Points: 10
Time limit: 0.6s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
ICPC North America Qualifier 2016, Problem D

Inversion Example

A bracket sequence consisting of ( and ) is defined to be valid as follows:

  • An empty sequence is valid.
  • If X is a valid bracket sequence, then (X) is a valid bracket sequence.
  • If X and Y are valid bracket sequences, then the concatenation of X and Y, Z = XY, is a valid bracket sequence.

For example, (()), ()(), and (()())() are all valid bracket sequences, while ( and ()) are invalid bracket sequences.

You get a bracket sequence from the professor of length n. However, it might not be valid at the moment. The professor asks you to check if it is possible to make the sequence valid by performing at most one segment inversion operation. That is, you may choose two 1-based indices l and r (1 \le l \le r \le n) and invert each bracket with an index in the closed interval [l,r]. After the inversion, a left bracket ( becomes a right bracket ), and a right bracket ) becomes a left bracket (.

You can make ())( valid by inverting the segment [3,4]. You can make ())) valid by inverting the segment [3,3], or alternatively by inverting the segment [2,2]. However, there does not exist a segment you can invert to make )))( valid.

Input Specification

The input consists of one line containing between 1 and 5\,000 brackets.

Output Specification

Output possible if you can make the bracket sequence valid by performing at most one segment inversion, or impossible otherwise.

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2


Sample Input 3


Sample Output 3

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported


There are no comments at the moment.