Painters problem question

#1

sir can u explain me the logic of painters problem i am not able to understant it

#2

Question:
Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.

Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.

From the above examples, it is obvious that the strategy of dividing the boards into k equal partitions won’t work for all the cases.

We can observe that the problem can be broken down into:
Given an array A of non-negative integers and a positive integer k, we have to divide A into k of fewer partitions such that the maximum sum of the elements in a partition, overall partitions is minimized. So for the second example above, possible divisions are:

  • One partition: so time is 100.We also know that the values in this range must be in sorted order. Here our target value is the maximum sum of a contiguous section in the optimal allocation of boards. Now how can we apply binary search for this? We can fix the possible low to high range for the target value and narrow down our search to get the optimal allocation.
  • Two partitions: (10) & (20, 30, 40), so time is 90. Similarly we can put the first divider
    after 20 (10 20 and 30 40 => time 70)
    after 30 (10 20 30 and 40=> time 60);
    so this means the minimum time: (100, 90, 70, 60) is 60.

this is brute force approach now to optimize it we can use binary search

Now how can we apply binary search for this?
We can fix the possible low to high range for the target value and narrow down our search to get the optimal allocation.

i hope this help
if you have more doubts regarding this feel free to ask
if your doubt is resolved mark it as resolved from your doubt section inside your course