Doubt in Book Allocation Problem

#1

Can you please tell why have we taken start=a[n-1] and not a[0] and Why have we take ans=min(mid,ans); because I think writing only ans=mid will also work.

#2

@sahilkhan2312000131 hey you can also take start = 0 and end = sum(all array elements). and since we are finding minimum distribution so thats why we take ans = mid(ans , mid).

#3

I tried submitting using start=0, but it is not passing any test case, and when I put start=a[n-1] it is passing all test cases. Can you please tell why?

#4

@sahilkhan2312000131 share your code i will check it

#5

#include<bits/stdc++.h>
using namespace std;
bool ismid(int a[],int n,int m,int mid){
int students=1,pagesread=0;
for(int i=0;i<n;i++){
if(pagesread+a[i]>mid){
++students;
pagesread=a[i];
if(students>m)
return false;
}

    else pagesread+=a[i];


}
return true;

}
int main() {
int t;
cin>>t;
while(t–){
int n,m;
cin>>n>>m;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}

	int s=a[n-1],e=accumulate(a, a+n,0),ans;
	while(s<=e){
		int mid=(s+e)/2;
		if(ismid(a,n,m,mid)){
            ans=mid;
			e=mid-1;
		}
        else s=mid+1;
	}
    cout<<ans<<endl;
}
return 0;

}

#6

hey @himanshu_aswal can we please solve this query??

#7

@sahilkhan2312000131 i have made some changes in your code

#8

Your code is giving multiple errors.
My code was already correct I just wanted to ask why we do not pass the test cases if we take start =0;

#9

@sahilkhan2312000131
“The task is to assign books in such a way that the maximum number of pages assigned to a student is minimum.”

solution expected: max no of pages assigned to a student
task: to minimize the expected solution

eg. we have 4 books with 10,20,50,60 pages and have m=3.
possible solutions:

  1. {10+20, 50,60}, ans = 60
    2,{10+50,20,60} , ans = 60
  2. {10,20,50+60}, ans = 110(max no of pages a student get = 110)
    …so on
    final ans = in best case(min of all possible solutions), how many max pages a student will get = 60

eg2. 10,20,30,90 and m=2
possible solutions:

  1. {10+20,30+90}, ans = 120
    2.{10+20+30,90}, ans = 90
  2. {10+30,90+20}, ans = 110…so on
    final ans = min of all possible solutions = 90

you can see that the final answer can never be less than the largest book. since atleast some student will get that book and then the solution can never be less than that.

#10

hey @himanshu_aswal
I am explaining my question for the 4th time, please answer this only and not the entire approach.
Question is even if I take start=a[0] the answer should be same but when we submit it, it does not pass any test case. Please explain this thing not the entire question.

#11

@sahilkhan2312000131
because if the no of students is equal to no of books in that case each student has to read 1 book in that case the last student has to read maximum no of pages so that all books are read ( array is sorted ) so the search space starts from s = max of element in array since atleast 1 book is being read by the student

#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.