CSES Problemset Array Division Help required

Revision en1, by jmdons, 2020-07-08 16:40:28

Can someone please help me understand the below solution.

Problem statement --> Array Division

Solution on GitHub --> Solution Here

After mulling over it and trying to find out what the code does leaves me with the following understanding.

A binary search is used to find the desired maxnumber which obviously lies between max(array) and sum of all elements of the array.

somehow only for the desired maxnumber the number of sets (counter) calculated with the condition equals the input k:

if (currentsum + currentelement > maxnumber)
    counter++;
    currentsum = 0;

Can someone please explain to me the relation between the maxnumber and number of sets (k), which is exploited in this solution ? It would be of immense help. Thanks in advance!

Tags c++, cses, partition, array division

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English jmdons 2020-07-08 16:40:28 988 Initial revision (published)