P15236 [NHSPC 2025] Bracket Problem

There are many kinds of brackets, such as curly braces `{}`, square brackets `[]`, and parentheses `()`. In this problem, we only consider parentheses. Brackets are usually used in pairs. If a sequence made of brackets has a **nested structure (nested structure)**, we call this sequence “well-formed”. For example: * Sequence $A=a_1a_2\cdots a_{6}=$`()(())` is well-formed. * Sequence $B=b_1b_2\cdots b_{5}=$`(()()` is not well-formed, because there is no way to make every left parenthesis match with a right parenthesis after it, while also ensuring that each right parenthesis `)` is matched at most once. More formally, “well-formed” is defined as follows: A bracket sequence $P=p_1p_2p_3\cdots p_n$ is well-formed if and only if it satisfies both conditions below: 1. Scanning from left to right from $p_1$ to $p_n$, at any position during the process, the number of right parentheses `)` never exceeds the number of left parentheses `(`. 2. The total number of left parentheses equals the total number of right parentheses in the sequence. PorgramText is a software company developing a brand-new text editor for programmers. This editor will provide many powerful features, one of which is automatically fixing input mistakes. After observing users’ typing behavior, PorgramText found that many programmers, due to typing too fast, often accidentally type extra left parentheses or right parentheses. To solve this, the editor will provide a feature: automatically convert a possibly “not well-formed” bracket sequence $P$ into a “well-formed” sequence $P^\prime$. During the conversion, the only allowed operation is **deleting left parentheses or right parentheses**. PorgramText wants you to help them: compute the minimum number of parentheses that must be deleted to turn $P$ into a “well-formed” sequence.

$$ \begin{aligned} & n \\ & P_1P_2\cdots P_n \\ \end{aligned} $$ * $n$ is the length of the bracket sequence. * $P$ is a bracket sequence consisting of `(` and `)`.

$$ans$$ * $ans$ is the minimum number of parentheses that need to be deleted.

### Constraints * $1 \leq n \leq 10^5$. * $P$ contains only `(` and `)`. ### Scoring This problem has three subtasks, with the constraints as follows. Each subtask may contain one or more pieces of testdata. You will receive the score for a subtask only if all testdata in that subtask are answered correctly. | Subtask | Score | Additional Input Constraints | | :----: | :--: | ------------- | | 1 | 30 | All left parentheses appear before all right parentheses (so `(` and `)` do not interleave). | | 2 | 30 | $ans$ can only be $0$ or $2$. (Note: you only need to determine whether $P$ is “well-formed”.) | | 3 | 40 | No additional constraints. | Translated by ChatGPT 5