Can anyone help me with this dynamic programming problem. The problem is 225C - Штрихкод. I can't get the solution from editorial.

Before contest

Codeforces Round #647 (Div. 1) - Thanks, Algo Muse!

24:47:03

Register now »

Codeforces Round #647 (Div. 1) - Thanks, Algo Muse!

24:47:03

Register now »

*has extra registration

Before contest

Codeforces Round #647 (Div. 2) - Thanks, Algo Muse!

24:47:03

Register now »

Codeforces Round #647 (Div. 2) - Thanks, Algo Muse!

24:47:03

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 193 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | tourist | 166 |

6 | Um_nik | 165 |

7 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 161 |

10 | Geothermal | 158 |

Can anyone help me with this dynamic programming problem. The problem is 225C - Штрихкод. I can't get the solution from editorial.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/03/2020 16:47:58 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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: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.

Note that in editorial they are reversed by mistake)`dp[0][0] = dp[1][0] = 0`

— obvious answer for zero columns.`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]`min(dp[0][M], dp[1][M])`

Feel free to ask if you cannot understand something.

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

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

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.

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.

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

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++){

}

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.

Got it. Thank you very much. Much obliged. God bless you!

but what if j > i