Online Round 1 March 4, 2006 Match summary Other complications aside, the problem set for this round generated very few questions. Each statement was fairly succinct, but as we all know, tricky problems can have simple descriptions. The medium, which had the shortest problem statement, also had the fewest number of correct submissions. The usual suspects solved all three problems fairly quickly. Petr took first place by almost 150 points. kia, the second place finisher, earned 200 points challenging level 2 submissions. The ProblemsSeparateConnectionsUsed as: Division One  Level One:
This problem required coders to find a maximum matching in an arbitrary graph. This is much trickier than the bipartite case, but luckily the constraints allowed for many simpler solutions. One possible solution is to consider all possible ways of splitting the nodes into 2 roughly equal sized groups, and then run bipartite matching each time. Another is to sort the nodes by degree, and then run a simple recursive algorithm that tries to add, for each node n, any available edge incident to n to the matching. The most popular approach, which will be described here, was memoization. Using this technique, antimatter was able to solve the problem in 2 minutes and 39 seconds! To solve the problem using memoization, we write a function: int solve(int bitmask, boolean[][] adjacencyMatrix)Given a bitmask describing some subset of the vertices, solve will determine the largest matching using only those vertices. For each edge e between allowed vertices, we recursively call solve on the smaller vertex set obtained by removing the ends of e. Using the bitmask as a cache key, we can memoize solve, and thus achieve a fast enough algorithm to pass systests. FirstToLast Used as: Division One  Level Two:
Our goal is to find the smallest positive integer n (less than 2 billion) such that R(n) = pn/q,where R(n) (rotate) is obtained by removing the leftmost (most significant) digit of n and attaching it on the right side. For example, R(71) = 17 and R(103) = 31. We first analyze the behavior of R(n) when n has k digits, and the leftmost digit is d: R(n) = (n  10^{k1}d)*10 + d = 10n  10^{k}d + d.Solving 'R(n) = pn/q' for n, we obtain: n = dq(10^{k}  1)/(10q  p).The denominator causes some worry, but observe that R(x) is always less than 10x, so we can immediately return 1 if p >= 10q. This formula is nice, since we can try all possible d and k values very quickly, and each time get an n. Then we simply check that this generated n actually has length k and starts with d. We return the smallest positive n less than 2 billion that works, or 1 if none do. NumPermutationOrders Used as: Division One  Level Three:
Here we must find the number of possible orders of permutations on the set S = {1,...,n}. The order of a permutation p is the smallest positive k such that p^{k} = 1, where 1 is the identity permutation. When working with permutations, one often looks at their cycle structure. For example, suppose we have the following permutation p: 1>3, 2>6, 3>5, 4>1, 5>4, 6>7, 7>2, 8>8Then we can also write p as (1 3 5 4)(2 6 7)(8), where the numbers in parentheses represent cycles. As another example, suppose q is defined as follows: 1>2, 2>1, 3>4, 4>3Then the cycle structure of q is (1 2)(3 4). To obtain the cycle structure we just begin at 1, and keep apply the permutation until we reach 1 again. Then we repeat this process on another value. Looking at the cycle structure, we can see that the order of p is 12 and the order of q is 2. As it turns out, the order of a permutation is actually the least common multiple (lcm) of the lengths of its cycles. Our problem actually looks at this issue from another direction: which orders are possible? An order k is possible if we can write a permutation S whose cycle lengths add up to n, and the lcm of the lengths is k. Since we can always tag on cycles of length 1, we can relax these constraints by letting the cycle lengths sum up to a value that is at most n. So now we are basically looking for a sequence of lengths L_{1}, L_{2}, ..., L_{r}whose sum is minimal, and whose lcm is k. We can achieve this by using distinct prime powers for each L_{i}. Thus, we can solve this problem by determining the number of sums of distinct prime powers that are less than n. To solve this new problem, we first enumerate all primes less than or equal to n. Then we write a function int solve(int primeIndex, int n, int[] primes)which determines the number of distinct prime power sums less than n using only the elements of primes whose indices are at least primeIndex. We can implement solve recursively by trying various powers of primes[primeIndex], and then calling solve(primeIndex+1,nprimes[primeIndex]^{j},primes)to solve the associated subproblem. Using primeIndex and n as the cache key, we can memoize this function, and thus obtain a quick enough solution to pass tests. 
