parth_cp_n0ob's blog

By parth_cp_n0ob, history, 3 years ago, In English

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 !

  • Vote: I like it
  • -26
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

and n can be as large as $$$10^9$$$

If n = 10^9, then this is an unsolvable problem, since you need to read 10^9 integers.

If serious, why the answer is not $$$\frac{\sum\limits_{i = 1}^n a_i}{m}$$$? And what is $$$k$$$, that is not mentioned in the statement but mentioned in the example?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    k is the number of integers that can be divided among all persons and eaten, so the time taken to just eat those optimally selected integers is ( a1 + a2 + ... + ap ) / m, where p <= k.

    I think the answer is not just the division of sum of all integers by m, because sometimes grouping some of the integers might result in a multiple of m, which might minimise the answer.

    p.s. This problem is something I thought of on my own, so it might not be framed very correctly. Please feel free to make assumptions as and when required.

    Let me know what you think about it !

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Well, if four people will <> number $$$17$$$, will they do it in 4.25 sec, or in 5 sec?

      If in 4.25 sec, so the solution is still $$$\frac{\sum\limits_{i = 1}^n a_i}{m}$$$.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

According To Me:
Your question reduces something like this:
Given an integer array of size n, and two integers m and k.
You need to find out k elements such that their sum is divisible by m. And the sum of k elements is as large as possible.
Then the answer would be "Sum of n-k elements + (sum of k chosen elements)/m)".
And if there doesn't exist such k elements then the answer would be "sum of all elements".
But I don't think choosing k elements is possible in linear time or polynomial time or at least I am not able to find on the net.