andreyDagger's blog

By andreyDagger, history, 5 weeks ago, In Russian

Hi Guys, Can anyone help me solve this problem?

I tried to solve it greedily. Also i tried to solve it using dynamic programming. I had dp[l][r] true if exists k such that dp[l][k] is true and dp[k + 1][r] is true or dp[l + k][r — k] is true and we can connect letters from range (l, l + k) to the letters from range (r — k, r). Unfortunately, that works for O(n^3)

  • Vote: I like it
  • 0
  • Vote: I do not like it