i am not able to understand the painter problem question given please illustrate the sample input and output
Painter problem question in challenges
We know that the invariant of binary search has two main parts:
the target value would always be in the searching range.
the searching range will decrease in each loop so that the termination can be reached.
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.
We can see that the highest possible value in this range is the sum of all the elementsin the array and this happens when we allot 1 painter all the sections of the board. The lowest possible value of this range is the maximum value of the array max, as in this allocation we can allot max to one painter and divide the other sections such that the cost of them is less than or equal to max and as close as possible to max. Now if we consider we use x painters in the above scenarios, it is obvious that as the value in the range increases, the value of x decreases and vice-versa. From this we can find the target value when x=k and use a helper function to find x, the minimum number of painters required when the maximum length of section a painter can paint is given.
Can you explain the order in which we took in the sample Input and then how the sample output is computed?
I think something is wrong in the sample I/P
First line must be the number of boards, next line must be the time taken by the painter to paint 1 unit of board and the last line must be the array of board length…
https://hack.codingblocks.com/contests/c/452/716
in the problem statement it is mentioned that “each painter takes 1 unit of time to paint 1 unit of boards i.e. if the length of a particular board is 5, it will take 5 units of time to paint the board.”
This problem has a different problem statement…the one in the challenges section of my Algo++ course is different…i have posted its screenshot…can you verify the question…Sample Output for it is 50.