Integer eating problem

Revision en5, by parth_cp_n0ob, 2021-09-18 10:02:08

Problem

Given an array of size n consisting of positive integers. There are m persons. Each person can eat one integer at a time, where the time taken by each to eat the integer is equal to the value of the integer. It is given that the m persons can eat k integers together and divide the integer equally amoung themselves, reducing the time taken to eat the integer to (a1+a2+...+ap) / m, where p <= k.

For example :

If the integers are [ 1, 3 , 5 , 8 ], m = 4 and k = 1, the one of the ways by which the 4 people could eat the integers could be, to have one inetegr each, in which the total time would be 1 + 3 + 5 + 8 = 17. Another way could be to feed all four people the integer 8, as the limit is 1, and so the total time would be 1 + 3 + 5 + (8/4) = 11, which is also the minimum time which the 4 people could have taken to eat all the integers.

Given, n, m, k and the list of all n integrers, find the minimum possible time in which the integers can be eaten up.

My Solution

My approach was to first sort the array in non-decreasing order, and start a recursive search from (N-1)th index. At each recursive I would have two branches, in one I would assume the current element was eaten by just one person, and in the other branch add the value to the sum of all integers which will be eaten by all m people, and also reduce the value of k by 1 in the next recursive call. Then in the base case of (k == 1 || index = -1), assume all remaining elements to be eaten by a single person, and return (sum + batch_eating_sum / m ) only if batch_eating_sum can be equally divided among all m, if not, add them to the sum as well assuming all are being eaten by one person each. I also take min of both the branches.

This solution seems fine to me. But I'm afraid this seems to be an O(2n) solution, and n can be as large as 105, so this might fail in those cases.

I was then thinking of two possible approaches :

  • One could be to keep a track of recursive calls which we have already seen, and not compute them again, but I can't seem to figure out what they exactly are.
  • I then though if this problem could be boiled down to somthing like number of subsets of an array which add up to a number S, which in this case could be, subsets of length <= k which are a multiple of m.

But, I couldn't make any progress in any of the two.

Do let me know your views on what your approach would have been !

Thanks !

Tags #arrays, #math, # dp, #constructive algorithms, #recursion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English parth_cp_n0ob 2021-09-18 10:02:08 21
en4 English parth_cp_n0ob 2021-09-18 06:29:29 2 Tiny change: 'as 10<sup>9</sup>, so' -> 'as 10<sup>5</sup>, so'
en3 English parth_cp_n0ob 2021-09-18 06:11:12 4
en2 English parth_cp_n0ob 2021-09-17 21:48:11 10 typo fix
en1 English parth_cp_n0ob 2021-09-17 21:34:52 2565 Initial revision (published)