ssesamyak's blog

By ssesamyak, history, 5 years ago, In English

Problem Link:- C-Barcode My Code :- My Code

Ive been struggling for 5 hours straight and I'm still not able to find the solution to and get an AC in the problem . You can get the question above . My approach is just like the editorial

Approach : let's look on Nxi rectangle formed with the first i columns. What can we say about its last stripe? Either it's black or white and his width is ranged from x to y. Let's imagine the last stripe in your subrectangle is white. It means that previous stripe's color has to be the different (black). Then, for each a x <= a <= y check the cost of oainting rectangle Nx(i-a) in stripes so it will end with the black stripe (dp[1][i-a])and add the cost of painting columns from i-a+1 to i in white (sum-of-whites(i-a+1,i)). Then we keep the best outcome.

Same thing with the case, where the last stripe in rectangle Nxi is white, but with reverse colouring.

I'm Not able to get the answer , somebody Please help . :frowning_face::frowning_face:

  • Vote: I like it
  • -9
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Have you tried the following:

  • Make a very simple and naive solution that is clearly correct (even though very slow);
  • Make program that generates thousands of small test cases;
  • Compare your output with its outputs.