The Painter’s Partition Problem

 

Programming is a vast and challenging concept. But most of all, it is highly adaptable and versatile

for solving real world problems by using computer softwares and programs.

One such problem that we are tackling in this blog is the Painter's Partition Problem. In this particular programming problem we are provided a set of boards that needs to be painted by an undefined number of painters.

The catch here is that each painter can paint a single unit of the board at a time but they are only allowed to paint entire boards by themselves without the help of other painters.

This means that painter 1 can paint boards (1, 2, and 3) on his own without being helped by any of the other painters. 

So, which algorithms will help us in solving this problem? Let's find out in this blog! 

What is the Painter's Partition Problem in programming?

The Painter's Partition problem in programming is a pretty common problem that you might be required to solve during your coding interviews.

In this problem, each painter takes a single unit of time in order to paint a single unit of a board. The challenge is to calculate the amount of time it would require each painter to paint an entire board.

This problem can be effectively solved by using the Brute Force Algorithm where we will consider all the possible partition patterns. 

This will help in further calculating the maximum partition it would require for the painters to paint the given boards.

Also, an important factor to be noted here is that one painter cannot paint half of the board. This means that two painters cannot share a board to paint. 

Each painter will be allowed to paint contiguous boards, i.e if a certain painter paints boards 1 and 3 leaving the 2nd board, then the painting will be considered as invalid.

Since this is the naive approach the time complexity of this algorithm is exponential. There are other approaches as well that we will be discussing in the further sections of this blog.

What are the methods for solving Painter's Partition Problem?

From Brute Force to Overlapping Problems, there are a few methods that can be used for easily solving the Painter's Partition Problem.

But first, let's have a look at the problem statement for this problem.

Problem Statement:

You have been given 'n' number of boards to paint of lengths {A1, A2 … An}. There are 'k' number of painters to paint the given boards. Each painter takes about a single unit of time in order to paint a single unit of the board. 

Your task is finding the least possible time it would take the painters to complete painting all the boards while each painter is only allowed to paint the continuous sections of the boards. For example, boards {2, 3 and 4} must be painted by the same painter and so forth.

Answer Key:

Firstly we need to figure out the number of partitions that can be made:

• Single partition: The time taken would be 100

• Dual partition: (10) along with (20, 30 and 40), by doing so the time will be 90.

• Triple partition: We will put the first divider at 20 (so the time will be 70) or, we can also put the divider at 30 (so the time can be 60)

This basically means that the minimum time intervals can be either 100, 90, 70 or 60 

Now, let's check out the methods that can be used for solving the painter's partition problem.

Method 1: Brute Force Algorithm

The Brute Force Algorithm will take every possible contiguous pattern into consideration and calculate maximum sum partitions that can be made in each of the cases and return the minimum value for all of these cases.

Let us consider the algorithms for this approach:

• Start by implementing the naive solution for this approach by using the recursive approach

• Assume that you already have the k-1 partitions in accurate places, this can be attained using the k-2 dividers 

• Next up, we can place the k-1th divider in order to get the k partitions

• For this, place the k-1th divider in-between the ith and the i+1th elements where i will be equal to 1

• Hence, the maximum cost incurred of any partition will be applied towards the left of the k-1th divider. 

Time Complexity for this approach:

The time complexity for this solution will be exponential 

Method 2: By Overlapping the Subproblems 

The overlapping subproblems approach is also used to solve other programming problems such as, counting inversions, finding the root node of a BST and finding the next smaller element.

With regards to overlapping subproblems, we can certainly confirm that there are various subsets of the given problem that can be solved through and through.

By using dynamic programming, this problem can be solved by either implementing the bottom-up tabular method or the top-down memorized method.

Have a look at the algorithms for this approach:

• Write a function that will help in calculating the sum between two different indices in an array

•  Perform bottom up tabular function using Dynamic Programming

• After initialising the table, check for the base cases and add 2 to k partitions

• Track the minimum number of partitions that can be made and place the ith separator before the array

• Finally, perform the driver function to check whether all of the functions have been executed perfectly

Time Complexity for this approach:

O(k*N3) 

Last but not least we have a final optimization for this approach that can reduce the above mentioned time complexity to O(k*N2) by pre-analysing the cumulative sums within the array. This helps in avoiding repeated calls within the function.

Try performing this function on the Whiteboard to check if this is more accurate and less time consuming than the dynamic programming approach. 

Wrapping Up

Partition is a pretty common problem in programming that is often asked in technical interviews to test the logical thinking capacity of the candidates.

Other such problems that you might encounter during your coding interviews are, merging two sorted arrays, finding the root in a Binary Search Tree, or finding the next smaller element in n array.