ragingbull's blog

Stucked at a DP problem in Round 349 (29 April 16)
By ragingbull, 8 years ago, In English

I'm having trouble understanding the DP solution in 667C - Ребляндская лингвистика. Firstly, i am not able to comprehend that "How could I think in direction of reversing the string? (How could we know, that doing this would make it a DP problem?)". Also, i have tried implementing the method using pen paper, but still the intuition and approach towards the problem remains unknown to me. Thanks. Solution link http://codeforces.me/blog/entry/44622

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is no need to reverse the string.Proceed from backwards and maintain a set of unique strings. Now insert into the set the last substring of length two or three if its possible to do so.Maintain dp[i][j] as a boolean stating whether it is possible to make a substring starting from position i and j==0 means the length of string is 2 else 3.ed dp[10][0] of true means that we are able to print a string of length 2 starting at that point.

The transitions are:

// try to print substring of length 2 assume you are at position i

if dp[i+2][0]==1 means you have printed the string just check whether the printed string is equal to that of s[i]+s[i+1] if so you cannot print it and mark dp[i][0]=false if dp[i+3][0]==1 means you are able to print a string of length 3 starting at position i+3 so mark dp[i][0]=true and print the s[i]+s[i+1].

Repeat the same for length three and print the contents of the set.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    @javacoder1

    1. Why if the string already printed is equal to s[i] + s[i+1], we can't print it? We are already maintaining a set of strings, so we shouldn't be bothered about repetition.Right?

    2. Also, when checking for string length of 3, starting at position i+3, shouldn't we mark "dp[i][1] = true" as 'j == 0' corresponds to length 2 substrings?.

    3. Also, why exactly i am checking if the dp[i+2][0] == 1 when at index i, i am not getting the intuition behind doing this. Thanks.

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

      A value of 1 at either dp[i][0] or dp[i][1] for some i implies that some two or three length can be printed from that position , so we re using this fact. A value of 0 means that it is not possible and hence we are not printing dp[i-2][0] or dp[i-3][1] as the case may be.

      → Reply