Dividing K resources fairly to N people

Question

There are K points on a circle that represent the location of the treasures. N people want to share the treasures. You want to divide the treasure fairly among all of them such that the difference between the person having the maximum value and the person having the minimum value is as minimum as possible.

• They all take contiguous set of points on the circle. That is, they cannot own segmented treasures.
• All the treasures must be allocated
• Each treasure should only belong to only one person.

For example if there are 4 treasures and 2 people as shown in the figure, then the optimal way of dividing would be

(6, 10) and (11, 3) => with a difference of 2.

1 <= n <= 25

1 <= k <= 50

How do I approach solving this problem? I planned to calculate the mean of all the points and keep adding the resources until they are lesser than the mean for each person. But as obvious as it is, it will not work in all cases.

I'd be glad if someone throws some light.

Answer 1

So say we fix x, y as the min max allowed for the treasure. I need to figure out if we can get a solution in these constraints.

For that I need to traverse the circle and create exactly N segments with sums between x and y. This I can solve via dynamic programming, a[i][j][l] = 1 if I can split the elements between i and j into l whose sums are between x and y (see above). To compute it we can evaluate a[i][j][l] = is_there_a_q_such_that(a[i][q - 1][l-1] == 1 and sum(q -> j) between x and y). To handle the circle look for n-1 segments that cover enough elements and the remaining difference remains between x and y.

So naive solution is O(total_sum^2) to select X and Y plus O(K^3) to iterate over i,j,l and another O(K) to find a q and another O(K) to get the sum. That's a total of O(total_sum^2 * K^5) which likely is too slow.

So we need to compute sums a lot. So let's precompute a partial sums array sums[w] = sum(elements between pos 0 and pos w). So to get the sum between q and j you only need to compute sums[j] - sums[q-1]. This takes care of O(K).

To compute the a[i][j][l]. Since the treasures are always positive, if a partial sum is too small we need to grow the interval, if the sum is too high we need to shrink the interval. Sine we fixed a side of the interval (at j) we can only move the q. We can use binary search to find the closes t and the furthest q that allow us to be between x and y. Let's call them low_q (the closest to j, lowest sum) and high_q (far from j, largest sum). If low_q < i then the interval is too small so the value is 0. So now we need to check if there's a 1 between max(high_q, i) and low_q. The max is to make sure we don't look outside of the interval. To do the check we can precompute again partial sums to count how many 1s are in out interval. We only need to do this once per level so it will be amortized O(1). So, if we did everything right this will be O(K^3 logK).

We still have the total_sum^2 in front. Let's say we fix X. If for a given y we have a solution you might be able to find also a smaller y that still has a solution. If you can't find a solution for a given y then you won't be able to find a solution for any smaller value. So we can now do a binary search on y.

So this is now O(total_sum *log(total_sum) * K^3 * logK).

Other optimization would be to not raise i if the sum(0-> i- 1) > x. You might not want to check for values of x > total_sum/K since that's the ideal minimum value. This should cancel out one of the K is the complexity.

There might be other things that you can do, but I think this will be fast enough for your constraints.