Painter partition problem

#1

Hey i have unlocked the tutorial of this problem but i am still not able to understand the approach . Can you share a simpler approach

#2

here i am explaining the Problem and its solution

Problem:
You have to find the min time require to paint all boards

Solution
min time to paint the board = time taken by that painter who is painting max no of boards

boards[] = {12, 34, 67, 90}
No of painters = 2

There are 2 number of paiters. boards can be distributed in following fashion :

  1. [12] and [34, 67, 90]
    Max number of boards is allocated to painter
    2 with 34 + 67 + 90 = 191 boards
    we can say that the time require by 2nd painter is the total time
    because in the same time painter 1 can finished his task
  2. [12, 34] and [67, 90]
    Max number of boards is allocated to painter
    2 with 67 + 90 = 157 boards
  3. [12, 34, 67] and [90]
    Max number of boards is allocated to painter
    1 with 12 + 34 + 67 = 113 boards

from the above distribution we can say that min time is taken in 3rd case

so first we have to minimize the max no of boards assigned to 1 painter
after that if we get the max no of board painted by 1 painter(lets say painter px will paint these boards)
then time requried to paint these board will be the total time
because when px paint these boards meanwhile (on the same time) other painters also paint the boards assingn to them

and to find the max no of boards assigned to painter(minimized) we can use binary search

look at reference Code
Reference Code

if you want to ask something about this feel free to ask
i hope this helps
if yes show your response with :heart: and don’t forgot to mark doubt as resolved

#3

https://ide.codingblocks.com/s/245741?_ga=2.99799518.1135539697.1622364051-601025507.1597674626 hey this is eko spoj problem can u explain me the line no 12 and 13

#4 
if(a[i]-mid>0){

            sum=sum+(a[i]-mid);

here if difference is positive we are getting it to sum

#5

in the line no 27 of your shared code , can we initialise start as we had done previously in book allocation problem ?

#6

Why have u initialised end as (s+e-s)/2

#7

Hey sorry for bothering you again , https://ide.codingblocks.com/s/314596 i tried writing this on my own and it is throwing some strange error

#8

ll mid= s+(e-s)/2;
this is same as mid=(s+e)/2;
i have done in that way to avoid overflow

you can use anyone

#9

this code link is mine
plz share your code i will check

#10

https://ide.codingblocks.com/s/489156 here it is

#11

Sometimes tutorials can feel a bit overwhelming, especially when the explanation gets too technical. I totally get where you’re coming from! On a different note, if you’re looking for something relaxing and rewarding to balance the mental load, I’d recommend trying Customised Paint By Numbers . I recently gave it a shot, and the results were incredible! It’s a fun way to take a break while creating something beautiful. Highly recommend checking them out!