Match Editorial

In division 1, Eryx led the coding phase, followed by misof, tomek and krijgertje. However, the challenge phase turned out to be important as tomek gained 150 points, and took first place. misof and krijgertje got 75 and 25, giving them second and third, respectively. Eryx, with no challenges, was forced to settle for fouth.

In division 2, many C++ coders failed the easy problem, but not bvs, you won easily. In second place, bungle's good scores on the medium and hard made up for his failed easy submission. Rounding out the top three was zmast3r.

The Problems

Value	250
Submission Rate	231 / 249 (92.77%)
Success Rate	133 / 231 (57.58%)
High Score	Protean for 243.93 points (4 mins 30 secs)
Average Score	195.49 (for 133 correct submissions)

Usually, it's the C++ coder who get away with things that Java and C# users can't, in regards to floating point arithmetic. This problem was an exception to that, with many C++ coders failing because of the way they compared doubles.

In Java, C# and VB, you can expect a division of two numbers to always give you the same 64-bit double precision floating point value. Hence, in these languages, it was safe to simple do something like:

    if(ones/(ones+twos) < lowestRatio){
        ...
    }

    if(0.666667 < 0.66667){
        ...
    }

Value	500
Submission Rate	188 / 249 (75.50%)
Success Rate	61 / 188 (32.45%)
High Score	bvs for 447.11 points (10 mins 0 secs)
Average Score	302.92 (for 61 correct submissions)

Value	250
Submission Rate	216 / 221 (97.74%)
Success Rate	153 / 216 (70.83%)
High Score	m00tz for 247.72 points (2 mins 43 secs)
Average Score	187.41 (for 153 correct submissions)

The best solution to this problem is to use a regular expression to replace groups of vowels surrounded by consonants. This approach allowed m00tz and Im2Good to take first and second place on this problem. Alternatively, you could write some actual code that looks for vowels which have a consonant before a space or edge of string in both directions. Just loop over all the characters and when you find a vowel, loop both forward and backward to find the next consonant. If you find the consonant before a space in both directions, remove the vowel.

Value	1000
Submission Rate	63 / 249 (25.30%)
Success Rate	10 / 63 (15.87%)
High Score	bvs for 832.14 points (13 mins 19 secs)
Average Score	538.62 (for 10 correct submissions)

If you try all possible locations of the rectangle you are supposed to place, your solution will surely timeout. However, there is a simple way to figure out which locations to consider. If your rectange covers some number group of previous rectangles, consider whether you might be able to slide it a little bit in the +x and +y direction. If none of the covered rectangles have the same lower x coordinate as your rectangle, you can do so without decreasing the number of rectangles covered. The same thing goes for the y coordinate. Eventually, you will have slid it as far as it will go, and both of its lower x and y coordinates will be the same as some of the covered rectangles (not necessarily the same ones for x and y). Thinking about it this way, its clear that you need only consider locations for your rectangle where the lower x and y coordinate are the same as the lower x and y coordinates of some existing rectangles.

 int ret = 0;
 for(int i = 0; i<r.length; i++){
   for(int j = 0; j<r.length; j++){
     int c1 = 0, c2 = 0;
     for(int k = 0; k<r.length; k++){
       if(r[i][0]<=r[k][0] && r[j][1]<=r[k][1] && 
             r[i][0]+qa>=r[k][2] && r[j][1]+qb>=r[k][3]) c1++;
       if(r[i][0]<=r[k][0] && r[j][1]<=r[k][1] && 
             r[i][0]+qb>=r[k][2] && r[j][1]+qa>=r[k][3]) c2++;
     }
     ret = Math.max(ret,Math.max(c1,c2));
   }
 }
 return ret;

Value	500
Submission Rate	106 / 221 (47.96%)
Success Rate	84 / 106 (79.25%)
High Score	tomek for 431.97 points (11 mins 39 secs)
Average Score	262.41 (for 84 correct submissions)

The input constraints are small enough that a simple brute force approach to this problem works fine. Many coders chose to play it safe and memoize, caching the return value of their recursive function for a particular left and right valid, along with which dominoes were used, but this was unnecessary. Instead, just write a single recursive function that takes the some information about the left and right most dominoes, along with the set of dominoes which has been used (or is available). The only information you need about the dominoes on the end is whether or not they are doubles, and what the outermost value is. Then, just see which dominoes, if any, can be added on either end, and recurse. You can either keep a running score as you do the recursion, in which case you find the final score for a particular game at the bottom of the recursive call tree, or your method could return the best score from the rest of the game, in which case you find the optimum at the root of the call tree. I choose the latter approach because it makes things easier in case you decide you have to memoize after all.

Value	1000
Submission Rate	63 / 221 (28.51%)
Success Rate	57 / 63 (90.48%)
High Score	cyfra for 946.70 points (6 mins 49 secs)
Average Score	755.00 (for 57 correct submissions)

With 800 songs, there are way to many orderings to consider anywhere near all of them. That should be your first clue that perhaps there is some trick or greedy approach to solving this problem. The first thing to think about is the distance metric (which turns out to be a terrible way to achieve its desired goal). Notice that, for a particular artist, the total distance contributed by all of that artist's songs is really just the distance from the first to the last song. The ones in the middle don't matter, since moving them left or right increases one distance, while decreasing another. This suggests that, for each artist with more than one song, you should put one of that artist's songs towards the end, and one of them towards the beginning, and throw the rest into some middle section which is between all of the beginning and ending songs from all artists. Artists with one song don't contribute to the distance themselves, so there songs should go in the middle section to increase the distance contributed by other artists.

Now, you just need to figure out exactly what order to put the beginning, middle and ending songs in. Notice that if you have a particular order, and swap two songs in the beginning section, the distance contributed by one artist will go up, but the distance from the other will go down by the same amount. Similarly, the order of the ending section has no affect on the total distance. We already know that the middle ordering doesn't matter, so we can just sort each of the sections alphabetically, and we will get the return we want.