wizard_18's blog

Dynamic Programming Approach for Partial Replacement (Codeforces Round #710(div 3))
By wizard_18, history, 5 years ago, In English

What is the dp approach for this problem??

  • Vote: I like it
  • -7
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

You can check-out my submission. I used dynamic programming.

https://codeforces.me/contest/1506/submission/111002216

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    what was your intuition behind this approach? basically what is the overlapping subproblem in this solution?

    → Reply
    • »
      »
      »
      5 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +6 Vote: I do not like it

      The idea was to find the answer if the string was to end at ith index such that s[i] = '*'.

      dp[i] represents the minimum number of replacements for the prefix s[0]....s[i] where s[i]='*'.

      dp[index of first occurrence of '*' in s] = 1 (base condition).

      The transition is pretty simple, if s[i]='*', and because it is the last character of our prefix, we will have to change it to 'x'.

      So we traverse over all the previous indices 'j' of s such that s[j]='*' and (i — j)<=k (due to the range given) and do the transition dp[i]=min(dp[i],dp[j]+1) (+ 1 because we are replacing the current character to 'x' as well).

      Our final answer will be dp[index of last '*' character in s].

      → Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

Here's a recursive DP approach , I think it is pretty intuitive.

https://codeforces.me/contest/1506/submission/111108103

→ Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My submission with explanatory comments

→ Reply