TopCoder SRM 500 Div 2 Easy

I have solved another TopCoder problem. I am starting to get better at these as this one took a lot less time to understand. I ended up getting my first attempt wrong on some test cases and couldn’t figure out why at the time. I think it was because I did the first attempt in cpp and spent most of the time trying to remember how to use it. Think I will stick with Java for the rest of them as this will allow me to focus on coding the solution and keep me from tripping up on the language. Here’s the problem statement:

Dmitry likes TopCoder Single Round Matches. Once, he registered for an SRM and was waiting for the coding phase to begin. To entertain himself while waiting, he decided to play the following game.

He makes a pile of cards, and on each card, he writes the number of an SRM in which he has competed. No two cards contain the same number. He then takes turns until the pile is empty. Each turn consists of the following sequence of actions:
Dmitry chooses an arbitrary card from the pile. Let A be the number written on this card.
The card with number A is removed from the pile.
If the pile contains a card with number A-1, that card is removed from the pile.
If the pile contains a card with number A+1, that card is removed from the pile.
The game is finished when the pile becomes empty. It’s fun to play the game, so Dmitry wants to spend as much time as possible playing it.

You are given a int[] cards containing the numbers written on the cards in the pile before the start of the game. Return the largest possible number of turns in which Dmitry can finish the game.

Constraints
– cards will contain between 1 and 50 elements, inclusive.
– Each element of cards will be between 1 and 499, inclusive.
– All elements of cards will be distinct.

So basically we needed to play the game of removing a card and any other cards with a value within 1 of the value of the current card as long as possible. The best way to play the game longer is to limit the amount of cards that you remove each turn.  The most you can remove is 3 and the least is 1, but if there are 3 cards that are within 1 of each other, say with values {1,2,3}, the least you can remove is 2 cards ( either 1 and 2, or 2 and 3 ).  So it is best to always shoot for this case of removing either 1 or 2 cards.  To do this, we can sort the array and always test the beginning as this will always be the least valued card in the deck.  We would either just remove the first card, or the first and the second at most.

First attempt: 1h

#include <vector>
#include <algorithm>

using namespace std;

class SRMCards {
public:
    int maxTurns(vector<int> cards) {
        int turns = 0;

        // sort the array
        sort(cards.begin(), cards.end());
        auto it = cards.begin();

        // run through to see how long we can play
        while (!cards.empty()) {
            if ((it + 1) != cards.end() && *(it + 1) - *it == 1) {
                cards.erase(it + 1);
            }

            ++it;
            ++turns;
            cards.erase(cards.begin());
        }

        return turns;
    }
};

This was my initial approach. I spent the majority of the time fumbling over the c++ language. I forgot how long it’s been since I have actually done any coding in this language. This failed some of the test case and I couldn’t figure out why. I thought it was because I had misunderstood the problem statement so I looked at the editorial. Low and behold my understanding of the statement was correct, but I had overcomplicated the implementation. I think this is partially because I hadn’t really used vectors ever in c++ and I just kind of felt it out. Here’s my second attempt:

Second attempt: 20m

import java.util.Arrays;

public class SRMCards {
    public static int maxTurns(int[] cards) {
        int turns = 0;
        Arrays.sort(cards);

        for (int i = 0; i < cards.length; i++) {
            if (i < cards.length - 1 && cards[i+1] - 1 == cards[i]) {
                ++turns;
                ++i;
            }

            else
                ++turns;
        }

        return turns;
    }
}

I went back to java and knocked out a second attempt. This time instead of removing items from the array, I just incremented the counter to move an extra position. This made for much a more concise implementation.

Third attempt: 1m

import java.util.Arrays;

public class SRMCards {
    public static int maxTurns(int[] cards) {
        int turns = 0;
        Arrays.sort(cards);
        for (int i = 0; i < cards.length; ++i) {
            if (i < cards.length - 1 && cards[i+1] - cards[i] == 1) {
                ++turns;
                ++i;
            }
            else
                ++turns;
        }

        return turns;
    }
}

Having fully understood the problem and implementation, the third attempt only took me 1 minute to code! Not a bad improvement, I am looking forward to the next practice problem. Actually today I am hoping to get my chance to participate in my first live SRM!

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.