O.S.Mozes's blog

Help? Anyone? (Hints for a problem)
By O.S.Mozes, history, 5 years ago, In English

Hello Codeforces,

I read this interesting problem a while ago and don't know how to solve it efficiently. Any hints?

Link to the problem

I tried mapping strings to states but that obviously sucks. Any help would be appreciated.

Thank you!

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

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This can be solved with dp in O(n3)

Say dp[i][j] is the number of possible ways to remove exactly substring [i, j]. Obviously, dp[i][i + 1] = (s[i] =  = s[i + 1]).

Now to calculate dp[i][j] let's check with which position was s[i] deleted. If we deleted s[i] with s[k], it has to be s[k] = s[i] and then we had to delete [i + 1, k - 1] separately (and, therefore, to delete [k + 1, j] separately. So we get dp[i + 1][k - 1] ways to delete [i, k] in this manner and dp[k + 1][j] to delete [k + 1, j]. Note that deletions in those substrings are independent and don't afffect each other. So to get total number of possible ways, we have to multiply this by . In total, we get the following dp:

Hope that helps

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

    Thank you so much for the detailed comment. The idea you described helps a lot.

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

Please tell me, how to create an account on that site?

→ Reply