Editorial for ICPC NAQ 2016 D - Brackets
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Let
denote the sequence of brackets.
- An alternative way to characterize a valid bracket sequence:
- For each prefix of the sequence, there are at least as many left brackets as there are right brackets, and
- there are equally many left and right brackets in the entire sequence.
- Basic idea:
- Step through the sequence from left to right, keeping track of the number of left and right brackets.
- At some point start inverting brackets. At some later point, stop inverting brackets.
- At each step, make sure there are at least as many left brackets as there are right brackets (condition 1).
- When at the end, make sure there are equally many left and right brackets (condition 2).
- How to decide when to start/stop inverting? Dynamic programming.
- Let
be true iff it's possible to step through
such that conditions 1 and 2 are satisfied, assuming that
is the number of left brackets we've seen so far, and
if we have not started inverting brackets yet,
if we are currently inverting brackets, and
if we have stopped inverting brackets.
- Note that
is the number of right brackets we've seen so far.
- Base case:
iff
.
- Recurrence:
where
- Answer is
.
- Can be computed in
using dynamic programming.
Comments