Match Editorial

Division 1 had a pretty hard problem set, as a great number of coders received 0 points. At the end of the challenge phase, it looked like Yarin would come out on top, with an impressive time on the hard problem. However, his medium submission failed system tests and he ended up in fourth place. Veteran John Dethridge ended up taking the match, followed by jvpardon in second, and halyavin in third, competing in only his third SRM.

Division 2 had a much easier set with high success rates. As in division 1, a TopCoder veteran, kmd-10 took first place. He was followed by first time competitor {dano} in second and galkovsk in third.

The Problems

Value	250
Submission Rate	288 / 299 (96.32%)
Success Rate	224 / 288 (77.78%)
High Score	jambon_vn for 246.17 points (3 mins 33 secs)
Average Score	207.73 (for 224 correct submissions)

First, you need to sort the three dimensions so that you can apply the formulas in the notes, using x, y and z where x ≤ y ≤ z. Once you do this, you pretty much just need to make sure that you spell the return values correctly.

Value	500
Submission Rate	219 / 299 (73.24%)
Success Rate	174 / 219 (79.45%)
High Score	Jsub for 483.18 points (5 mins 20 secs)
Average Score	343.17 (for 174 correct submissions)

Since the numerator can not be more than 1000, the return is always relatively small. In fact, example 2 shows that the largest return is only about 300,000. As a result, it is easy to use brute force to generate all fractions in the list up to numerator/denominator. Simply use two nested loops to generate all numerators (the outer loop) and denominators (the inner loop) up to the fraction represented by the input. As you generate the fractions in the list, you need to check that the greatest common denominator of the numerator and denominator is 1.

    int cnt = 0;
    for(int i = 2; ; i++)for(int j = 1; j<i; j++){
        if(gcd(i,j) == 1)cnt++;
        if(j==numerator && i == denominator)return cnt;
    }

    int gcd(int a, int b){return b == 0 ? a : gcd(b , a%b);}

Value	1000
Submission Rate	111 / 299 (37.12%)
Success Rate	72 / 111 (64.86%)
High Score	kmd-10 for 862.70 points (11 mins 43 secs)
Average Score	576.07 (for 72 correct submissions)

This was rather easy as far as div 2 hard problems go. You simply need to generate all of the numbers from 1 to 100, as specified, and then see which one is closest to the input. To generate the numbers, you should have three arrays of strings for the ones, tens, and teens. Having the strings in order in arrays makes it easy to generate the correct string from a number by either looking them up directly or by combining the appropriate two strings. To check the distance between two strings, just compare each character one at a time.

Value	300
Submission Rate	198 / 237 (83.54%)
Success Rate	153 / 198 (77.27%)
High Score	John Dethridge for 278.86 points (7 mins 56 secs)
Average Score	178.56 (for 153 correct submissions)

This problem tripped up a lot of coders. However, the last sentence of the problem provides the key to solving it. Since the child farthest from a chair is the loser, we simply need to calculate the distance from each child to the chair closest that child. To do this for a particular child, first compute the position of the child. We can say that child i starts 1-i/n, where the distance around the circle is 1 (this makes then evenly spaced, and in the correct order). After time seconds, the child advances time/10 to position (1-i/n+time/10) mod 1. Next, we compute the distance to the nearest chair from this position. A simple way to do this is to compute the distance to every chair, as there are at most 25 of them. Alternatively, you can compute that the nearest chair is at either floor(pos*(n-1))/(n-1) or ceil(pos*(n-1))/(n-1). A lot of coders made the mistake of sending the children in the wrong direction, with A following B instead of the other way around.

Value	500
Submission Rate	75 / 237 (31.65%)
Success Rate	21 / 75 (28.00%)
High Score	ardiankp for 384.84 points (16 mins 37 secs)
Average Score	298.20 (for 21 correct submissions)

The first step in this problem is to reverse some of the words so that the front of the train car is the same as the front of the word. This can be done by always using the lexicographically earlier of the input word and its reverse, which has the added benefit of being the correct direction for the tie breaking rules on the output. Once the words are all facing the proper direction, you can sort them in a particular way that makes the problem quite simple. Sort primarily be the first letter of each word. When ties occur, put the words whose first and last characters are the same earlier. When ties still remain, break them lexicographically. This order is the same as the order the words will have in the output (meaning that the output words are a subsequence of the words when sorted like this).

Next, we can use dynamic programming to compute the output. For each word, find the longest sequence that ends at that word by looking back at all of the previously computed sequences:

    for(int i = 0; i<cars.length; i++){
        best[i] = cars[i];
        for(int j = 0; j<i; j++){
            if(cars[i].charAt(0) == cars[j].charAt(cars[j].length()-1)){
                best[i] = better(best[i],best[j]+"-"+cars[i]);
            }
        }
        ret = better(ret,best[i]);
    }
    return ret;

Value	1000
Submission Rate	26 / 237 (10.97%)
Success Rate	17 / 26 (65.38%)
High Score	Yarin for 772.90 points (16 mins 26 secs)
Average Score	577.90 (for 17 correct submissions)

We can use brute force to find one of the segments, which we will denote as the segment with the smallest sum. Starting with this segment, we can use dynamic programming to minimize the sum of the largest segment, subject to the constraint that all segments have sum at least as high as the initial segment we found via brute force. The idea is to compute the best way to use k gems to make j segments such that all of the segments have a sum at least as large as the segment designated as the lowest sum segment. For a particular smallest segment, we can call this value dp[k][j].

If we know dp[k][j], then we can consider making a segment out of the gems from k+1 to i. If the sum of those gems is not as high as the value of the segment designated as the lowest sum segment, then those gems do not form a valid segment. Otherwise, we know that one possible value for dp[i][j+1] is max(dp[k][j],sumOfGems(k+1..i)). In other words, we have added on segment, making j+1 total, the last one of whose sum is sumOfGems(k+1..i). Since we already know the best way to arrange the first j segments, the value of the largest segment must either be the value of the largest from those j, or else the value of the new segment.

public int inequity(int n, int[] gems){
    int[] v = new int[gems.length+1];
    int ret = Integer.MAX_VALUE;
    for(int x = 0; x<gems.length; x++){
        int min = 0;
        //precompute the sum of gems[0..a] for each a
        for(int a = 1; a<v.length; a++)v[a] = v[a-1] + gems[a-1];
        for(int y = 0; y<gems.length ;y++){
            min+=gems[y];
            //gems[0..y] forms the segment with smallest sum, min
            int[][] dp = new int[n+1][gems.length+1];
            dp[1][y+1] = min;
            //dp[1][y+1] represents the best and only way
            //to arrange the first y gems in one segment
        
            //now loop over j -- add segments
            for(int j = 2; j<=n; j++){
                //loop over i -- the number of gems used to make j segments
                for(int i = y+1; i<=gems.length; i++){
                    //loop over k -- the number of gems used to make j-1 segments
                    for(int k = y+1; k<i; k++){
                        //first make sure that the gems from k+1 to i form a valid
                        //segment and that it is possible to make j-1 segments with k gems
                        if(v[i]-v[k] < min || dp[j-1][k] == 0)continue;
                        int t = Math.max(dp[j-1][k],v[i]-v[k]);
                        //t holds a possible value for dp[j][i]
                        if(dp[j][i] == 0 || t < dp[j][i]){
                            dp[j][i] = t;
                        }
                    }
                }
            }
            //If it was possible to make n segments using this 
            //initial segment, minimize the return value
            if(dp[n][gems.length]!=0){
                ret = Math.min(ret,dp[n][gems.length]-min);
            }
        }
        //rotate the gems array 1 position to keep things simple
        int t = gems[0];
        for(int a = 0; a+1<gems.length; a++)gems[a] = gems[a+1];
        gems[gems.length-1] = t;
    }
    return ret;
}