Match Editorials

Match summary

The latest round of the TCHS division led competitors through a minefield of darts, sales, and parts. Oh my!

The competition was fierce during the coding phase, as the competitors fought through a relatively easy problem set. tomekkulczynski was the first to submit all three problems, but resubmitted the 1000 point problem a few minutes later. After the coding phase, Weiqi led all coders due to the fastest times on both the 500 and 1000, followed by Achtung-Achtung and Loner.

The challenge phase gave Achtung-Achtung 50 points, vaulting him into the lead. System tests were not kind, however, knocking out his 1000 point problem, leaving Weiqi (who also regained his red color) as the winner. Filling out the rest of the top 5 were Loner, hupo001, yep (in his debut match), and tomekkulczynski.

The Problems

Value	250
Submission Rate	132 / 151 (87.42%)
Success Rate	120 / 132 (90.91%)
High Score	tomekkulczynski for 247.78 points (2 mins 41 secs)
Average Score	206.80 (for 120 correct submissions)

The easiest way to solve this problem involves iterating over all possible targets to aim at. For each target, you can calculate the expected score, and keep track of the highest score found. You have to be careful, though, when checking the score at the first and last elements of payout to avoid going out of bounds; this can be fixed by hard-coding those cases, or by using modular arithmetic. Java code illustrating the latter follows:

public class DartThrow
{

public double bestScore(int[] payout, int prob)
{
    // probability as a decimal
    double p = prob / 100.0;
    // probability of hitting a side target
    double p2 = (1 - p) / 2.0;
    int i, N=payout.length;
    double ret = 0.0;
    for(i=0; i<N; i++)
        ret = Math.max(ret, p*payout[i] + p2*payout[(i+1)%N] + p2*payout[(i-1+N)%N]);
    return ret;
}
}

Value	500
Submission Rate	101 / 151 (66.89%)
Success Rate	81 / 101 (80.20%)
High Score	Weiqi for 487.23 points (4 mins 37 secs)
Average Score	382.42 (for 81 correct submissions)

Let r be the cost of regular in cents. Similarly, let s be the cost of sale in cents. If you purchase s items at regular cost, then it is the same as buying r items at the sale price, meaning that you get free = s-r items for free. However, if s and free have any common divisors, this is not the smallest possible solution. To fix this, you need to find the greatest common divisor (or gcd for short) of s and free, which can be found using the Euclidean Algorithm. Finding the gcd turns out to be very useful in many TopCoder problems, so it is good to be able to quickly code this. See otinn's solution for a clean implementation of this.

Value	1000
Submission Rate	50 / 151 (33.11%)
Success Rate	25 / 50 (50.00%)
High Score	Weiqi for 859.83 points (11 mins 52 secs)
Average Score	603.92 (for 25 correct submissions)

Helping Lucy out with her science project turns out to be an exercise in Dynamic Programming (see this tutorial for more information), a tool that turns out to be very useful in TopCoder competitions. To do this, we need to build a two-dimensional array. dp[time][e] will be set to 1 if there is some configuration of parts that takes exactly time seconds and ends with e energy; if this cannot happen, then it is set to 0.

Since we can start out with any type of energy, we can set dp[0][i] to 1 for all four types of energy, and set the rest of the array to 0. We then proceed to step through the array chronologically. For each time t, we see if dp[t][e] is equal to 1 for any energy e. If it is, then we can extend the machine with any parts that begin with e energy; this allows us to set dp[t + part_time][part_output]=1 for those parts. After looping through all values of t, we can then look in the last column to find the closest element to target that is set to 1.

Although this method works, there was another trap to watch out for. Sometimes, you had to go over the target to get the closest time; example 4 was one example of this. Extending your array and searching through a total of 2*target seconds was sufficient to avoid this scenario.

See MB__'s solution for a good example of this method.