Match Editorial

The Problems

Division-II, Level 1: Cosines (200pt) 
94% submission rate (180/192)
74% success rate (133/180)
Best score w280sax, 195.37pt

This particular problem easily deserved its 200pt title, as almost the entire program was explained in the problem. The only potential problem is that their equations want the side lengths to be sorted, while the input is not necessarily sorted, and the only example case that demonstrates this is the last one. On the other hand, every language includes a sorting function of one sort or another, and those who took advantage of this generally had little trouble.

Most errors appear to stem from flawed sorting code, most of it being people using < and > instead of <= and >=, causing their programs to throw a metaphorical cog on inputs like 3,4,3 or 3,3,6. Some people tried to use clever tricks to avoid having to sort it straight off, and tricks are always prone to backfiring horrendously.

Division-II, Level 2: Mirror (500pt) 
82% submission rate (158/192)
45% success rate (71/158)
Best score jayberkenbilt, 479.73pt (time!)

There are quite a few ways to introduce special cases on this problem - it practically comes preloaded with them. In the end, though, a solution is simple.

Your first step is to parse out the hours and minutes, and your preferred method for this will vary based on your preferred language. StringTokenizer works nicely for Java, and one can use sscanf or a combination strchr and atoi on C++. I believe C# has regexps, but in any case this isn't difficult.

Your first step should be to get rid of that ugly 12. Programmers never count from 1, programmers always count from 0. Unfortunately, whoever designed clocks clearly doesn't see the beauty in this counting system. So we ignore them and do it ourselves. If the "hour" is 12, set it to 0. Problem solved.

Most people chose to handle the minutes and hours separately. Personally, I find it far easier to combine the two. Multiply "hour" by 60 and add it to "minutes". Now you've got the number of minutes past the hour. Now invert it and add 12 * 60. Now you've got the number of minutes past the hour on the inverted clock.

From here it's just a matter of extracting the hours and minutes again using division and modulus, remembering to change an hour of 0 to 12, and outputting it. You've got to be careful to use two digits on the "minutes" part - in C++, you can use sprintf with the formatting string "%d:%02d". Alternatively, a technique that should work in any language is to convert the minutes to a string, then check the length - if it's 1, add a '0' in front.

The core code, for the curious:

if( hour == 12 )
    hour = 0;
minute += hour * 60;
tempminute = 12 * 60 - minute;
newhour = newminute / 60;
newminute = tempminute % 60;
if( newhour == 0 )
    newhour = 12;

That code should work on any language that Topcoder supports.

It's worth noting that in the case of 12:00, newhour will end up 12 before the if statement to set it to 12. We get the right answer anyway, but things like that should be watched for.

The most common bug was to fail on "11:57", returning "0:03" instead of "12:03". A few other programs had subtler bugs.

Division-II, Level 3 & Division-I, Level 1: CheatCodes 

Div-II: (1050pt)
14% submission rate (26/192)
19% success rate (5/26)
Best score Ukraine, 560.95pt

Div-I: (300pt)
64% submission rate (71/111)
56% success rate (40/111)
Best score radeye, 235.28pt

This one was perhaps a bit undervalued in Division 1. At first glance it seemed easy, but requiring a keypress to belong to only one code - and not even having any explicit way to figure out *which* code until it's done - complicates things quite a bit.

The best way, in my opinion, is to loop through each button-press. For each button-press, just run through each code from first to last and check to see if that code fits, running *backwards* - as in, the button you're at is the

last one in the code sequence. If it does, add it to your code list and mark the key you're currently at with some "null" value that can't be used in an actual code (00000000 would work, or 11111111, or basically anything else, for that matter.) Once you get to the end, you're done.

Unfortunately, the length of the input cases on this one made testing a chore. I got tripped up by a flaw in my code that would have been found if I'd finished the test cases, but they took so long to input that I didn't want to. This same issue makes it nearly impossible to figure out what went wrong in most people's code.

Division-I, Level 2: CityRoads (650pt) 
27% submission rate (30/111)
43% success rate (13/30)
Best score bigg_nate, 588.71pt

There are, as far as I know, two major ways to do this. The first is to build an adjacency matrix and multiply it by itself "length" times. It's a little tricky to get this one fast enough - you have to use the fact that squaring a matrix twice does in fact raise it to the fourth power. Since I don't know much about matrix multiplication I'm going to leave that one up to the reader to implement :)

The solution I used was to make a big array of "how many ways can you get here". Fill it with 0 to start with, and set the "start" position to 1. Then just iterate length times, and each time, run through all the paths and add appropriately. For instance, if we know that we have a path from A to B, newways[ B ] += oldways[ A ]. If we have three paths from A to B, we just end up doing that three times. We also obviously must test for overflow - I did this by using -1 as an "overflow" value. If oldways[ A ] or newways[ B ] was -1, I just set newways[ B ] to -1 - if they weren't, I tested if newways[ B ] > newways[ B ] + oldways[ A ]. Overflows wrap around into negative, so if this apparently paradoxical statement was true, it signified an overflow.

Looking at it again, I didn't even need the oldways[ A ] == -1 test. If oldways[ A ] == -1, then obviously newways[ B ] > newways[ B ] + oldways[ A ]. But such is the advantage of hindsight.

Once we'd run through "length" times, it's just a matter of returning the value at the "end" position. Since we were clever enough to use -1 as an overflow value we don't even need to test, just blindly return the value that's there.

There's one major part of this that I'm skipping over, which is how to access something like oldways[ A ] when A is a string. Two ways to do this also. The first is to come up with some sort of a map from string to integer, then either convert all the roads before doing the loop or convert as you go. The second, which is what I'd do if I was reimplementing it, is to use the C++ STL. Instead of an int[ 100 ], I would use a map< string, int >. I'm not sure if the other languages have easy equivalents for this sort of a construction though.

Oh, yes - you need an int[ 100 ] because you could, in theory, have 50 roads that each lead from one spot to a different spot, each spot never referred to more than once. I don't know if anyone failed because of this, but it's something to watch out for. The begin and end are guaranteed to be in the road matrices somewhere, so you don't need 102. (I used 110 anyway.)

Division-I, Level 3: QuickDiv (850pt) 
23% submission rate (26/111)
46% success rate (12/26)
Best score lars, 826.48pt

I've got to admit here, I can't prove that my solution works. In fact, I'm not even entirely sure *how* it works. I did this one almost entirely on instinct, it appears. But I'll explain it anyway.

First off, it's obviously easy to determine how many numbers between 1 and N are a multiple of some number M. It's N/M. That's trivial.

So then it's also easy to determine how many numbers between 1 and N are a multiple of, say, A, B, or C. N/A + N/B + N/C. However, the problem is, what if it's a multiple of A *and* B? You'd count it twice. Well, the obvious solution now is to subtract. Multiply A and B and subtract the numbers that are multiples of both. N/A + N/B + N/C - N/(AB) - N/(AC) - N/(BC). However, what if it's a multiple of A, B, *and* C? We've just added three then subtracted three, we haven't noticed it at all! So let's multiply A, B, and C, and add *those* factors. N/A + N/B + N/C - N/(AB) - N/(AC) - N/(BC) + N/(ABC).

At this point I noticed a pattern I was working up to. If we have an even number of multiples, we subtract. If we have an odd number of multiples, we add. A little math proved to me that this same thing worked if it was a multiple of 4 different numbers: 4-6+4-1 = 1. If it's 5, it still works: 5-10+10-5+1 = 1. I decided to assume it worked all the way up, so to speak.

So we have a bunch of divisors. First we add all the multiples of each divisor. Then we subtract all the multiples of each pair of 2 multipied divisors. Then we add all the multiples of each 3 multiplied divisors. And so on, until we run out of numbers to start with.

So I tried this. And it *almost* worked. It got very close results, but not quite right - it was perfect on a lot of the examples, but it failed on two.

Eventually I figured it out. Say we have 50, 6,10. There are 8 multiples of 6 and 5 multiples of 10. 13 total. 6*10 is 60, and obviously we have no multiples of 60 from 1 to 50. But this answer is wrong - the right answer is 12. We're counting 30 twice, because 30 is still a factor of both 6 and 10!

The solution is the Least Common Multiple, of course, and just plugging that in to my function fixed the whole thing. Instead of N/A + N/B + N/C - N/(AB) - N/(AC) - N/(BC) + N/(ABC) the equation is actually N/A + N/B + N/C - N/LCM(A,B) - N/LCM(A,C) - N/LCM(B,C) + N/LCM(A,B,C). (LCM(A,B,C) == LCM(LCM(A,B),C).) In the end, that's actually all you need.

So: to summarize the whole solution. Start by choosing 1 number from the list of divisors. Add the number of multiples of it that are within the bounds. Repeat for each number in the list. Now choose 2 numbers from the list. Get the LCM of them, and *subtract* the number of multiples of that are within the bounds. Repeat for every combination of 2 numbers. Now choose 3, and do the same thing again, only add. Now 4, but subtract. Toggle the sign every step and add another divisor every step, until you run out of divisors.

Now you're done.

I hope this makes sense to somebody - I'm still a bit hazy on it myself, but then again, a lot of Topcoder seems to be about trusting your instincts.