Tuesday, July 12, 2005 Match summary
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. The ProblemsElectionsUsed as: Division Two  Level One:
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. if(ones/(ones+twos) < lowestRatio){ ... }When you do the division, ones/(ones+twos), you are guaranteed (assuming the numbers stay reasonably small) to get the same thing as the division (x*ones)/(x*(ones+twos)), for some integer x. This is true in C++ also; but the result of a floating point operation is a long double with 80 bits, not just a double. Therefore, when lowestRatio is a double, which has been cast (implicitly) from a long double, and you compare it to the original long double, they may not be equal. To get a better understanding, think about the ratio 2/3. The long double has more precision, so it will represent the fraction as something like 0.666667, while the double may only represent it as 0.66667. When you do the division, you get the long double, but then you store it in a regular double, so lowestRatio may take on the value 0.66667. Now, when you get another element of the input, that also has two thirds ones, you compare the long double from the division directly to the double, and get something like: if(0.666667 < 0.66667){ ... }This evaluates to true, and you end up using the higher index among tied elements, rather than the lower one. One solution to this is to simply make sure that you do all your comparisons in the same precision. Alternatively, you can use an epsilon, or else avoid floating point numbers altogether. SMS Used as: Division Two  Level Two: Used as: Division One  Level One:
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. OneMoreRectangleUsed as: Division Two  Level Three:
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;DominoesGame Used as: Division One  Level Two:
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. MusicCompilationUsed as: Division One  Level Three:
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. 
