The Painter's Partition Problem Part I

The Painter’s Partition Problem Part I

You have to paint N boards of length {A₀, A₁, A₂ … A_N-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

This is a problem which is fairly difficult. Try your very best to really think through it. You will improve your problem solving technique by struggling through it!

It turns out that this problem is the same as “FairWorkload” from TopCoder’s division 1 level 2 problem in SRM 169. If you find the problem statement above is difficult to understand, head over to TopCoder’s FairWorkload problem statement for a clearer description with examples. This problem is an interesting problem because it has several approaches, which I will outline them one by one here.

Read full article from The Painter’s Partition Problem Part I