During the [Educational CF Round 128](https://codeforces.me/contest/1997) while solving problem C, I stumbled upon a cheeky ↵
DP based solution to the problem.↵
↵
## Problem: [problem:1997C]↵
(it doesn't even have a dp tag)↵
↵
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: [submission:277181878]↵
↵
↵
↵
PS: This is my first blog so feel free to leave any suggestions/feedback and Sorry for any mistake i made :)↵
DP based solution to the problem.↵
↵
## Problem: [problem:1997C]↵
(it doesn't even have a dp tag)↵
↵
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: [submission:277181878]↵
↵
↵
↵
PS: This is my first blog so feel free to leave any suggestions/feedback and Sorry for any mistake i made :)↵
