During the Educational CF Round 128 while solving problem C, I stumbled upon a cheeky DP based solution to the problem.

Problem: 1997C - Even Positions

for those who're too lazy to click on the link, in short the problem says that.

we're given a sequence a Bracket sequence which was originally a valid bracket sequence but now every odd position element is lost and we have the remaining sequence (eg: _(_)_)). now we need to find the minimum cost between all the possible valid sequences where the cost of a sequence is summation of the distance between each opening and its corresponding closing bracket (eg: for _(_)_) a possible valid sequence can be (())() and its cost would be $$$3 + 1 + 1 = 5$$$).

Now given the incomplete bracket sequence we need to find the minimum possible cost among all the possible valid sequences.

Constraints are so that its always possible to construct a valid sequence.

Solution I found:

we can say that $$$dp[i] = \text{minimum cost if we just consider the suffix from i to n}$$$

the base case will be $$$dp[n] = 1$$$ as last element will always be ) and the only valid answer for that is always () which gives 1 as the minimum cost. we can clearly see this in the figure below.

now the transition from one state to next state will be

$$$dp[i] = dp[i + 1] + 1$$$ (if we stumble upon ))

or $$$dp[i] = dp[i + 1] + 3$$$ (if we stumble upon ().

we can just create our answer all the way to $$$i = 1$$$ and our final solution will be at $$$dp[1]$$$ (PS: we're considering 1 based indexing here)

now why does it work ? let's look at some bigger cases.

We can observe that no matter which type of bracket we get we can always create smaller brackets whose cost will be 1.

if we get ) we just create a smaller bracket but if we get ( we still create a smaller bracket of cost 1 but we push it inside a bigger bracket whose cost keeps increasing by 2 with each incoming (.

so why $$$+3$$$ ? $$$+3$$$ represents the increase in size of the bigger bracket by $$$+2$$$ and a creation of smaller bracket which costs $$$+1$$$ in total giving us a $$$+3$$$.

Here's an AC solution to the problem with this approach: 277181878

PS: This is my first blog so feel free to leave any suggestions/feedback and Sorry for any mistake i made :)