WinstonWolf's blog

how to prove that a dp solution state is wrong in general?
By WinstonWolf, history, 7 years ago, In English

I'm stuck in this problem 225C - Barcode

Here is my solution 33821210

I tried to calculate the array dp[current_column][width_of_current_group][hash_or_dot], and after i read the tutorial saying that i should calculate only dp[current_column][hash_or_dot] i didn't figure out why my solution was wrong.

I think they are the same, can't see any difference... can somebody help?

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by WinstonWolf (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Both solutions have the same idea .. but yours uses more memory in vain. So either there's a bug in your code or you have a wrong dp state.

We have dp[pos][type][how_much] means that you're in the [pos] column and now you're trying to fill it with [type] (white or black) and you have [how_much] of them from previous columns, and it returns the minimum possible of pixels to repaint till the end.

dp[pos][type][how_much] = dp[pos + 1][type][how_much + 1] + arr[pos][type ^ 1]

And if (x <= how_much <= y) dp[pos][type][how_much] = min(dp[pos][type][how_much], dp[pos + 1][type ^ 1][1]+arr[pos][type]);

Where arr[pos][type] refers to number of white or black pixles in the column [pos].

So the answer is min(dp[0][1][0], dp[0][0][0]).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks for your help :)

    It was one silly fault in my implementation :"D

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

The following submission using C++ STL arrays and based on the problem tutorial may help you to improve the readability and efficiency of your solution.

33832273

Please note that computing the number of black and white pixels between columns 1 and j inclusive is done prior to the DP main loop. The result is then used to compute the number of black and white pixels between columns j and i inclusive in O(1) time using a simple subtraction operation.

Best wishes

→ Reply