No test case working, Please find the mistake with this approach

#1

Sharing my code using CB IDE

#2

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.

#3

I am sorry to say this but I haven’t received your suggestion on the code.
Please give your suggestion about this approach
I understood the approach taught in the lecture
But what is the problem with this approach

#4

Sorry, but i think this was sent by mistake. Can you please post the question also, so that i can help you

#5

You are given number of pages in n different books and m students. The books are arranged in ascending order of number of pages. Every student is assigned to read some consecutive books. The task is to assign books in such a way that the maximum number of pages assigned to a student is minimum.

Input Format

First line contains integer t as number of test cases. Next t lines contains two lines. For each test case, 1st line contains two integers n and m which represents the number of books and students and 2nd line contains n space separated integers which represents the number of pages of n books in ascending order.

Constraints

1 < t < 50
1< n < 100
1< m <= 50
1 <= Ai <= 1000

Output Format

Print the maximum number of pages that can be assigned to students.

Sample Input

1 4 2 12 34 67 90

Sample Output

113

Explanation

1st students : 12 , 34, 67 (total = 113)
2nd students : 90 (total = 90)
Print max(113, 90)

#6

Name of the problem: Book Allocation Problem

#7

After seeing your code, I can understand that you are applying binary search. Your approach is definitely correct, just missing some cases in my opinion.

I am sharing my code for this problem you can refer that for help.

what to do:

1. sort the array of no. of pages.
2. now the book with the maximum number of pages is at a[n-1]. So the monotonic search space is from a[n-1] to sum of all pages, which means that you can read only one book with maximum pages or you can read all books or anything between them.
3. then i applied binary search and found that if i can read that number of pages or not. if i can, then searching on the left side is useless as we can read more pages then them already. then we search in right and keep doing this until we found the maximum.

look at the code and i can guarantee you that you can understand that easily.

Thanks.

#8

if you think that i cleared your doubt, then you can please mark this as resolved now, and please give feedback on the above link.

#9

Hi, I understood the approach but still I had some questions:
1 Why are we doing min(ans,mid) Why can’t we just write ans = mid; Because every time we are able to find max number of pages for which we can assign all the students with books properly then we are just going to the left of it, Which inturn in the end would give us the minimum possible ans

  1. Suppose for this case:
    Number of books: 40
    Number of students: 3

books array: 10 20 30 40
So it means that we have to assign these 4 books to 3 students in such a way that max pages of books assigned to student is min
So possiblities: 1. Student 1: 10+20 = 30 Student 2 = 30 Student 3 = 40
2nd Possibility: Student 1= 10 Student 2 = 20+30=50 Student 3 = 40
3rd Possibility: Student 1 = 10 Student 2 = 20 Student 3=70
So min is 40.
I am asking this question because I am still confused that I understood the problem completely or not
So for this case ans should be 40 ?

#10

WhatsApp Image 2020-08-14 at 13.55.21
WhatsApp Image 2020-08-14 at 13.55.21962×1280 97 KB

#11

Thanks I understood the problem completely
Thank you so much for your assistance :heart:
Marking as resolved

1 Like