Tuesday, January 15, 2008 Match summaryThe match started with registration troubles, which may have played a hand
in limiting the registration to In Division I, coders were treated to a quite simple easy, a technical but straightforward medium, and a hard that required little theory but a lot of optimisation. jakubr started out strong, solving the easy in under 90 seconds and also getting the fastest solution to the medium, but he wasn't able to solve the hard. At the end of coding, ainu7 was in first place, but a failed medium left him in fourth. ardiankp won the match, followed by Revenger and xhl_kogitsune. In Division II, the problems were mostly straightforward, and scores were quite high. Dottik won the match, having submitted all three problems in only 23 minutes. The ProblemsMonotoneSequenceUsed as: Division Two  Level One:
This can be implemented in linear time, but as is often the case with 250's in TopCoder, the most efficient solution just isn't worth the effort. The simplest solution is to iterate over all contiguous subsequences, then check whether each one is strictly monotone or not (e.g., with one check for increasing, another for decreasing). Exercises
Used as: Division Two  Level Two:
If we are going to change a vote, we might as well take it from the candidate with the most votes, and give it to our candidate. Keep doing this until our candidate has more votes than any other. Exercises:
Used as: Division Two  Level Three:
Smooth numbers play a role in the Quadratic Sieve, a method for efficiently factoring large numbers. For the constraints in this problem, a brute force approach will be too slow. The Sieve of Eratosthenes provides a good template on which to build a solution. The standard sieve simply marks numbers as prime or not prime, but we can extend it to mark numbers with their largest prime factor. Whenever we find a prime p, we promptly iterate through all multiples of p and indicate that the largest prime factor is p (it will be the largest known so far, since we discover primes in increasing order). In this part of the algorithm, we ignore k completely, and run the loop right up to N. Since this is essentially performing the same steps as the Sieve of Eratosthenes, the running time will have the same order of magnitude. Computing this running time is far from trivial, but it turns out to be O(N log log N). Since there are no divisions or mods in this solution, the constant factor is quite small. In the second part of the algorithm (or else concurrently with the first part), we count all the numbers up to N whose largest prime factor is at most k. Refer to A_A_Lunyov's solution for an example.
Exercises:
Used as: Division One  Level One:
This version of the problem was easily bruteforceable (see jakubr's solution for an example). For a discussion of more efficient ways to solve it, refer to the writeup of SmoothNumbersHard in Division II. InformFriendsUsed as: Division One  Level Two:
The timing of this problem was rather unfortunate, coming so soon after PolygonCover, which can be solved in a similar way. A subset with the property required is known as a dominating set, and the maximum number of independent dominating sets is known as the domatic number. The Domatic Number Problem is an area of ongoing research. For this problem, however, a basic O(3^{N}) algorithm suffices. The solution is based on dynamic programming: we compute the domatic number for every subset, in the context of the whole set: that is, each dominating set we consider must dominate the whole set, not merely the subset. To find the domatic number of a subset A, we pick a dominating set D ⊆ A and note that the domatic number of A is at least one more than that of A − D. By iterating over all subsets D of A and checking a precomputed table to determine whether a particular D is dominating, this can be implemented in O(3^{N}) time. See jakubr's solution as an example. Exercises:
Used as: Division One  Level Three:
There were only five correct solutions to this problem, and between them they implemented 3 different solutions. ardiankp, ainu7 and xhl_kogitsune used an approach based on wildcards: once a number, say 1234567, has been allocated, mark any pattern with separation  1 of those bits replaced with a wildcard as unusable. For example, if separation = 3, then ??34567, 1?3?567, 123?56? and so on are all marked invalid. See ainu7's solution for an example. The intended solution was more of a brute force, but with some optimisations for the separation = 3 case. The most important optimisation is to meet in the middle: instead of marking numbers at a distance of 2 as illegal, mark those at a distance of 1, and check whether a candidate is a distance of 1 from a marked number. Other optimisations are mainly tricks to skip over candidates without explicitly testing them, and lowlevel optimisations like storing booleans in bit vectors instead of one per byte. See Jedi_Knight's solution for an example. Revenger's solution makes a clever optimisation to the brute force algorithm, based on an observed pattern: for the numbers encountered in the constraints, the solution is always just k  1 (in hex), with two extra digits appended (this is not true if the total number of digits is larger). It keeps a list of all the allocated numbers, and uses the observation to quickly find the numbers in the list that are of interest in testing a candidate. There is yet another solution attempted by several contestants, but none successfully. Revenger's observation can be taken further: the last separation  1 digits form a kind of checksum on the digits of k  1. I've written a solution based on this that passed all the system tests, but I don't have a proof of correctness when separation is 3. Exercises:

