editorial_28350_780x0_proportion

TopCoder SRM 145 Div 1 250 Point

I completed my first practice problem not too long ago.  I chose this problem at random in the topcoder arena after reading through Planning an Approach to a Topcoder Problem: Part 1.  In the write up, the author gives the first task of picking any problem in the practice rooms, and solving it 3 times.  The first time you solve it represents the time it takes you to solve the problem with no information about it, the second time is the time it takes minus the time it took you to understand the problem, and the third time represents your potential.  So with that in mind, here is the problem statement:

Problem Statement

You have a certain amount of money to give out as a bonus to employees. The trouble is, who do you pick to receive what bonus? You decide to assign a number of points to each employee, which corresponds to how much they helped the company in the last year. You are given an points, where each element contains the points earned by the corresponding employee (i.e. points[0] is the number of points awarded to employee 0). Using this, you are to calculate the bonuses as follows:

– First, add up all the points, this is the pool of total points awarded.
– Each employee gets a percentage of the bonus money, equal to the percentage of the point pool that the employee got.
– Employees can only receive whole percentage amounts, so if an employee’s cut of the bonus has a fractional percentage, truncate it.
– There may be some percentage of bonus left over (because of the fractional truncation). If n% of the bonus is left over, give the top n employees 1% of the bonus. There will be no more bonus left after this. If two or more employees with the same number of points qualify for this “extra” bonus, but not enough bonus is left to give them all an extra 1%, give it to the employees that come first in points.

The return value should be a , one element per employee in the order they were passed in. Each element should be the percent of the bonus that the employee gets.

After reading through this multiple times, I understood what I needed to do.  Basically you get an array of int values.  Using these values you have to determine out of 100 how much bonus percentage each employee gets.  There are no partial percentages ( i. e. integers not floats ), so the remainders should be stripped away and redistributed at the end.    This is done by taking the remainder and giving it to the highest rated employees.  If there are multiple employees with the same rating at this point, we should give the bonuses to the employees that came first in the array with the highest value (so if there are 4 with the same rating and 2 points left over, give the first two employees one extra point).  So with the understanding in mind, here is the first attempt:

// first attempt, 3 hours
public class Bonuses {
	private Boolean inArray(int[] array, int value) {
		for(int i = 0; i < array.length; ++i) {
			if (array[i] == value) return true;
		}

		return false;
	}

	public int[] getDivision(int[] points) {
		int[] divisions = new int[points.length];

		int tally = 0;
		int total = 0;

		for(int i = 0; i < points.length; ++i) {
			total += points[i];
		}

		for(int j = 0; j < points.length; ++j) {
			divisions[j] = (int)(Float.valueOf(points[j]) / total * 100);
			tally += divisions[j];
		}

		tally = 100 - tally;
		int[] bonusEmployees = new int[Math.min(tally, points.length)];
		for (int i = 0; i < bonusEmployees.length; ++i) {
			bonusEmployees[i] = -1;
		}

		for (int i = 0; i < bonusEmployees.length; ++i) {
			int currentMax = 0;
			for (int j = 0; j < points.length; ++j) {
				if (!inArray(bonusEmployees, j) && currentMax < points[j]) {
					currentMax = points[j];
					bonusEmployees[i] = j;
				}
			}
		}

		while (tally > 0) {
			for (int x = 0; x < bonusEmployees.length && tally > 0; ++x) {
				divisions[bonusEmployees[x]] = divisions[bonusEmployees[x]] + 1;
				--tally;
			}
		}

		return divisions;
	}
}

So my first attempt took an embarrassingly long amount of time :) .  I got caught up on redistributing the the remainder.   I first needed to get the total from the points array which indicates the employee and the percentage of the bonus they should receive.  I then setup another array to keep track of the employees have received a portion of the remainder.  I then run through the divisions array again and pull out the employees that need to receive the bonus and store them in the bonusEmployees array.  And finally I used bonusEmployees array to go back and add to the division array.  This passed all the test cases given but I was sure there was a more efficient approach.  At this point I read the editorial for the match and attempted the problem again.

// second attempt 20 minutes
public class Bonuses {
    private Boolean inArray(int[]arr, int value) {
        for (int n = 0; n < arr.length; ++n) {
            if (arr[n] == value) return true;
        }
        return false;
    }

	public int[] getDivision(int[] points) {
		int [] divisions = new int[points.length];

        int remainder = 100;
        int total = 0;

        for (int point : points) {
            total += point;
        }

        for (int i = 0; i < points.length; ++i) {
            divisions[i] = (int)(Float.valueOf(points[i]) / total * 100);
            remainder -= divisions[i];
        }

        int nextUpdateIndex = 0;
        int[] updates = new int[remainder];
        for (int x = 0; x < updates.length; ++x) updates[x] = -1;

        while (remainder > 0) {
            int max = 0;
            int index = -1;

            for (int j = 0; j < divisions.length && remainder > 0; ++j) {
                if (max < divisions[j] && !inArray(updates, j)) {
                    index = j;
                    max = divisions[j];
                }
            }
            divisions[index]++;
            remainder--;
            updates[nextUpdateIndex] = index;
            nextUpdateIndex++;
        }

        return divisions;
	}
}

A wrote the solution much faster this time.  After reading the editorial, I realized that the remainder would always be smaller than the input array so I was able to eliminate a loop.  Everything else ended up staying relatively the same.  The code got a little cleaner this time, but I was still hung up on how to keep track of the employees that needed to receive the remainder.  I then checked out some of the other solutions to the problem and saw the obvious solution.  See my last attempt:

// final attempt, 3 minutes
public class Bonuses {
    public int[] getDivision(int[] points) {
        int [] divisions = new int [points.length];

        int total = 0, remainder = 100;

        for (int p : points) {
            total += p;
        }

        for (int i = 0; i < points.length; ++i) {
            divisions[i] = points[i] / total * 100;
            remainder -= divisions[i];
        }

        while (remainder > 0) {
            int index = 0, max = 0;

            for (int x = 0; x < points.length; ++x) {
                if (points[x] > max) {
                    max = points[x];
                    index = x;
                }
            }

            remainder--;
            divisions[index]++;
            points[index] = 0;
        }

        return divisions;
    }
}

Just lower the point value of the employee that already received the remainder in the points array!  That way, the next time through the final loop no longer needs any extra checks to keep track of which employee received the bonus as the max will keep track of this for us.  Since we will only go through the points array once ( as remember the remainder will always be less than the number of employees ) setting the last employee to receive the remainder’s point value to 0 effectively ensures that they won’t receive a bump more than once.  By the time I had come to this solution, my time to implement dropped to 3 minutes, way down from 3 hours the first time!

I am very happy with the results of this approach and I look forward to replicating these improvements on some other problems.  This was one of the easy ones that didn’t require any fancy algorithms, but the plan is to work my way up to the hard questions as I learn more about the algorithms and even start participating in some of the weekly competitions to start ranking.

Published by

Duke Deus

Deus Duke is a mobile software developer in the Bay Area. Also interested in game development, the occasional bar, and all around good times.

Leave a Reply