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.
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.
What do you mean by last removal of [i+1, k-1]. How does it account for removing gemstones i and k ?
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.
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.
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].
Thank you all for your explanation! Understood the solution now.