1080. When a Closing Bracket Counts Double

A line contains only ( and ). Under the rules here, every ( must be matched by TWO CONSECUTIVE ) after it, properly nested. So ()) is balanced, () is not, and (()) is not either, because it has two openers and only two closers.

You may INSERT brackets anywhere. Print the fewest insertions that make the line balanced.

(())) -> 1 insert one ) at the end, giving (()))) , which reads ( ( )) )) ()) -> 0 () -> 1 it needs a second ) ((( -> 6 each opener needs its own pair of closers ()() -> 2

## What most people try first

Search over insertions, which branches hard, or the counter from #1043 with the closing side weighted. The second idea is right and the weighting is where it goes wrong: a ) cancels HALF an opener, so the running quantity is no longer an integer count of openers, and an implementation that halves things loses the odd cases.

The brute force the expected outputs were checked against is a shortest path over (position in the line, closers still owed, half way through a pair), which never uses the counter at all.

## Carry the number of CLOSERS still owed

res = 0 insertions so far need = 0 how many ) are still owed by the openers seen for each character c: if c == '(': need += 2 if need is odd: we are stranded mid-pair res += 1; need -= 1 insert one ) to finish the pair first else: need -= 1 if need < 0: this ) has no opener res += 1; need = 1 insert one ( , which owes two, one of them just paid answer = res + need

## The two repairs, in words

An opener arriving while need is ODD means the previous opener is half paid: exactly one of its two closers has arrived, and the new opener would nest inside a broken pair. The only repair is to insert one ) now, which costs 1 and makes need even again.

A closer arriving when nothing is owed has no opener at all. Inserting one ( before it costs 1 and owes two closers, of which the current character pays one, leaving need = 1.

At the end, need closers are still owed and each costs one insertion, so the answer is res + need.

## Why each repair is forced rather than chosen

In both cases the character being read cannot be part of any legal line given what precedes it, and the prefix before it has already been made legal at minimum cost. So a repair must happen at this point, and each repair above is a single insertion, which is the smallest any repair can be. Since exactly one insertion resolves the conflict, no cheaper choice exists and no alternative repair does better.

That is a lower bound and an achievable construction at once, the same shape as #1043.

## Why the doubling really changes things

On () the answer is 1 and on ()() it is 2, so the answer is NOT the #1043 answer scaled. And (())) answers 1 while its ordinary-bracket answer is 1 as well, which is why a single sample cannot distinguish the two rules. The tests include ((( at 6 and ))) at 3, which pin the asymmetry.

## Overflow

need is at most twice the length, 400000, and the answer is at most twice the length too. The 32 bit limit of 2147483647 is not in play.

## Cost

Time O(m). Space O(1).

Constraints - `1 ≤ length ≤ 200000` - the line contains only `(` and `)`