determinism's blog

UVa 1261 — String Popping | Analysis of Complexity
By determinism, 10 years ago, In English

I couln't analyse the complexity of this solution to this problem. Can someone explain why even simple recursive approach doesn't get TLE?

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

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Maybe it's because the maximum length of the string is 25? Though you can solve this problem with dynamic programming in O(N3) with the same recurrence relation using memoization.

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

    There are 2^26-2 = 67108862 states, and what you do in one state is linear. Can you explain why it's O(N^3)?

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

      Let dp(i, j) be a boolean function that tells us if we can reduce the substring s[i][j]. Also define function l(i) and r(i), where l(i) the largest index j ≥ i such that s[i] = s[i + 1] = ... = s[j], and l(i) as the lowest left index with the mentioned property.

      Now here's the code for the recurence:

      dp[i][j]=0;
if (r[i]>i) dp[i][j]=dp[r[i]+1][j];
for (k=r[i]+1; k<=j; k++)
    if (s[i]==s[k])
       dp[i][j]=dp[i][j] | (dp[r[i]+1][l[k]-1]] & dp[k+1][j]);

      (There are also some cornes cases)

      We observe that if r(i) > i then we can transition to state dp(r(i) + 1, j) and see if we can reduce the substring s[r(i) + 1, j]. But also we can combine the substring s[i][r(i)] with some other substring s[x][y] if all their characters are equal. So we are left to reduce s[r(i) + 1][x - 1] and s[y + 1][j]. We use r(i) and l(x) because it's always better to pick these indeces instead of fixing the right point of an interval and try to extend it to the left until we get to a different character.

      I know that I worded it pretty badly, but try to simulate the recurrence on the examples and it should become clear why this kind of approach works. (but take notice, I'm not 100% sure that this solution is correct)

      → Reply