On Jun 16, 2:1@shubham
couldnt understand following logic in you algo please explain
"when first k elemnts traversed then traverse again k elemnts of B
and
S[2*k-i]+=B[i])...again S[i-2*k]+=B[i][.so on till B is traversed
completely."
6 am, Shubham Sandeep <s.shubhamsand...@gmail.com> wrote:
> wat constraints does dis bring in the question... "Also the books are
> arranged in a certain order and this order must never be changed."
> does this imply ---> a student gets only consecutivly numbered book
>
> if not then---->
> sort the array B in decreasing order in Onlogn
> take another array S of k elements
> traverse B(sorted)
> S[i]=B[i]
> when first k elemnts traversed then traverse again k elemnts of B and
> S[2*k-i]+=B[i])...again S[i-2*k]+=B[i][.so on till B is traversed
> completely......
>
> On Sat, Jun 16, 2012 at 2:22 AM, Hemesh Singh <hemesh.mn...@gmail.com>wrote:
>
>
>
>
>
>
>
> > At first look it appears to be a simple problem of discrete binary
> > search. Take sum of b[i] as the upper_bound and 0 as the lower bound. Then
> > apply a simple binary search for the number of pages that can be given to a
> > student. Complexity : O(N log( sum( B ) ) )
>
> > On Thu, Jun 14, 2012 at 12:26 PM, algogeek
> > <dayanidhi.haris...@gmail.com>wrote:
>
> >> In a library there are N books with the number of pages in i th book
> >> given by bi . These books are to be distributed among K students such that
> >> the difference between the largest sum of pages in the books assigned to
> >> any student and the smallest sum of number of pages in the books assigned
> >> to any student is minimum for the given input. Also the books are arranged
> >> in a certain order and this order must never be changed.
> >> For eg:
> >> suppose B[ ] contains the number of pages in each book.
> >> then
> >> N=6
> >> K=3
> >> B={3,7,8,2,6,4}
>
> >> then the output will be 0 as we can give book 1 and 2 to student 1 and
> >> book 3 and 4 to student 2 and the remaining to student 3. That makes 10
> >> pages for student 1 10 for 2 and 10 for 3 and thus the difference is 0
>
> >> similarly if B={3,6,8,2,6,4} then the minimum difference will be 1 .
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To view this discussion on the web visit
> >>https://groups.google.com/d/msg/algogeeks/-/JjKITS_gN9UJ.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Hemesh singh
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
