|
Match Editorial |
Online Round 2
January 19, 2005
Summary
Submissions to the first two problems came in fast and fierce during round 2 of the TopCoder Collegiate Challenge. Eryx was the first to submit both problems, doing so in under 10 minutes. Others were not far behind though, and after 20 minutes, most of room 1 was working on the last problem. tomek was in his usual form, and his time on the hard problem would have been enough to give him yet another win. However, an unsuccessful challenge knocked him down to second, giving haha the narrow victory. In third place, the ever-speedy antimatter was only one point behind. Amongst the advancers, president was the lowest rated member to advance to the next round, while bstanescu, a regular at past onsite events, had the dubious distinction of being the highest rated member not to advance.
The Problems
CalendarHTML
Used as: Division One - Level One:
Value 250 Submission Rate 182 / 184 (98.91%) Success Rate 166 / 182 (91.21%) High Score m00tz for 245.85 points (3 mins 42 secs) Average Score 206.82 (for 166 correct submissions)
This problem was quite a bit easier than the easy from round 1, and most people had little trouble with it. First, you should add the header tags, which can easily be hard coded. Next, for the first row, you should add a number of empty cells equal to start. Then, just start iterating over days, adding a cell for each day. When you get to a day, d, such that d+start % 7 == 1, you have reached the end of a row, and you should take the appropriate steps. The one special case you have to deal with is when start is 0, you don't want to start two new rows on the first day. Finally, at the end of the month, you need to add enough days so that the final row has 7 cells. Again, be careful not to add an extra row of empty cells at the end when there are just enough days to fill the calendar. There are dozens of other good ways to go about all this, so if you don't like this one, take a look at some of the high scoring submissions, as they provide a number of alternative methods.
NthFraction
Used as: Division One - Level Two:
Value 500 Submission Rate 124 / 184 (67.39%) Success Rate 101 / 124 (81.45%) High Score Eryx for 486.46 points (4 mins 45 secs) Average Score 332.31 (for 101 correct submissions)
This was my favorite problem out of the bunch, as it was simple to state, and if you saw how to do it, it was also quite simple to solve, which led to some amazing scores. The trick to it was to notice that there are the same number of fractions in the set that are between 0 and 1, as there are between 1 and 2, and between any pair of adjacent integers. For example, consider the case where bound = 4. Between every pair of adjacent integers x and x+1, we have the following fractions, which can also be expressed as improper, reduced fractions, a/b:
x, x+(1/4), x+(1/3), x+(1/2), x+(2/3), x+(3/4), x+1
Now, lets say there are K reduced fractions between each pair of adjacent
integers (only counting one of the boundaries). Then, to find the
Nth fraction, we can use integer division to find
N/K, which gives us integral part of the fraction to be returned.
Next, to find the fractional part of the return, we find the
N%Kth smallest fraction between 0 and 1. Finally, add the
two together and return the result. The only missing piece of the puzzle is:
how do we calculate K, and how do we find the N%Kth smallest
fraction between 0 and 1. The answer is brute force. With a bound of no more
than about a 1000, there are clearly no more than a million fractions between 0
and 1, and in fact there are much fewer (around 300 thousand). With two nested
for loops, and a GCD function, we can simple enumerate all of the possible
fractions, make sure they are reduced, and then sort them once we have them all.
The only subtlety to this is that there is no fraction primitive, so unless
you've got your own fraction class handy (and many TopCoders do), you'll have to
deal with sorting the fractions. An alternative to this is to just use doubles,
but then you have to convert from a double to a fraction before you return the
result (doubles have plenty of precision in this case). In any event, the basic
idea remains the same - use brute force to count all the fractions up to 1, and
then use the division and modulus operators to compute the return.An even better, but much trickier, solution can be seen in Eryx' code. Rather than finding all the fraction and then sorting, he simply generates them in order! If you look at his code, the recursive sbpush method inserts all fractions between an/ad and bn/bd into his list, in order. In order to accomplish this, he successively splits the interval, inserting things from the lower half first. So, on the first call, he goes from 0/1 to 1/1. He splits this into 0/1 to 1/2 and 1/2 to 1/1. Then, the first of these is further split into 0/1 to 1/3 and 1/3 to 1/2, and so on. At each step, he first generates everything from an/ad to (an+bn)/(ad+bd), and then generates everything from (an+bn)/(ad+bd) to bn/bd. Its a bit more difficult to prove that this method does in fact generate all of the relevant fractions, but it can be done, though I'll leave it as an excercise. Driving
Used as: Division One - Level Three:
Value 1000 Submission Rate 32 / 184 (17.39%) Success Rate 16 / 32 (50.00%) High Score tomek for 596.95 points (27 mins 38 secs) Average Score 470.43 (for 16 correct submissions)
There are two different approaches that most coders took to this problem. In
both approaches, you need to be able to figure out the cost of a specific speed.
The linear interpolation method mentioned in the problem is left sort of vague,
so you have to figure out the details of the math. However, its fairly simple,
if you are interpolating a function, f(x), and want to find the value
of f(c)
between two points, a < b, then you find how far c is from
a, as a fraction of
the distance from a to b: (c-a)/(b-a). You then multiply this by the difference
(f(b)-f(a)), and finally add f(a) to the result. With this part of the problem
done, you still have to minimize the function. If you consider a sorted list of
all of the speeds in the input, you should look at the interval between each
pair of adjacent speeds in the list separately. Within one of these intervals,
if you look carefully at the cost function, you
will notice that it is of the form a+bx+c/x. The minima will be at the
point where the derivative is 0, so we can find the derivative,
b-c/x2, and then solve x = sqrt(c/b). If we find
each such value of x for all of the intervals, and check those along with all of the speeds in
the input, we are then guaranteed to find the minimum.
An alternative to this approach, which does not require calculus and derivatives
is to do a ternary search. This is similar to a binary search, except that it
is used on functions that are concave (like a quadratic, they have a single
minima or maxima). To find the minima of a function f(x) between to
points, a < b, you can use something like the following:
min = a;
max = b;
while(max > min+EPSILON){
double s1 = (2*min+max)/3;
double s2 = (min+2*max)/3;
if(f(s1) < f(s2)){
max = s2;
}else{
min = s1;
}
}
The idea here is that, at each iteration you chop off one third of the search
interval. Because the function is concave, you are guaranteed that the third
you chop off will not contain the minima. If you're not convinced, try drawing
out a few cases, and notice that no matter how you pick the two points to test,
cutting off the section as defined by the above algorithm will always leave the
minima in the search interval.Regardless of which approach you took, you needed to figure out the interpolation, and then realize the form of the function you were dealing with. If you got these two steps, and knew one of the two approaches mentioned above, the details of the implementation were not too bad.
