Tuesday, November 23, 2004 Match summary
New Slovakian speed coder misof let failed challenges trump him out of a win in his first match while Shadowfax21 edged him out of the lead. Almost 150 points behind them, new coder pure_ took a convincing third place in Division 2. Meanwhile, Division 1 was extremely exciting; the 900 point problem causing several lead changes due to resubmissions, challenges and a system test that took out nearly half of the remaining submissions. In the end, tomek took the lead, finishing all three problems without resubmitting and with time to spare. Two challenges widened his lead over Jan_Kuipers, who was the fastest to finish the hard problem but was set back by having to resubmit the medium problem twice. lars just stayed ahead of dgarthur's challengefest to take 3rd place.
The ProblemsLeapAgeUsed as: Division Two  Level One:
This problem was a reasonably simple counting problem  only simple because it was very possible within the constraints to try every year between born and year and count the leap years. A few coders attempted to be cleverer than that and do the problem without loops, but this turned out to be unnecessarily tricky and caused several failures. One twist to the problem was that the parameters didn't have to be leap years. Strangely, failed solutions failed on cases when they were leap years, more often than not, either from counting the first year or not counting the last year. Here's a simple solution: int count = 0; for (int y = born + 1; y <= year; y++) if (y%4 ==0 && (y%100 != 0  y%400 == 0)) count++; return count;HiddenNumbers Used as: Division Two  Level Two: Used as: Division One  Level One:
I think the premise of looking for numbers without knowing why must have been inspired by having watched the movie, "Holes". This parsing and sorting problem wasn't hard to figure out, but the particulars could be a problem to some implementations, including at least one which actually timed out. Another potential challenge was doing the comparisons for sorting, but the constraints allowed for the main piece of sorting to be done by converting the strings to 64bit integers and comparing them. Some coders discovered that parsing them as doubles and comparing them didn't necessarily work. After that, if they were equal in value, you had to account for how many leading zeros each had. If you know your language's mechanism for sorting with a custom comparer, the rest was easy, the final task being to leave out the right number of elements. The comparison could also be done without conversion to longs, like so: public int compare(Object o1, Object o2) { String s1 = (String)o1; String s2 = (String)o2; int originalLength1 = s1.length(); int originalLength2 = s2.length(); while (s1.startsWith("0")) s1 = s1.substring(1); while (s2.startsWith("0")) s2 = s2.substring(1); if (s1.length() > s2.length()) return 1; if (s2.length() > s1.length()) return 1; if (s1.equals(s2)) return originalLength1originalLength2; return s1.compareTo(s2); } Using this allows you to avoid worrying about the particulars of your language's stringtolong conversion. TaglishTranslatorUsed as: Division Two  Level Three:
I thought of this problem while reading complaints on the Round Tables about problems that favor native Englishspeakers over other coders. I wondered what would happen if I made a problem that specifically favored speakers of my favorite Austronesian language over native EnglishSpeakers. It didn't work however, as the only Tagalogspeaking contestant that I know of that opened the problem didn't have enough time to finish it. This problem was a parsing problem in its purest form  reading data in one format and spitting it back out in a different, somewhat unrelated format. It required reading in the input as an English sentence and determining what the noun, verb and sometimes object were. The problem required you to decide what tense the verb was, whether the subject and object were names or things, and whether the object (if it existed) was a direct or indirect object. At that point, it needed to be recreated with Tagalog syntax and verb conjugations. The hardest part of converting it to Tagalog syntax is doubling the first syllable of the verb root in some of the verb tenses. HeartsGameUsed as: Division One  Level Two:
This simulation problem turned out to be confusing at first to coders who didn't read the problem statement carefully enough. The thing that people didn't realize was that the input came in the order the cards were played, so the first card in each trick was the first card played, not the card played by player 1. In some ways, this made the problem easier and in other ways it made it harder, but it did make it harder to understand for several people. The real challenge to this problem, however, was figuring out who was cheating. In order to figure this out, you had to keep track of:
A good way to model this is to keep track of what players have "claimed" they are out of what suits. For instance, if the trick is led with a club and the player plays something else, they are claiming they are out of clubs. If a player leads a trick with a heart before hearts are broken, they are claiming that they are out of every other suit. As a special case, if a player plays a scoring card in the first trick, they are claiming they have no nonhearts except for possibly the Queen of Spades. At the end of the round, you had to return the scores for the noncheating players and the string "CHEATER!" for the cheating players. This requires that you tag which players cheated without messing up scoring in any way, particularly if a scoring player "shot the moon". RearrangeFurnitureUsed as: Division One  Level Three:
When I originally wrote this problem, I understood what made it tricky, but I wasn't completely sure what the best way was to solve it. The short, simple examples made the problem look deceptively easy, but some coders weren't fooled by this apparent simplicity, including the matchwinner, tomek and dgarthur, who resubmitted when he realized that he handled the hard case slightly wrong. A few coders noticed that this problem easily mapped to SillySort from the 2002 ICPC World Finals. What this problem was missing was SillySort's 3rd test case  one that showed that you couldn't just take the smallest unsorted element and swap it with whatever element belonged in its place. The key to figuring out this problem was to recognize that you needed to resolve cycles in the data  if you follow an item to the item that's in its spot, and then the one that's in the next one's spot, until you reach the original item again, you'll have a cycle of elements that should be in each others' spots. If an item is already in its spot, it forms a cycle of one element. The minimum cost of resolving a cycle is (sum of the weights in the cycle)+(number of elements in the cycle2)*(minimum weight in cycle). This cost is zero for oneelement cycles and the sum of the elements for twoelement cycles. For larger cycles, it is the cost of swapping the smallest element in the cycle with each element until all of them are in the right spot. The tricky part of this problem is figuring out that simply resolving all the cycles doesn't always give you the best answer. Sometimes the optimal answer comes by swapping the smallest element of the whole set into the cycle and then resolving the new cycle. The cost of swapping in the smallest element is the sum of that weight and the smallest weight in the cycle. The cost of resolving the new cycle is (sum of the weights in the cycle + minimum of all weights) + (number of elements in the cycle + 1) * (minimum of all weights). Sometimes this creates a smaller final value and sometimes it makes it bigger. The key to this problem was figuring out which cycles should merge with the smallest element and which should just be resolved. Here's a fairly simple implementation: //minimum of all elements: int min = Integer.MAX_VALUE; for (int i=0; i<weights.length; i++) min = Math.min(min, weights[i]); boolean[] done = new boolean[weights.length]; int total = 0; for (int i=0; i<weights.length; i++) { if (!done[i]) { int sum = 0; //sum of weights in a cycle int cyclemin = weights[i]; //minimum of weights in a cycle int ind = i; int count = 0; //number of weights in a cycle while (!done[ind]) { done[ind] = true; count++; sum += weights[ind]; cyclemin = Math.min(cyclemin, weights[ind]); ind = finalPositions[ind]; } //minimum of the cost to resolve and the cost to swap in and resolve. total += Math.min(sum+cyclemin*(count2), cyclemin+min+sum+min*count); } } return total; 
