Painter Problem

#1

i tried the approach to this problem but my code is not working
here is my code https://ide.codingblocks.com/s/277217

#2

your approach is not correct
don’t increase your search space by multipling it with time
also your check function is not correct
also you have to print the answers after taking mod with 10000003
take help form reference code
Reference Code

if you have more doubts regarding this feel free to ask

i hope this helps
if yes hit a like and don’t forgot to mark doubt as resolved

#3

Bhai ekbar jo approach honi chaiye vo samjha do please

#4

@jatinupadhyay786
watch this video

this is for book allocation problem
both the problem book allocation and painter problem are of same kind
so watch this video and then try
you can also see the Reference code that i have provided to you
it’s a link click on that

#5

bhai video dekh ke he kia hai question mai 5 unit time lagega ek board ko paint karne mai toh last ko 5 se multiply kia matlab 50mera s hua and sum ko maine 5 se multiply kia 55 mera e hogaa toh yahi toh mera search space husa naa

#6

fir sir ne bola ki mid ko hum time se multiply karenge agar vo <= painter hua toh we will return true varna false?

#7

toh yahi toh kia hai maine bhi

#8

toh aprroach toh maine vaise he kia hai

#9

this will increase the search space size
it will create problem for large values

correct way to do this is use normal seach space
s=max element in array
e=sum of all element
and now find ans
after that multiply the time like this
return ((ans%mod)*time)%mod;
here mod is 10^7+3 as given in quesition

inside check function we have to use this logic

bool canPaint(ll boards[],ll n,ll no_painters, ll mid){
    ll painter=1;
    ll boardPainted=0;
    for(ll i=0;i<n;i++){
        if(boardPainted+boards[i]<=mid){
            boardPainted+=boards[i];
        }
        else{
            painter++;
            if(painter>no_painters)return false;
            boardPainted=boards[i];
        }
    }
    return true;
}

i think if you have watch the video you can understand this

complete code

#10

bool canPaint(ll boards[],ll n,ll no_painters, ll mid){

ll painter=1;

ll boardPainted=0;

for(ll i=0;i<n;i++){

    if(boardPainted+boards[i]<=mid){

        boardPainted+=boards[i];

    }

    else{

        painter++;

        if(painter>no_painters)return false;

        boardPainted=boards[i];

    }

}

return true;

}
bhai ye code kaise work kar raha hai samajh ni arraha ye smajha do given input ke context mai
yaha taak samjh aaya ki start mera=10 and end=11 hua mid mera 10 aaya sir ne video mai bola tha ki hum ek check function banaenge jisme hum mid ko divide karenge time se agar vo <= painter hua toh mid-1 karenge but yaha toh ye function banaya he nahi

#11

brother please help me out ye samjh he ni aara mujhe dry run karke bhi dekh lia

#12

in this code we are checking whether it is possible to paint the board
mid is max size of board a painter can paint

so we say we have 1 painter initially

ll painter=1;
ll boardPainted=0;

he starts painting the board

 for(ll i=0;i<n;i++){
        if(boardPainted+boards[i]<=mid){
            boardPainted+=boards[i];
        }

if it’s limit cross we come up with new painter

 else{
            painter++;
            if(painter>no_painters)return false;
            boardPainted=boards[i];
        }

but here
if(painter>no_painters)return false;
it is not possible to paint the board
so we return false

i hope this helps
if yes hit a like and don’t forgot to mark doubt as resolved :grinning:
if you have more doubts regarding this feel free to ask

#13

return ((ans%mod)*time)%mod;
ye kyu kia question mai ans ko mod kara tha sirf yaha mod karne ke bad time se multiply fir dobara mod kardia?

#14

ans *mod may overflow due to large values
so before multiply we have to take mod
and after that mod is also required as after multiplying it may also overflow