parth_cp_n0ob's blog

By parth_cp_n0ob, history, 5 weeks 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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Give me integer first,I will eat

»
5 weeks 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?

  • »
    »
    5 weeks 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 !

    • »
      »
      »
      5 weeks 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}$$$.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yaah, I understand. But I actually did also mention it in the problem statement, that the integers being divided among all the m people should be equally divisible. So, you cannot have a floating point output.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also, I'm Sorry about the 109 constraint. I didn't realise that I set it too high.

    Would 105 be a solvable limit ?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Okay, not gonna lie, but it's really demotivating to see these many downvotes on my first post. Please do post below on what doesn't feel right about the post. I'll be really happy to know how I could improve my post(s) !

»
5 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, even I couldn't find any way to do that.

    Also, the number of chosen elements could be <= k, as in, k is the upper bound on the number of elements that can be chosen together. This makes it even more tough for me to solve the question.