ps06756's blog

By ps06756, history, 9 years ago, In English

Hello all, I am trying to understand the algorithm mentioned in the editorial for the following problem
Zuma Here is its editorial editorial.

In the case, when the ith color matches with the kth color in the range [i...j], shouldn't we be doing

D[i][j] = D[i+1][k-1] + D[k+1][j] + 1, instead of
D[i][j] = D[i+1][k-1] + D[k+1][j]
?

This is because, we have to destroy the matching characters in ith position with kth position also, which will take 1 step extra.

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

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

It's a valid question, or it would be, if it wasn't explained in the editorial — "We can reduce to the subproblem [i + 1, k - 1] because we can just remove gemstones i and k with the last removal of [i + 1, k - 1]".

In other words, if only [i+1,k-1] is non empty, we will destroy it using some optimal sequence of moves, and we can extend the last move with the pair (i,k). So yes, we get this pair for free.

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

    What do you mean by last removal of [i+1, k-1]. How does it account for removing gemstones i and k ?

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      The last string which you remove from [i+1, k-1] is a palindrome. But i and k gemstones are same, hence if you include these gemstones in that palindrome, it would still be a palindrome.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      You can forget about i and k for a moment, and imagine executing the optimal solution on [i+1,k-1]. You will be removing some palindromes, and then, there will be some last move, which will erase everything left in [i+1,k-1].

      That means, that before the last move, stuff left in [i+1,k-1] was a palindrome. Then you can remember that you also have gemstones i, k on the sides, and you can remove them for free, because then [i,k] will also be a palindrome.

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Imagine the last subsequence we'd delete to completely destroy the segment [i+1; k-1]. Because this subsequence will be deleted last, this is definetely a palindrom. So if we add i-th and k-th characters in the beginning and in the end of this subsequence, it will still be a palindrome (because i-th and k-th characters have the same color). That's why "destroying" the same characters doesnt actually takes extra step — they will be added to some other subsequence.

P.S. This is only correct if i+1 != k, otherwise this will take 1 step to destroy this segment, because there are no palindromes in segment [i+1; k-1].

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

Thank you all for your explanation! Understood the solution now.