Match Editorial

Match summary

The match started with registration troubles, which may have played a hand in limiting the registration to only 1424 contestants in spite of the prize money. Fortunately, TheFaxman worked his usual magic and the match was able to proceed.

In Division I, coders were treated to a quite simple easy, a technical but straight-forward 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 straight-forward, and scores were quite high. Dottik won the match, having submitted all three problems in only 23 minutes.

The Problems

Value	250
Submission Rate	662 / 708 (93.50%)
Success Rate	378 / 662 (57.10%)
High Score	mRefaat for 248.65 points (2 mins 5 secs)
Average Score	203.69 (for 378 correct submissions)

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

1. Write a solution that works in linear time.

Value	500
Submission Rate	618 / 708 (87.29%)
Success Rate	424 / 618 (68.61%)
High Score	morshed for 498.22 points (1 mins 42 secs)
Average Score	409.81 (for 424 correct submissions)

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:

1. Solve the problem assuming that the number of votes is very large, so that it is infeasible to work one vote at the time. The running time of your solution should be independent of the number of voters, assuming that you have an integer type large enough to manipulate vote counts.

Value	1000
Submission Rate	209 / 708 (29.52%)
Success Rate	85 / 209 (40.67%)
High Score	A_A_Lunyov for 928.13 points (8 mins 1 secs)
Average Score	571.67 (for 85 correct submissions)

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:

1. Find a solution that takes O(N log log k) time.
2. Find a solution for k = 100 and N up to 10¹⁸ (hint: you don't need to identify the smooth numbers, just count them).

Value	250
Submission Rate	618 / 629 (98.25%)
Success Rate	568 / 618 (91.91%)
High Score	jakubr for 249.63 points (1 mins 6 secs)
Average Score	216.25 (for 568 correct submissions)

This version of the problem was easily brute-forceable (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.

Value	500
Submission Rate	392 / 629 (62.32%)
Success Rate	246 / 392 (62.76%)
High Score	jakubr for 476.67 points (6 mins 20 secs)
Average Score	320.12 (for 246 correct submissions)

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 pre-computed 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:

1. Prove that the running time of this algorithm is O(3^N).

Value	1000
Submission Rate	23 / 629 (3.66%)
Success Rate	5 / 23 (21.74%)
High Score	ainu7 for 671.71 points (22 mins 17 secs)
Average Score	538.63 (for 5 correct submissions)

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 low-level 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:

1. What data structures would you use to implement the wildcard-based solution efficiently?
2. Prove that the observation used in Jedi_Knight's solution eventually breaks down if the number of digits and k are unbounded.
3. Find the checksum formulae referred to above (it is easiest by observation, so you should have a working solution handy).
4. Prove the formulae you found. This is not too difficult when separation is 2, but I haven't solved this yet for separation = 3.