JOIN
 Match Editorial
SRM 388
Tuesday, January 15, 2008

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

MonotoneSequence
Used as: Division Two - Level One:
 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.
VoteRigging
Used as: Division Two - Level Two:
 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.
SmoothNumbersHard
Used as: Division Two - Level Three:
 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 1018 (hint: you don't need to identify the smooth numbers, just count them).
SmoothNumbers
Used as: Division One - Level One:
 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.

InformFriends
Used as: Division One - Level Two:
 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(3N) 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(3N) time. See jakubr's solution as an example.

Exercises:

1. Prove that the running time of this algorithm is O(3N).
TelephoneNumbers
Used as: Division One - Level Three:
 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.

By bmerry
TopCoder Member