FairBandwidth | Topcoder Archive

Problem Statement

Some time ago, our company was smaller and we had less employees, so we shared the bandwidth equally among them, and if one of them was not using all his assigned bandwidth then the unused part was lost. However, in recent years, our number of employees grew a lot faster than our bandwidth, so there are now many employees with limited connectivity and others with unusued bandwidth, which is a poor use of a scarce resource.

For this reason, a new algorithm for bandwidth sharing must be implemented. Let's define an employee as satisfied if his assigned bandwidth is greater than or equal to his needed bandwidth. This new algorithm must be efficient and fair, which means:

If there is a satisfied user with unused bandwidth, there must be no unsatisfied users.
If a user is satisfied, all users that need less bandwidth than him must be satisfied too.
If a user is unsatisfied, then all users who need the same bandwidth as him or more must have the same assigned bandwidth as him.
Each unsatisfied user must have at least as much bandwidth as each satisfied user.

Create a method share that given the needed bandwidth by each user in a int[] needed and the total bandwidth available, returns a double[] with the same number of elements as needed, where the k-th element of the return value will be the assigned bandwidth to the k-th user.

Definition

Class:: FairBandwidth
Method:: share
Parameters:: int[], int
Returns:: double[]
Method signature:: double[] share(int[] needed, int bandwidth)
(be sure your method is public)

Notes

The returned values must be accurate to the correct results within a relative or absolute value of 1E-9.

Constraints

needed will contain between 1 and 50 elements, inclusive.
Each element of needed will be between 1 and 100, inclusive.
bandwidth will be between 1 and 5000, inclusive.
bandwidth will not exceed the sum of all elements of needed.

Examples

```
{20, 10, 40, 35}
```
```
102
```
```
Returns: {20.0, 10.0, 37.0, 35.0 }
```
We have enough bandwidth to satisfy users 0, 1 and 3, so we give the remaining 37 bandwidth to user 2.
```
{20, 10, 40, 35}
```
```
72
```
```
Returns: {20.0, 10.0, 21.0, 21.0 }
```
We could satisfy users 0, 1 and 3 and give the remaining bandwidth to user 2, but we would be breaking rule #4. To assign the bandwidth correctly, we must satisfy users 0 and 1 and give the remaining bandwidth to users 2 and 3.
```
{1, 20, 35, 13, 42}
```
```
4
```
```
Returns: {0.8, 0.8, 0.8, 0.8, 0.8 }
```
Even if we try to satisfy user 0, it is impossible because of rule #4, so we share our scarce bandwidth between all users.

{10, 22, 32, 7, 34}

Returns: {10.0, 22.0, 32.0, 7.0, 34.0 }

This time we can satisfy all the users.

{10, 24, 56, 63, 36, 75,
 12, 53, 23, 54, 12, 43}

Returns: {10.0, 24.0, 24.142857142857142, 24.142857142857142, 24.142857142857142, 24.142857142857142, 12.0, 24.142857142857142, 23.0, 24.142857142857142, 12.0, 24.142857142857142 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.