Match Editorial

Match summary

In the SRM 409 we witnessed many great performances, fast submissions and high scores. The top three rated topcoders ACRush, tomek and Petr fought to the last seconds of the challenge phase to claim the match win.

The division 1 problems were simpler than usual, which allowed 78 coders to end up with over 1000 points. Petr once again showed his incredible skills by finishing with the fastest time on 250 and 900 points problems, and the second best time on the 600 pointer, taking only around 14 minutes of solving time to complete all three. But even that wasn't enough to leave ACRush far behind, as he got the fastest time on 600, and the second fastest on 900. A successful challenge allowed him to climb to the top, but only for a couple of minutes, until Petr also got a challenge what finally gave him his 45th division 1 SRM win.

In the division 2 scores weren't that high, mostly due to the difficult 1000 points problem, that only bogomaster ended up solving. However it was flexme who took the win with a very fast times on the first two problems and 100 points from challenges.

The Problems

Value	250
Submission Rate	807 / 923 (87.43%)
Success Rate	643 / 807 (79.68%)
High Score	ohhenrie for 249.23 points (1 mins 34 secs)
Average Score	190.72 (for 643 correct submissions)

This problem was a nice example, how taking more time on thinking about a solution can save you time, on a longer run. I'll show three solutions, each a bit harder to come up with, but on the other hand easier to implement.

Solution 1

Since the problem statement already gives the complete algorithm we can simply follow it directly and implement something like this:

That certainly works, but as you can see it requires some effort to code.

Solution 2

If you look closer at the algorithm, you can notice that every time we add something to the list, it's smaller than all the elements that are already there (we take the smallest element and cut it in half). So we don't have to traverse the whole list to get the minimum, just take the last element. Even more we don't really need to keep track of the whole list at all. Knowing the sum of elements, the last element, and the count of elements is all we need. That gives a much simpler code:

Not only it's faster to type, but what's more important, less complex code means less places where you can make bugs.

Solution 3

Consider what are the possible sticks lengths at the end of the algorithm.

• All of them are powers of 2 - We take 64 and keep dividing it by two.
• They are all distinct - In a middle of the algorithm we can have two occurrences of the same length, right after a break. But if we kept both halves it means that the sum was greater than x and one of them will be broken in the next step.
• The lenghts sum up to x.

That should look fammilar, as it's nothing else than a binary representation of x, where each stick represents one bit that is set.

It can't get any simpler than that.

Value	500
Submission Rate	516 / 923 (55.90%)
Success Rate	174 / 516 (33.72%)
High Score	dlwjdans for 476.31 points (6 mins 23 secs)
Average Score	294.49 (for 174 correct submissions)

Value	250
Submission Rate	616 / 640 (96.25%)
Success Rate	425 / 616 (68.99%)
High Score	Petr for 247.11 points (3 mins 5 secs)
Average Score	189.24 (for 425 correct submissions)

To understand better how an ordered superstring looks like, imagine that you've written a string S on a piece of paper, and now you want to write all the elements of words in rows beneath it - In a way that each word starts in the same column, or right from the previous word and characters in every column match. If it's possible to do that then S is an ordered superstring of words otherwise it isn't. For example

abbbcabbbcabb
abbbcabbbcabb    
abbbcabbbcabb    
abbbcabbbcabb
abbbcabbbcabb
abbbcabbbcabb

shows that "abbbcabbbcabb" is an ordered superstring of {"abbb", "bb", "bbb","c", "bb"}. Although not the shortest as you can also write:

abbbcbb
abbbcbb
abbbcbb
abbbcbb
abbbcbb
abbbcbb

Now how do we find this shortest ordered superstring? Just iterate over the words and place each word as far left as possible. Where possible means not earlier than the previous word, and matching the already placed characters. Here is a sample code:

Proof

What is left is to show that the algorithm actually always give the optimal solution. I'm going to use the "ad absurdum" argument, that is assuming that that there is a better solution and showing how that leads to a contradiction.

• (w₁...w_n) - input words.
• X - the ordered superstring generated by the above algorithm.
• (x₁...x_n) - indices at which words were placed by the above algorithm.
• Y - the shortest solution (we are assuming it's shorter than X).
• (y₁...y_n) - indices of words in Y.

What it does is, for each word if it fits entirely in the already generated string, move it as far left as possible. Note that the procedure doesn't change any letters, just generates a valid, non-decreasing, sequence of indices.

If y'_n < y_n we have a contradiction since Y was assumed to be the shortest superstring. Otherwise:

Take the first index where sequences (x₁...x_n) and (y'₁...y'_n) differ, and call it j.

• x_j < y'_j - Since while generating x_j it was placed as far left as possible.
• S - the string made from words (w₁...w_j) placed at indices (x₁..x_j).Note that it ends with w_j, because otherwise while generating y'_j it would've been made equal to x_j.
• Z - the substring of Y from the index y'_j to the end - It starts with w_j.

Now, since S and Z have an overlapping part (w_j), we can decrease indices (y'_j...y'_n) by y'_j - x_j resulting with a new ordered superstring, shorter than Y. Which contradicts that Y was the shortest, and completes the proof.

Value	1000
Submission Rate	17 / 923 (1.84%)
Success Rate	1 / 17 (5.88%)
High Score	bogomaster for 423.25 points (51 mins 18 secs)
Average Score	423.25 (for 1 correct submission)

The problem proved to be rather difficult, and only one competitor managed to solve it during the match. When you are facing a complex problem, it's always a good idea to see if it can be divided into simpler subproblems. And that's exactly what I want to show here, I'll break it down into few parts, each of them quite simple to solve on its own, and then glued together they'll give the full solution.

The general idea

After the first read of the problem you should get at least the following facts:

• You have cities connected with roads, which is probably the most common disguise for a graph problem. What's less common is that the graph isn't given explicitly, but described by a building algorithm given in the problem statement.
• You need to select a subset of vertices to put teleports on them.
• If you read the problem all the way down to the constraints section, you noticed that the number of teleports is at most 4, which should immediately turn on a glowing "bruteforce" sign inside your head.
• The inconvenience that you need to minimize is "the minimal number of roads one needs to follow..." so simply the minimal distance between two vertices in an undirected graph.

Constructing the graph

All that's to be done here, is directly following the algorithm given in the statement. For each of the cities, other than capital, we select another city and put an edge connecting them. And here's a code:

One little trick to note is that the dist function returns the square of the Euclidean distance. That's because we don't really need to know the actual distance, just be able to compare two distances. If we compare squares that allows us to avoid using floating point numbers. Not that it matters in this particular problem but it's a good habit to use exact arithmetic whenever you can.

Generating all possible teleports placements

What we basically need to do here is to iterate over all subsets of vertices that have size equal to teleportCount. There are few ways to do that, in example, if you are not afraid of a messy code, you can just use a number of nested for loops. But I prefer to do that with a recursive function, that at each level of recursion tests all the possible elements at a position, and keeps that elements are generated in the increasing order.

As you can see it's short and easy to code. If you are not sure why it works, try to output the values it generates and see the pattern they follow.

Measuring the inconvenience for the given teleports placement

From the definition of "the inconvenience of the whole Kingdom" we know that we need to compute the inconveniences of every city and take the maximum of them. To compute the inconvenience of the city we need to know its distance to the capital and to all the cities with teleports. To make things simpler we can start with precomputing distances between all the pairs of cities. Again in can be done in various ways, especially if you notice that the graph is in fact a tree. I choose to use the good old Floyd–Warshall algorithm, it's not the most efficient choice, but it's good enough for at most 50 vertices, and it's so simple to code.

With that done, computing the inconvenience of a city and of the whole Kingdom becomes only a matter of:

Putting it all together

Value	600
Submission Rate	297 / 640 (46.41%)
Success Rate	211 / 297 (71.04%)
High Score	ACRush for 574.84 points (5 mins 59 secs)
Average Score	381.98 (for 211 correct submissions)

To solve the problem we need to find the largest value, not greater then gnomesAvailable, that divides C(spheresCount + fakeSpheresCount, spheresCount), where the C(n,k) denotes the number of ways to chose k elements out of n. That's a well known function in Combinatorics and it can be computed using the formula (n!)/(k! * (n-k)!). Of course it's not feasible to directly compute the value of factorial of a number as big as two billion. But as it turns out we don't need to know the exact value to find it's divisors.

Consider the value of 13!, it can be written as

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13

To easily find it's divisors, we want to factorize it, and represent it as a multiplication of its exponented prime factors, that is 2^e₁ * 3^e₂ * 5^e₃...

To compute e₁ we need to know how many times 2 divides 13!, lets do that by looking at the above representation and counting occurrences of 2 for each factor separately.

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13
    X       X       X       X        X         X
            X               X                  X
                            X

You can notice the pattern, every second number adds 1 to the result, every fourth number adds additional 1, and so on for higher powers. The same thing happens for other prime factors, for example for 3:

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13
        X           X           X              X
                                X

If we follow that logic for all primes less than or equal to 13 we get 13! = 2^10 * 3^5 * 5^2 * 7 * 11 * 13, which, as you can check, is correct. That gives as a function to compute the exponent of the given prime factor of n!:

Now how to do the same thing for C(n,k)? Very simple, based on the (n!)/(k! * (n-k)! formula, it's just:

So to check if a number x divides the C(n,k) we only need to factorize it, and then see if all the exponents are less than equal to the corresponding exponents of C(n,k). Within the problem constraints it was enough to iterate over the possible team sizes and test them one by one. See the code of Ying for a clean implementation of exactly this idea.

There was also a faster way to find which team sizes are acceptable. Rather than checking each number separatly we can use a sieve-like method to eliminate all the numbers that are not acceptable. Notice that if in C(n,k) we have a prime factor p, and the corresponding exponent e. No number divisible by p^(e+1) will be a divisor of C(n,k), so we can iterate over all primes (found by the sieve of Eratosthenes), calculate q as p^(e+1), and mark all numbers divisible by q as incorrect. The highest unmarked number will be the answer.

Value	900
Submission Rate	140 / 640 (21.88%)
Success Rate	122 / 140 (87.14%)
High Score	Petr for 878.05 points (4 mins 30 secs)
Average Score	589.08 (for 122 correct submissions)

We are required to find the expected number of cells colored after K iterations.
From the definition of expected value, if you know how to calculate the probability that the given cell (x,y) gets colored, then the answer is just the sum of these probabilities over all cells.

Lets start with defining a function p(x,y) - probability that a cell at (x,y) gets covered by a single selection.
To calculate it we can count the number of different selections that cover it, divided by the total number of selections (which is rows*cols*rows*cols).

If a rectangle covers the cell(x,y) it's left side must be between 0 and x, and it's right side between x and (cols - 1), so there is a total of 2 * (x+1) * (cols-x) - 1 pairs of X-coordinates that cover x. The factor 2 comes from the fact that we can get the same pair of cells in two ways (A,B), or (B,A). The -1 at the end is to avoid counting twice in the case where both coordinates are the same. Analogically we compute it for y, so the final function looks like:

Once we have this we can compute the probability that the cell in not covered by a single selection, as 1-p(x,y). And further, since all the selections are independent, we compute the probability that the cell is not covered by K selections as (1-p(x,y))^K. That's all we need to complete the solution:

    public double area(int K, int rows, int cols) {
        double r =0;
        for(int i=0;i<cols;i++)for(int j=0;j<rows;j++){
            double p = p(i,j,rows,cols); //covered in a single selection
            double q = Math.pow(1-p, K); //not covered in K selections
            r+=1-q;                      //covered in K selections
        }
        return r;
    }