Блог пользователя ps06756

Автор ps06756, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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