diavolobia's blog

By diavolobia, 13 days ago, In English

I'm solving my school's DP problem set. Since it's not in English so I'll try my best to translate the problem.

There is a wall of N blocks ($$$N \leq 5000$$$), the block at the $$$i_{th}$$$ position has the color of $$$c_i$$$ ($$$1 \leq c_i \leq 5000$$$ for all $$$i$$$).

A painter needs to paint the so all blocks of the wall have the same color. It can be whichever color, it just needs to be the same for all blocks. One at a time, he does the following operation: Choose a segment of the wall, then use a color to paint all the blocks in that segment to the same color.

As a professional painter he knows that if he paints the same color to 2 blocks with different colors, the color will end up distorted, so he only paints a segment of which all the blocks have the same color. Because he is lazy, tell him the minimum operations he needs to paint the wall.

Sample input:
5 2 2 1

Sample output: 2

First he can paint the segment [2, 3] to color 5. The wall becomes 5 5 5 1.
Then he can paint the segment [1, 3] to color 1. The wall becomes 1 1 1 1.

I've came up with a DP solution that looks like this: Let $$$dp[l][r][k]$$$ be the minimum operations needed to paint the segment $$$[l, r]$$$ to the same color, with $$$k$$$ is a boolean to identify whether the segment should be painted to the left part's color or the right one.

My transition formula is:

$$$ dp[l][r][k] = \min_{i = l}^{r - 1} \left( \begin{array}{c} dp[l][i][0] + dp[i + 1][r][0] + (color[l][i][0] \neq color[i + 1][j][0]),\\ dp[l][i][1] + dp[i + 1][r][0] + (color[l][i][1] \neq color[i + 1][j][0]),\\ dp[l][i][0] + dp[i + 1][r][1] + (color[l][i][0] \neq color[i + 1][j][1]),\\ dp[l][i][1] + dp[i + 1][r][1] + (color[l][i][1] \neq color[i + 1][j][1]) \end{array} \right) $$$

where $$$color[l][r][k]$$$ is the color of the segment $$$[l, r]$$$ after being painted optimally. This formula has $$$N^2$$$ states and each transition costs $$$O(N)$$$, which makes the time complexity of this approach $$$O(N^3)$$$ — too slow for the problem's constraints.

Is there anything I can do to speed up the transition part? Or do I have to tackle this problem from a different approach?

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

13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Hello, i think I got a solution (this might be wrong).

Firstly, you can notice that if you have a segment of the same color (in the given array) you can treat it as a single number. Exemple : (5 5 6 7 2 2 3 3 3) this is the same as (5, 6, 7, 2, 3). This is because you can change the whole segment (with the same color in just 1 operation).

The state is dp[i][j] which means the minimum number of operations to turn the first i blocks into the same color.

Now, the transitions : You have 2 choices : 1) You dont change the color of the ith block : dp[i][j] = dp[i — 1][j] Here j needs to be the color of the ith block.

2) You change the color of the ith block : dp[i][j] = dp[i — 1][j] + 1; You need to do +1 because you change the color of the ith block

If you don't understand something feel free to comment. If you want the code i can send it with discord.

  • »
    13 days ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    I think that your solution is correct.

    The only point not mentioned in your comment is that the second index $$$j$$$ of the state $$$dp[i][j]$$$ is the final color of the first $$$i$$$ segments of consecutive blocks with the same initial color.

    The initial state should be $$$dp[0][j] = 0$$$ for $$$1 \leq j \leq 5000$$$.

    The required answer should be computed as follows after iterating on $$$i$$$ from $$$1$$$ to $$$k$$$ as follows.

    $$$\min\limits_{j=1}^{j=5000} dp[k][j]$$$

    where $$$k$$$ is the number of segments of consecutive blocks with the same color, and $$$1 \leq k \leq N$$$.

    The state-update equation can be expressed as follows.

    $$$dp[i][j] = dp[i-1][j]+(s[i]\neq j)$$$

    where $$$s[i]$$$ is the initial color of the $$$i$$$-th segment.

    • »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Does this not disregard cases where it is optimal to change an index twice?

      for example 01210 can be completed with 01210 01110 00000

      this feels like range dp?

      • »
        13 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yes, it does. Painting the block with color 2 twice brings the minimum number of operations down to 2, while the minimum number of operations using left-to-right scanning with painting at most once is 3. Thanks for this counterexample.

      • »
        13 days ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        My friends also came up with similar DP solutions but received wrong answer. Turns out Whimpers was right, their solutions didn't consider the case where it is optimal to change an index twice.

        Another problem with the solution is that it forces the whole segment from $$$[1, i - 1]$$$ to have the same color before changing, which isn't always the optimal answer (the optimal way might be painting the middle part first then change the outside later, like Whimpers' example). That's why my DP solution takes both $$$l$$$ and $$$r$$$ as parameters.

12 days ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

I found an O(n^2 log n) solution with a different approach (I think I overcomplicated this though):

First, remove all blocks next to each other with the same color. (Actually, this might not be necessary, but it probably optimizes things, and also it makes things simpler.)

Define a good segment (or GS) as a segment with endpoints of the same color without any blocks of that color within the segment other than the endpoints. In other words, for each block, you can form a GS to the nearest block to the left or right (if it exists.)

Then, if you make all the colors in a GS to be the same, this "subtracts" one move from the maximum number of moves, and this is the only way to reduce this. The maximum number of moves is gotten by just going through the segments left to right and setting the color of each segment to that of the one to the right. Using a GS reduces the number because it can combine three segments in one move, and it is the only way to combine three segments in one move- all other moves would combine only two segments. Thus, the problem is reduced to finding N minus the maximum number of used GSs.

Now, to find the number of used GSs, notice that GSs can have GSs inside of them. However, two GSs which overlap but where one is not inside the other cannot both be used, as using one would destroy an endpoint of the other. (Example- ABAB)

Then, the key is to find the maximum number of GSs in a GS. DP from smallest to largest GSs. Then, you don't need to consider GSs inside GSs because it is already computed. This reduces this subproblem (finding max GSs in a GS) to finding the maximum sum in GSs of non-intersecting GSs. To do this, go through GSs left to right based on the left endpoint and store a DP on the maximum sum for a right endpoint. Then you can use a segment tree to get the maximum sum before the left endpoint of each GS. (Also remember to use coordinate compression.)

Applying this to the whole wall (even though it's not necessarily a GS) solves the problem.

Edit- also you can prove that there are a maximum of N GSs because left endpoints are distinct (or right, doesnt matter cuz symmetric) this results in O(n^2 log n) actually cuz GSs*GSs*segtree. Might be even less tho idk maybe it could be reduced further with some optimizations