Sunday, June 29, 2014

Bonuses

Problem:
Overview:

Determine the amount of bonuses to award to each employee.

Java Source:
```    01: /*
02: TopCoder
03: Single Round Match: 145
04: Division: 1
05: Level: 1
06: Points: 250 Points
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1677&rd=4530
08:  */
09:
10: public class Bonuses {
11:
12:     public int[] getDivision(int[] points) {
13:
14:         // An array to store the bonus amounts.  This is the return value.
15:         int[] bonuses = new int[points.length];
16:
17:         // Used to keep track of employees that received the "extra" bonus.
18:         boolean[] extraBonus = new boolean[points.length];
19:
20:         // Calculate the total points that have been awarded.
21:         int totalPoints = 0;
22:         for (int point : points) {
23:             totalPoints += point;
24:         }
25:
26:         /*
27:         Assign each employee their bonus percentage based on their points
28:         and the total points.  Fractions will be rounded down.  Keeps
29:         track of the percentage remaining.
30:          */
31:         int bonusPctRemaining = 100;
32:         for (int i = 0; i < points.length; i++) {
33:             bonuses[i] = (points[i] * 100) / totalPoints;
34:             bonusPctRemaining -= bonuses[i];
35:         }
36:
37:         /*
38:         If there is any bonus percentage remaining, we'll assign 1% to each
39:         of the top scoring employees until it is used up.
40:          */
41:         while (bonusPctRemaining > 0) {
42:
43:             int maxPoints = -1;
44:             int employee = -1;
45:
46:             /*
47:             Find the employee with the highest points value that has
48:             not yet been awarded the extraBonus.
49:             Ties go to the employee positioned earlier in the points array.
50:              */
51:             for (int i = 0; i < points.length; i++) {
52:                 if ((!extraBonus[i]) && (points[i] > maxPoints)) {
53:                     employee = i;
54:                     maxPoints = points[i];
55:                 }
56:             }
57:
58:             /*
59:             We've found the next top employee, so set extraBonus to true,
60:             so they are not considered next time; add 1% to their bonus,
61:             and remove 1% from the amount remaining.
62:              */
63:             extraBonus[employee] = true;
64:             bonuses[employee] += 1;
65:             bonusPctRemaining -= 1;
66:         }
67:
68:         return bonuses;
69:     }
70: }
```
Notes:

Lines 21-24 simply counts up the total number of points that were assigned across all employees.

Line 33 then calculates the percentage for each employee. The "/" operator truncates any fractions. As each bonus is assigned, we subtract that amount from the bonus percentage remaining.

While there is any bonus percentage remaining, we'll assign 1% to the top scoring employee that has not already received this extra bonus.

This is implemented by creating an array of booleans (Line 15) that keeps track of each employee that has received this extra bonus. The loop at line 51 looks for the employee with the greatest score that has not been awarded the bonus. Ties will go to the employee appearing earlier in the points array, since line 52 requires that the current employee's points be greater than what has already been seen.

A more efficient way to do this might be to sort the employees by score, and award the extra bonus starting at the beginning of the list until the bonus runs out. However, we'd need to copy the points array to the new sorted array, and maintain a mapping between the tow. Furthermore, we'd need to use a stable sorting algorithm, that is, one that does not switch the positions of two employees if their score is the same. I'm not sure if the standard java sorting algorithms guarantee this or not - so we'd be looking at implementing our own sorting algorithm, which is not hard, but not necessary for this problem.

Update: Java's Collections.sort() is guaranteed to be stable.