Thursday, July 10, 2008 Match summaryIn 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 ProblemsStickUsed as: Division Two  Level One:
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 1Since 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>(); 9 A.add(64); 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); 16 A.add(newPiece); 17 if (sum(A) < x) 18 A.add(newPiece); 19 } 20 return A.size(); 21 } That certainly works, but as you can see it requires some effort to code. Solution 2If 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 3Consider what are the possible sticks lengths at the end of the algorithm.
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. OrderedSuperStringUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 } ProofWhat 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.
y'_{1} = y_{1} for i=2 to n S  the string made from words (w_{1}...w_{i1}) placed at indices (y'_{1}..y'_{i1}). if (there is an index z >= y'_{i1} such as w_{i} 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} = y_{i} 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, nondecreasing, 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_{1}...x_{n}) and (y'_{1}...y'_{n}) differ, and call it 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. TeleportsNetworkUsed as: Division Two  Level Three:
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 ideaAfter the first read of the problem you should get at least the following facts:
Constructing the graphAll 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 tiebreaker  (X[p] == X[best] && Y[p] < Y[best])) { // second tiebreaker 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 placementsWhat 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 placementFrom 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 togetherAnd 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:
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! * (nk)!). 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_{1} * 3^e_{2} * 5^e_{3}... To compute e_{1} 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! * (nk)! formula, it's just: count(p, n)  count(p, k)  count(p, nk)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 sievelike 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. GridColoringUsed as: Division One  Level Three:
We are required to find the expected number of cells colored after K iterations. Lets start with defining a function p(x,y)  probability that a cell at (x,y) gets covered by a single selection. 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) * (colsx)  1 pairs of Xcoordinates 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)*(colsx)1; double ry = 2*(y+1)*(rowsy)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 1p(x,y). And further, since all the selections are independent, we compute the probability that the cell is not covered by K selections as (1p(x,y))^K. That's all we need to complete the solution:
public double area(int K, int rows, int cols) { 
