Match Editorial

2006 TopCoder Open
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 Problems

SeparateConnections
Used as: Division One - Level One:

Value	350
Submission Rate	558 / 685 (81.46%)
Success Rate	317 / 558 (56.81%)
High Score	antimatter for 346.96 points (2 mins 39 secs)
Average Score	269.43 (for 317 correct submissions)

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:

Value	500
Submission Rate	438 / 685 (63.94%)
Success Rate	118 / 438 (26.94%)
High Score	IvanRomanov for 460.90 points (8 mins 25 secs)
Average Score	272.82 (for 118 correct submissions)

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 - 10k-1d)*10 + d = 10n - 10kd + d.

Solving 'R(n) = pn/q' for n, we obtain:

   n = dq(10k - 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:

Value	900
Submission Rate	219 / 685 (31.97%)
Success Rate	173 / 219 (79.00%)
High Score	Petr for 880.74 points (4 mins 13 secs)
Average Score	532.59 (for 173 correct submissions)

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->8

Then 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->3

Then 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

   L1, L2, ..., Lr

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,n-primes[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.