lama_codes's blog

By lama_codes, history, 4 years ago, In English,

Can anyone help me with this dynamic programming problem. The problem is 225C - Barcode. I can't get the solution from editorial.

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

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

First of all, we construct array of partial sums to calculate amount of pixels in some columns of some color in O(1). Let it be array w[]. w[i] — amount of white pixels in columns [1..i]. For each column we calculate amount of white pixels in it. Then, w[0]=0; w[i]=w[i-1]+amount_of_white_pixels_in_column_i; Example:

      # . # .
      . . # #
      # # # #
w[i]: 1 3 3 4

Now, amount_of_white_pixels_in_columns [i..j] = w[j]-w[i-1]; amount_of_black pixels_in_columns [i..j] = (j-i+1)*N - amount_of_white_pixels_in_columns [i..j];

Now, lets build dp solution.

  • Function: dp[i][j] — minimal amount of re-painted pixels to obtain a barcode in columns [1..j] and last column color is i. Color is white if i==1, black if i==0 ( Note that in editorial they are reversed by mistake )
  • Base values: dp[0][0] = dp[1][0] = 0 — obvious answer for zero columns.
  • Transitions: dp[0][j] — we are re-painting column j into black. Now we must paint in black from X to Y last columns. Consider all possible cases and find one that takes minimum re-paintings. Let's iterate a from X to Y. To make last a rows black, we must re-paint amount_of_white_pixels_in_columns [j-a+1..j] (see first part) white pixels. Also, we need re-paint columns [1..j-a] so that column j-a is white. This is dp[1][j-a]. Similarly calculate dp[1][j]
  • Answer: Answer is obviously min(dp[0][M], dp[1][M])

Feel free to ask if you cannot understand something.

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

    Thank you so much to take the time out to write such precise explanation. It helped me a lot. God bless you.

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

So, you are given a nxm pixel picture. Now, you need to make a barcode picture by changing minimum number of pixels .

  1. For a certain column you will either change every pixel of that column into black or white.To make every pixel of that column black : cost = number of white pixel of that column and vice versa.

  2. now suppose you are in Kth column. Now dp[0][K] means minimum number of pixels needed to make a barcode picture and the color of last bar is Black(width of last bar can be x to y). And we only got the ans for 1 to Kth column.

  3. So, to minimize complexity precompute. Let, preBlack[I][J] means number of Black pixels from Ith column to Jth column.

preWhite[I][J] is vice versa . Complexity : nm

  1. now iterate through every column for every column take the minimum ans from all possible width of last bar and save ans.

    for(I=1;I<=m;I++){

    int Min1=inf,Min2=inf;

    for(J=x;J<=y;J++){

    Min1=min(Min1,dp[1][I-J]+preWhite[I-J+1][I]);
    
      Min2=min(Min2,dp[0][I-J]+preBlack[I-J+1][I]);

    }

    dp[0][I]=Min1;

    dp[1][I]=Min2;

}

Now the ans will be min( dp[0][m] , dp[1][m] );

Think about it a little bit.