Match Editorial

With solid times on all three problems, Petr took first by over 100 points. tmyklebu had the best time one the hard problem by far, and despite a failed medium submission, he took second. kalinov took third thanks to a challenge. In division 2, sfcommand took first, followed by Minny and newcomer WSX.

The Problems

Value	250
Submission Rate	315 / 340 (92.65%)
Success Rate	291 / 315 (92.38%)
High Score	kissaki for 249.31 points (1 mins 30 secs)
Average Score	212.81 (for 291 correct submissions)

The simplest way to solve this problem was to look at each character in the code, starting from the first character, in order. As you go along, you keep an integer representing the value so far. If the character in the code is not in the key, you simply ignore it. Otherwise, you multiply the integer by 10, and add the number represented by the character. This is the standard way to parse numbers in any base: look at each character one at a time, multiplying by the base (10 in this case) and then adding each time.

Value	500
Submission Rate	297 / 336 (88.39%)
Success Rate	238 / 297 (80.13%)
High Score	RNGAN for 492.35 points (3 mins 33 secs)
Average Score	376.81 (for 238 correct submissions)

This problem was pretty straightforward. It's easy to add up the points for the jacks, queens, kings and aces. To add up the points for short suits, just count how many cards of each suit you have.

Value	1000
Submission Rate	139 / 340 (40.88%)
Success Rate	33 / 139 (23.74%)
High Score	Minny for 738.74 points (18 mins 18 secs)
Average Score	507.17 (for 33 correct submissions)

Working in 12 hour format is cumbersome. In these sorts of problems, it's typically best to convert the input format to a single integer, representing the number of minutes past midnight. The easiest way to do this is:

    int time = hour%12*60+minute;
    if(pm)time += 12*60;

    duration = (time2 - time1 + 24*60)%(24*60);

    int hours = ret/60%12;
    if(hours == 0)hours = 12;
    int minutes = ret%60;
    boolean pm = ret >= 12*60;

Value	300
Submission Rate	240 / 319 (75.24%)
Success Rate	171 / 240 (71.25%)
High Score	antimatter for 290.16 points (5 mins 16 secs)
Average Score	209.65 (for 171 correct submissions)

Many coders missed the part of the problem that said that the weights must add up to exactly 1. Assuming you saw that, the problem wasn't too bad. Since you always predict from exactly 5 previous values, you can easily solve this with 4 nested loops, each going from -1 to +1 in increments of 0.1. You can calculate the 5^th weight as d5 = 1-d1-d2-d3-d4. Assuming that this fifth weight is between -1 and +1, inclusive, you can compute the weighted average for each of the values beyond the fifth, and find the average error as described.

Value	450
Submission Rate	185 / 319 (57.99%)
Success Rate	61 / 185 (32.97%)
High Score	m00tz for 381.52 points (12 mins 30 secs)
Average Score	265.44 (for 61 correct submissions)

The parts of the return corresponding to the exchanges are relatively simple to calculate. Each new quote corresponds to a change in the quote, so the COUNT part of the return is just the number of times that the exchange appeared in the input. The average spread for an exchange is also pretty easy to calculate, since it's just a simple average over the spread from the input for that exchange.

The information corresponding to the inside quote is a bit more difficult to calculate. To calculate the inside quote, you need to keep track of the most recent quote from each of the exchanges that have issued at least one quote. The inside quote can be calculated from this information as described in the problem, by finding the highest bid and the lowest ask. After each new quote, you should recalculate the inside quote and see if it changed. If it changes, include that spread as part of the average spread, and increment the count.

Finally, you need to be particularly careful about the rounding mode you use for rounding your return to 2 digits. The default rounding mode in many methods is to round 0.005 towards the even number, not just up. Many solutions failed because they rounded 0.625 to 0.62 instead of 0.63.

Value	1000
Submission Rate	32 / 319 (10.03%)
Success Rate	19 / 32 (59.38%)
High Score	tmyklebu for 941.65 points (7 mins 9 secs)
Average Score	585.31 (for 19 correct submissions)

There are a few different ways you can do the dynamic programming for this problem. Since tmyklebu had the highest score, I'll describe a solution similar to his. First, observe that each computer must have at least minInComp processors. So, we can immediately remove minInComp*amount processors, and reduce minInComp to 0, to get an equivalent problem. Now, there are two basic cases that we need to handle. We can have some positive number of computers with 0 processors (minInComp processors in the original problem). Alternatively, we can have 0 computers with 0 processors, in which case the minDif doesn't come into play, as we could have computers with just 1 processor. In the first case, we will account for some of the computers and assign a number of processors to them. In this case, the remaining computers must have at least minDif processors (the ones we just assigned had 0 processors), so we subtract that many processors and recurse. In the second case, where we have 0 computers with 0 processors, all of the computers must have at least 1 processor. In this case, we can subtract 1 processor for each computer that we must make, and we still need to make the same number of computers. In both cases, the key realization is that the answer to choices(n,minDif,minInComp,amount) is the same as the answer to choices(n-minInComp*amount,minDif,0,amount), assuming that 0 is an acceptable value for minInComp.

So, our basic recurrence goes as follows:

    //go() returns the number of ways to make amount 
    //computers with n processors, assuming that the
    //minimum number of processors per computer is 0
    long go(int n, int amount){
        //too few processors, return 0
        if(n<0)return 0;
        //1 way to assign 0 processors to the computers -- 
        //0 processors to each one
        if(n==0)return 1;
        //all computers assigned, but extra processors

        if(amount == 0)return 0;
        long ret = 0;
        //assign 0 computers with 0 processors.  Each 
        //computer must have at least one processor.  
        //Same as n-amount processors for amount computers
        ret += go(n-amount,amount);
        for(int i = 1 ;i<=amount;i++){
            //assign i computers to have 0 processors.  The
            //other amount-i computers must have at least minDif 
            //processors, so subtract (amount-i)*minDif from n, 
            //and i from amount and recurse.
            ret += go(n-(amount-i)*minDif,amount-i);
        }
        return ret;
    }
    long choices(int n, int minDif, int minInComp, int amount) {
        return go(n-minInComp*amount,amount);
    }