P9805 [POI 2022/2023 R1] ply

This problem is translated from [POI2022~2023R1 ply](https://sio2.mimuw.edu.pl/c/oi30-1/p/ply/).

Define a "valid bracket sequence" and its depth as follows: - The empty string is a valid bracket sequence, with depth $0$. - If $w$ is a valid bracket sequence with depth $h$, then $(w)$ is also a valid bracket sequence with depth $h+1$. - If $w_1$ and $w_2$ are both valid bracket sequences with depths $h_1$ and $h_2$, then $w_1w_2$ is also a valid bracket sequence, with depth $\max(h_1,h_2)$. Define flipping a character as: - If the current character is `(`, change it to `)`. - If the current character is `)`, change it to `(`. You need to flip some characters in $s$ so that the depth does not exceed $H$. Find the minimum number of operations.

The first line contains two integers $n \ (2 \leq n \leq 10^6)$ and $H \ (1 \leq H \leq \frac{n}{2})$, representing $|s|$ and the required maximum depth after modification. The second line contains a string $s$, representing the original bracket sequence.

Output the minimum number of modifications.

For the sample, you can modify it to `(()()())`, whose depth is $2$. The subtasks are as follows: | Subtask ID | Special Property | Score | | :-----------: | :-----------: | :-----------: | | $1$ | $n \leq 20$ | $20$ | | $2$ | $n \leq 3000$ | $40$ | | $3$ | $n \leq 10^6$ and $H = h-1$ | $20$ | | $4$ | $n \leq 10^6$ | $20$ | Note: $h$ is the depth of the input bracket sequence. In this problem, subtask $0$ is the sample. Translated by ChatGPT 5