Cheeky DP solution to a Greedy problem [Div2C]
Разница между en1 и en2, 0 символ(ов) изменены
During the [Educational CF Round 128](https://mirror.codeforces.com/contest/1997) while solving problem C, I stumbled upon a cheeky ↵
DP based solution to the problem.↵

## Problem: [problem:1997C]↵
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.↵

![Image to show that only the top left combination works which gives the answer for base case as 1](https://gcdnb.pbrd.co/images/N6BVAnMXv4wu.png?o=1)↵

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.↵

![ ](https://gcdnb.pbrd.co/images/KmKQtk5ISgrb.png?o=1)↵

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 :)↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский BinaryBubble 2024-08-19 16:17:09 35 Tiny change: 'lem:1997C]\nfor thos' -> 'lem:1997C] (it doesn't even have a dp tag)\nfor thos'
en2 Английский BinaryBubble 2024-08-19 16:13:23 0 (published)
en1 Английский BinaryBubble 2024-08-19 16:12:38 2600 Initial revision (saved to drafts)