Can anyone tell the approach to solve Army and Packets Problem Code: AYPA

problem link

Please help

It looks like n^2 m*t should pass.
The answer for 200 and 35 is the minimum
Of max(sum(bomb in packet), solve(n-packet,34)
That should solve it i guess

Please elaborate your explanation

Time complexity =O(n^2 *m *t)
Let solve(i,j) denote the answer for last i elements and j people
Test case
4 3
10 20 30 40
Start with solve(n=4,m=3)
It is equal to minimum of
It shouldnt go to solve(1,2) because it is impossible to distribute 1 packet to 2 people
Now we have solve(3,2)
N=3 m=2
20 30 40
Min of
Solve(i,1) should just return the sum of the last i elements because only one person is left to receive.
So it is 50
2 2
30 40
This has only one case
Max(30,solve(1,1)) which equals 40
Put these values in the start
Minimum of
Which equals 40

1 Like

I got it thanks man.

This problem can also be solved with Time Complexity : O(N*log(Sum))*t sum is sum of all elements.


since n is small in this problem so nnm*t will give better time complexity