Problem Link:- CodeChef: Practical coding for everyone
EDITORIAL:
-
Difficulty:- Hard
-
Pre-requisites:- Binary Search, Theory of Permutation
-
Explanation:- Given number of explosives in n different packets and m soldiers. The packets are arranged in ascending order of number of explosives. Every soldier is assigned to use some consecutive explosives. The task is to assign packets in such a way that the maximum number of explosives assigned to a soldier is minimum.
Example :
Input : packets[] = {10, 30, 60, 90}
m = 2
Output : 100
Explanation:
There are 2 number of soldiers. packets can be distributed
in following fashion :
-
[10] and [30, 60, 90]
Max number of explosives is allocated to soldier
2 with 30 + 60 + 90 = 180 explosives
-
[10, 30] and [60, 90]
Max number of explosive is allocated to soldier
2 with 60 + 90 = 150 explosive
-
[10, 30, 60] and [90]
Max number of explosive is allocated to soldier
1 with 10 + 30 + 60 = 100 explosives
Of the 3 cases, Option 3 has the minimum explosives = 100.
The idea is to use Binary Search. We fix a value for the number of explosives as mid of current minimum(start) and maximum(end). We initialize minimum(start) and maximum(end) as 0 and sum-of-all-explosives respectively. If a current mid can be a solution, then we search on the lower half, else we search in higher half.
How to check if a mid value is feasible or not? Basically, we need to check if we can assign explosives to all soldiers in a way that the maximum number doesn’t exceed current value. To do this, we sequentially assign explosives to every soldier while the current number of assigned explosives doesn’t exceed the value. In this process, if the number of soldier becomes more than m, then the solution is not feasible. Else feasible.