JOIN
 Match Editorial
SRM 409
Thursday, July 10, 2008

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

Stick
Used as: Division Two - Level One:
 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:

1     int sum(ArrayList<Integer> A) {
2         int r = 0;
3         for (int y : A) r += y;
4         return r;
5     }
6
7     public int pieces(int x) {
8         ArrayList<Integer> A = new ArrayList<Integer>();
10         while (sum(A) > x) {
11             int minIndex = 0;
12             for (int i = 0; i < A.size(); i++)
13                 if (A.get(i) < A.get(minIndex)) minIndex = i;
14             int newPiece = A.get(minIndex) / 2;
15             A.remove(minIndex);
17             if (sum(A) < x)
19         }
20         return A.size();
21     }

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:

1     public int pieces(int x) {
2         int sum = 64;
3         int count = 1;
4         int last = 64;
5         while (sum > x) {
6             int newPiece = last / 2;
7             if (sum - newPiece >= x) sum -= newPiece; // discard one piece
8             else count++; // sum doesn't change, count does.
9             last = newPiece;
10         }
11         return count;
12     }

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.

1     public int pieces(int x) {
2         return Integer.bitCount(x);
3     }

It can't get any simpler than that.

OrderedSuperString
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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:

1     public int getLength(String[] words) {
2         String superString = "";
3         int last = 0;
4         for (String w : words) {
5             for (int i = last; i <= superString.length(); i++) {  //checking all positions
6                 int common = Math.min(superString.length() - i, w.length());  //length of the overlapping part
7                 String a = superString.substring(i, i + common);
8                 String b = w.substring(0, common);
9                 if (a.equals(b)) {  //match found
10                     superString += w.substring(common);
11                     last = i;
12                     break;
13                 }
14             }
15         }
16         return superString.length();
17     }

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

• (w1...wn) - input words.
• X - the ordered superstring generated by the above algorithm.
• (x1...xn) - indices at which words were placed by the above algorithm.
• Y - the shortest solution (we are assuming it's shorter than X).
• (y1...yn) - indices of words in Y.
First I'm going to generate a sequence of indices (y'1...y'n), with the following algorithm:
y'1 = y1
for i=2 to n
S - the string made from words (w1...wi-1) placed at indices (y'1..y'i-1).
if (there is an index z >= y'i-1 such as wi is a substring of S that starts at index z)
y'_i = z (if there are more than one possible indices choose the lowest).
else
y'i = yi
end

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 < yn we have a contradiction since Y was assumed to be the shortest superstring. Otherwise:

Take the first index where sequences (x1...xn) and (y'1...y'n) differ, and call it j.

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

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

TeleportsNetwork
Used as: Division Two - Level Three:
 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:

long dist(long x1, long y1, long x2, long y2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

int getTarget(int city, int[] X, int[] Y) {
long myCapDist = dist(X[city], Y[city], X[0], Y[0]);
ArrayList<Integer> candidates = new ArrayList<Integer>();
for (int p = 0; p < n; p++) {
long capDist = dist(X[p], Y[p], X[0], Y[0]);
if (capDist < myCapDist)
candidates.add(p); // consider only cities closer to the capital
}
int best = -1; // index of the best city found
long bestDistance = Long.MAX_VALUE;
for (int p : candidates) {
long d = dist(X[city], Y[city], X[p], Y[p]);
if (d < bestDistance) {
bestDistance = d;
best = p;
} else if (d == bestDistance) {
if (X[p] < X[best] // first tie-breaker
|| (X[p] == X[best] && Y[p] < Y[best])) { // second tie-breaker
best = p;
}
}
}
return best;
}

boolean[][] buildGraph(int[]X, int[]Y){
boolean[][]G = new boolean[n][n];
for(int i=1;i<G.length;i++){
int j=getTarget(i, X, Y);
G[i][j]=G[j][i]=true;
}
return G;
}

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.

void allCombinations( int index, int minValue, int[] teleports){
if(index==teleports.length){
//do something with the teleports here
}else{
for(int i=minValue;i<n;i++){
teleports[index] = i;
allCombinations(index + 1, i+1, teleports);
}
}
}

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.

int[][] getDistances(boolean[][]G){
int[][]D = new int[n][n];
for(int[]d:D)Arrays.fill(d,1000);
for(int i=0;i<n;i++){
D[i][i]=0;
for(int j=0;j<n;j++)if(G[i][j])D[i][j]=1;
}
for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)
D[i][j]=Math.min(D[i][j],D[i][k]+D[k][j]);
return D;
}

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

int inconv(int p, int[]teleports){
int res = D[p][0];
for(int q:teleports)res = Math.min(res, D[p][q]);
return res;
}

int kingdomInconv(int[]teleports){
int maxIncov =0;
for(int p=0;p<n;p++)maxIncov = Math.max(maxIncov, inconv(p,teleports));
return maxIncov;
}

### Putting it all together

And this way we are basically done. Change the line
//do something with the teleports here
to
result = Math.min(result, kingdomInconv(teleports)); //result is a class variable

And call the already written methods:

int n;
int result = 1000;
int[][] D;

public int distribute(int teleportCount, int[] citiesX, int[] citiesY) {
n= citiesX.length;
boolean[][] G = buildGraph(citiesX, citiesY);
D = getDistances(G);
allCombinations(0,0,new int[teleportCount]);
return result;
}

MagicalSpheres
Used as: Division One - Level Two:
 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^e1 * 3^e2 * 5^e3...

To compute e1 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!:

long count(long p, long n){
long res =0;
long q=p;
while(q<=n){
res+=n/q;
q*=p;
}
return res;
}

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

count(p, n) - count(p, k) - count(p, n-k)

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.

GridColoring
Used as: Division One - Level Three:
 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:

double p(double x, double y, double rows, double cols ){
double rx = 2*(x+1)*(cols-x)-1;
double ry = 2*(y+1)*(rows-y)-1;
return rx*ry/(rows*rows*cols*cols);
}

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;
}

By slex
TopCoder Member