current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

I've been trying out the dp tutorials on Topcoder. One of the problems given for practice was MiniPaint . I think I've got the solution partly- find the minimum no. of mispaints for a given no. of strokes, for each row and then compute for the entire picture (again using dp, similar to the knapsack problem). However, I'm not sure how to compute the min. no for each row.

P.S I later found the match editorial, but the code for finding the min. no. of mispaintings for each row seems wrong. Could someone explain exactly what they've done in the code?

share|improve this question
    
What have you tried? –  Matt Clark Feb 7 '13 at 6:25
    
I just did the basic recursive algorithm. I bunched up continuous colours in a row into 1 and wrote the sequence in a new array. I then found out the min. number of mispaintings in a given row, for a given number of strokes, till the number of mispaintings is zero. For example - for "wwbbbwww" - With 0 strokes, we have 8 mispaintings. With 1 stroke, we have 3 mispaintings (colour the whole thing white). With 2 strokes, we have 2 mispaintings and finally, with 3 strokes, we have 0 mispaintings (stop). However, I'm not sure what optimal substructures to use for the dp sol. here. –  user1968919 Feb 7 '13 at 8:59

1 Answer 1

up vote 0 down vote

The stripScore() function returns the minimum number of mispaintings for each row given the amount of strokes available to paint it. Although I'm not sure if the rowid argument is correct, the idea is that starting at start at a particular row with needed amount of strokes available to use and the colour of the region directly before it.

The key to this algorithm, is that the best score for the area to the right of the kth region, is uniquely determined by the number of strokes needed, and the color used to paint the (k-1)th region.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.