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 everspeedy 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 ProblemsCalendarHTMLUsed as: Division One  Level One:
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. NthFractionUsed as: Division One  Level Two:
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+1Now, lets say there are K reduced fractions between each pair of adjacent integers (only counting one of the boundaries). Then, to find the N^{th} 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%K^{th} 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%K^{th} 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:
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: (ca)/(ba). 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,
bc/x^{2}, 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. 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. 
