Saturday, December 23, 2008 Match summaryThe last SRM in this year gathered together not so many participants  1088, 488 in DivI and 600 in DivII. In DivI almost everybody solved the easy problem (partially because of good example cases). However, the other two problems were quite tough. This resulted in small number of solutions and only 4 coders solved all three problems. qizichao was much faster than anybody else (1st on the Hard and 3rd on the Medium overall) and got his first SRM victory with more than 300 points gap. zhuojie and Petr took second and third places, respectively, with very close scores. Both of them would have scored more, but resubmitted their Hards. Unfortunately, due to an ambiguity in the statement of DIIMedium problem, the SRM was not rated in DivII. The ProblemsMegaCoolNumbersEasyUsed as: Division Two  Level One:
The problem can be solved by generating all mega cool numbers between 1 and 1000, inclusive, and then counting how many of them does not exceed N. Generating 1 and 2digit mega cool numbers is trivial  all of them are mega cool, because any sequence of 1 or 2 numbers is an arithmetic progression. The only available 4digit number, 1000, is obviously not mega cool, so what's left is to generate 3digit numbers. To do this, let's iterate through all triples of digits (a, b, c), 1 ≤ a ≤ 9, 0 ≤ b, c ≤ 9. Each time the digits in this sequence form an arithmetic progression, i.e. b  a = c  b, we can tell that the number 100 * a + 10 * b + c is mega cool. Java implementation of this approach follows. import java.util.*; public class MegaCoolNumbersEasy { public int count(int N) { // let's add all mega cool numbers into the list ListFallingPoints Used as: Division Two  Level Two:
Let y[i] be the final ycoordinate for the ith falling point. We can calculate y's in sequential order. For the first point, there is no previous point, so it just falls down, i.e. y[0] = 0. Assuming we know y[i1], let's calculate y[i]. The ith point falls along the line x = X[i]. So we need to find the highest y when the distance between the points (X[i], y) and (X[i1], y[i1]) is equal to R. We can write this in form of mathematical equation and do some simple transformations: sqrt((X[i]  X[i1])^2 + (y  y[i1])^2) = R (X[i]  X[i1])^2 + (y  y[i1])^2 = R^2 (y  y[i1])^2 = R^2  (X[i]  X[i1])^2 The last equation doesn't have solutions if R^2  (X[i]  X[i1])^2 < 0 or, equivalently, X[i]  X[i1] > R (because the left part of the equation is always nonnegative and the right part is negative). In this case ith point will just fall down, i.e. y[i] = 0. Otherwise, we can take square root from both sides of the equation: y  y[i1] = +/sqrt(R^2  (X[i]  X[i1])^2) y = y[i1] +/ sqrt(R^2  (X[i]  X[i1])^2) Since we would like to know the highest possible value of y, we can deduce that y[i] = y[i1] + sqrt(R^2  (X[i]  X[i1])^2). Java implementation follows. public class FallingPoints { public double[] getHeights(int[] X, int R) { double[] y = new double[X.length]; y[0] = 0; for (int i=1; i < X.length; i++) if (Math.abs(X[i]  X[i1]) > R) y[i] = 0; else y[i] = y[i1] + Math.sqrt(R * R  (X[i]  X[i1]) * (X[i]  X[i1])); return y; } }SumAndProduct Used as: Division Two  Level Three:
We need to find the smallest n for which there exist n numbers x_{1}, x_{2}, ..., x_{n} > 0 such that x_{1} + x_{2} + ... + x_{n} = S and x_{1}x_{2}...x_{n} = P. To do this, it's enough to be able to answer the following question: for a given n and S which product values can we obtain using n nonnegative integers with their sum equal to S? First let's get some intuition by answering this question for n=1 and n=2. For n=1 the answer is trivial, the only one number x_{1} = S, so the product can only be equal to S. For n=2 we have two numbers x and y, x + y = S. The product is xy = x(S  x). Let's find for which values A the product can be equal to A. To do this, we need to solve the equation x(S  x) = A, which is equivalent to x^{2}  Sx + A = 0. The discriminant of this equation is D = S^{2}  4A. The equation has a solution if D > 0 <=> A ≤ S^{2}/4. Assuming A ≥ 0, it's easy to check that this solution x = S +/ sqrt(S^{2}  4A) is nonnegative. So, we've proved that using 2 numbers, we can obtain any product between 0 and S^{2}/4. Note that the maximum product S^{2}/4 is obtained when both numbers are equal to S/2. We can guess that the maximum product for n numbers is obtained when all of them are equal to S/n. And this guess is actually right as shows the following theorem. Theorem. Using n numbers with sum equal to S, we can obtain any product between 0 and (S/n)^{n}. Proof. Let's first show, that the product is maximal when all n numbers are the same. We already know that for 2 numbers this is true. Let's take n numbers for which the product is maximal and suppose that they are not the same. We can choose a minimal number m and a maximal number M among them and replace both of them to (m + M)/2. This will allow to increase the overall product. It contradicts to our assumption that taken numbers have the maximal product and proves that the product is maximal when all numbers are the same. Since when all number are the same, the product is (S/n)^{n}, it's only left to prove that for any A, 0 ≤ A ≤ (S/n)^{n}, it's possible to obtain the product A. We can do this constructively. Take a number B = A / (S/n)^{n2}. It's easy to see that 0 ≤ B ≤ (S/n)^{2}. Therefore we can choose two numbers x_{1} and x_{2} such that x_{1} + x_{2} = 2S/n and x_{1}x_{2} = B. Now it's enough to add numbers x_{3} = x_{4} = ... = x_{n} = S/n to obtain the required n numbers: x_{1} + x_{2} + ... + x_{n} = 2S/n + (n2)S/n = S and x_{1}x_{2}...x_{n} = B(S/n)^{n2} = A / (S/n)^{n2} * (S/n)^{n2} = A. End of proof. Using this theorem, we are now able to solve the problem. First, if S = P, just return 1. Otherwise, subsequently check n = 2, 3, ..., S. As only P ≤ (S/n)^{n}, return the current value of n. If we checked all these values of n and didn't find an appropriate one, for all subsequent values S/n < 1 and (S/n)^{n} < 1, therefore they will also not satisfy us. In this case solution doesn't exist and we should return 1. Can we be sure that our solution works fast enough? At the first glance, in the worst case it must check 1,000,000,000 candidates for n, so we can't. However, after a bit more careful analysis, it becomes clear that our solution is very fast. If S < 100, we will check at most 100 candidates and this is very fast. And if S > 100, the answer always exists and doesn't exceed 10, so we'll check at most 10 candidates. This is not hard to see: S / 10 > 10 and (S / 10)^{10} > 10^{10} > 1,000,000,000 ≥ P. Implementation is very easy. An example of Java implementation follows. public class SumAndProduct { public int smallestSet(int S, int P) { if (S == P) return 1; int n = 2; while (Math.pow(S / (double)n, n) < P) { n++; if (n > S) return 1; } return n; } }LaserShooting Used as: Division One  Level One:
The easiest way to solve this problem is using the fact that expected value of sum of several random variables is equal to the sum of expected values of each of these variables. Here, it means that we can calculate the expected number of hits for each of the obstacles (this number is actually the same as the probability to hit an obstacle) and return the sum of these numbers. To calculate the expected number for a single obstacle, take angles a_{1} and a_{2}  the angles of the rays that go exactly through the obstacle's ends (the angle of the ray that goes through the point (x, y) can be found as arctangent of y / x). Note that laser will hit the obstacle exactly in cases when the angle a of the shot lies between a_{1} and a_{2}. So, we need to calculate the probability that a random point thrown on a segment [Pi/2, Pi/2] of length Pi will fall within a segment [min(a_{1}, a_{2}), max(a_{1}, a_{2})] of length L = max(a_{1}, a_{2})  min(a_{1}, a_{2}). This probability is, of course, just L / Pi. Java implementation of this approach follows. public class LaserShooting { public double numberOfHits(int[] x, int[] y1, int[] y2) { double res = 0; for (int i=0; i < x.length; i++) { double a1 = Math.atan(y1[i] / (double)x[i]); double a2 = Math.atan(y2[i] / (double)x[i]); res += Math.abs(a1  a2) / Math.PI; } return res; } }MegaCoolNumbers Used as: Division One  Level Two:
The problem can be solved using dynamic programming, but first let's simplify the definition of mega cool number a bit. Note, that if the digits of a Ndigit number are split into X progressions and X < N, then they can be split into X + 1 progression as well. To do this, we can just take any progression that contains at least 2 digits and split it into 2 parts. Therefore, the only case when a number is of power A, but not of power A1, is when A is the smallest possible power of this number. So the number is mega cool of power A when A is its smallest power and its digits are in nondecreasing order. One important consequence is that there are no mega cool numbers of power more than 9. Since all digits of a mega cool number are in nondecreasing order, all equal digits stand in consecutive positions. For each distinct digit, we can create a progression containing all such digits. In such way, the number of progressions will be at most 9, and therefore the smallest power of such number can't be more than 9. Given a number, we can determine its smallest power using the following greedy algorithm. Assign the first digit to the first progression. For each next digit, if it can extend the current progression, then extend the progression with this digit, otherwise create a new progression containing only this digit. The correctness of this algorithm is straightforward to prove and it's left to the reader. Let's divide all idigit mega cool numbers into classes (pow, diff, last), where pow is the smallest power of the number, diff is the difference of the last progression in this number (assuming that progressions are generated using the greedy algorithm from the previous paragraph; special value diff = 9 can be used to indicate that the last progression consists only from one digit, so we don't yet know its difference) and last is the last digit of the number. Our goal is to calculate the amount of numbers from each class subsequently for i = 1, 2, ..., N. For i = 1 we have 1 number for each of the classes (1, 9, d), 1 ≤ d ≤ 9, and 0 numbers for all the other classes. Suppose we know all the information for some i = i_{0}. To calculate the information for i = i_{0} + 1, we need to iterate through all classes. For each class we need to check which numbers can be generated by adding 1 digit to each number from this class. There are 2 rules that can be used:
Using these rules, we can subsequently calculate the information for i = 2, 3, ..., N. The answer is the total amount of numbers in classes (A, diff, last) for i = N. Let's estimate the number of operations used by such solution, to see whether it's fast enough or not. For each i we have 9 * 10 * 9 = 810 states (1 ≤ pow, last ≤ 9, 0 ≤ diff ≤ 9). As 1 ≤ i ≤ N, the total number of states is at most 810,000. Processing each state requires checking at most 10 variants for the next digit, therefore the total number of operations is about 8,100,000, what is small enough to easily fit within 2 seconds. Java implementation of this approach follows. public class MegaCoolNumbers { final int MOD = 1000000007; public int count(int N, int A) { // there are no mega cool number of power more than 9 if (A > 9) return 0; // F[i][pow][diff][last] is the number of idigit mega // cool numbers from class (pow, diff, last) int[][][][] F = new int[N+1][10][10][10]; // initialize F for i=1 for (int d=1; d ≤= 9; d++) F[1][1][9][d] = 1; // calculate F for i=2, 3, ..., N for (int i=1; i < N; i++) for (int pow=1; pow <= 9; pow++) for (int last=1; last <= 9; last++) { for (int d=last; d <= 9; d++) { F[i+1][pow][dlast][d] += F[i][pow][9][last]; F[i+1][pow][dlast][d] %= MOD; } for (int diff=0; diff <= 8; diff++) for (int d=last; d <= 9; d++) if (d  last == diff) { F[i+1][pow][diff][d] += F[i][pow][diff][last]; F[i+1][pow][diff][d] %= MOD; } else if (pow < 9) { F[i+1][pow+1][9][d] += F[i][pow][diff][last]; F[i+1][pow+1][9][d] %= MOD; } } // calculate result and return it int res = 0; for (int last=1; last <= 9; last++) for (int diff=0; diff <= 9; diff++) res = (res + F[N][A][diff][last]) % MOD; return res; } }PerfectRectangles Used as: Division One  Level Three:
In order to solve this problem, it's helpful to be able for a given rectangle, consisting only of white cells, to determine whether it is perfect or not in time O(1). This can be done as follows. Let map_{i,j} be the cell in row i, column j, where each white cell is encoded as 0 and each black cell  as 1. A rectangle with its corners in cells (r_{1}, c_{1}) and (r_{2}, c_{2}), r_{1} ≤ r_{2}, c_{1} ≤ c_{2}, is perfect if it can't be extended in any of four possible directions. In other words, the part of row r_{1}1 directly over the rectangle must contain at least one black cell, and the same must hold for each of the following 3 parts: the part of row r_{2}+1 directly under the rectangle, the part of column c_{1}1 directly to the left from the rectangle and the part of column c_{2}+1 directly to the right from the rectangle. This can be written as mathematical inequalities: map_{r11,c1} + map_{r11,c1+1} + ... + map_{r11,c2} > 0, map_{r2+1,c1} + map_{r2+1,c1+1} + ... + map_{r2+1,c2} > 0, map_{r1,c11} + map_{r1+1,c11} + ... + map_{r2,c11} > 0 and map_{r1,c2+1} + map_{r1+1,c2+1} + ... + map_{r2,c2+1} > 0. So, in order to be able to check for perfectness in O(1), we need to be able to calculate the sums of values in arbitrary number of consecutive cells in the same row or column in 2dimensional matrix. This is quite a classic problem and it can be solved using cumulative sums. If sumRow_{i,j} = map_{i,0} + map_{i,1} + ... + map_{i,j}, then sum map_{i,j1} + map_{i,j1+1} + ... + map_{i,j2} can be calculated as sumRow_{i,j2}  sumRow_{i,j11}. Similarly, if sumCol_{i,j} = map_{0,j} + map_{1,j} + ... + map_{i,j}, then sum map_{i1,j} + map_{i1+1,j} + ... + map_{i2,j} can be calculated as sumCol_{i2,j}  sumCol_{i11,j}. Therefore, we can precalculate tables sumRow and sumCol in time O(N^{2}) and then be able to check perfectness in O(1) for a single rectangle. Now, let's describe an O(N^{3}) to this problem. It is not fast enough and will time out for given constraints, however it can be optimized for running time O(N^{2}) and we'll show how to do this. Let's iterate through all pairs of rows (r_{1}, r_{2}), r_{1} ≤ r_{2}, and calculate the number of perfect rectangles where the topmost row is r_{1} and the bottommost row is r_{2}. For a fixed pair (r_{1}, r_{2}) we can calculate an array of booleans isWhite, where isWhite[c] = true if and only if the part of column c between rows r_{1} and r_{2}, inclusive, contains only white cells. This array can be calculated in O(N) using cumulative sums in sumCol. Now, rectangle between columns c_{1} and c_{2}, c_{1} ≤ c_{2}, can potentially be perfect only if isWhite[c] = true for all c, c_{1} ≤ c ≤ c_{2} (otherwise it contains at least one black cell), isWhite[c_{1}1] = false (otherwise it can be extended to the left) and isWhite[c_{2}+1] = false (otherwise it can be extended to the right). Therefore, we need to find all maximal (by inclusion) consecutive sequences of true values in array isWhite and check for each of them whether it corresponds to a perfect rectangle or not. There can be at most N/2 such sequences and each of them can be checked in time O(1) using the method described above. The overall complexity of the obtained solution is O(N^{3}), because we need to check O(N^{2}) pairs (r_{1}, r_{2}). To get an O(N^{2}) solution, let's try to process all pairs of rows (r_{1}, r_{2}), where r_{2} is fixed, in linear time O(N). We will process all values of r_{1} in increasing order. Consider isWhite arrays for two consecutive r_{1} values. The difference between them is that some false values in an array for a lower r_{1} can turn to true in an array for a higher r_{1} (the reverse change from true to false is never possible). This change from false to true happens just once for each column. Let's define the height h(c) of column c as the number of white cells in this column starting from cell (r_{2}, c) and going up (i.e. cell (r_{2}h(c)+1, c) is still white, but cell (r_{2}h(c), c) is black). It's not hard to see that isWhite[c] changes from false to true when we consider r_{1} = r_{2}  h(c) + 1. These changes in isWhite from false to true are very important. Suppose we have isWhite array for some value of r_{1} and consider some maximal (by inclusion) sequence of true values in it. If none of these values has just recently changed from false to true (i.e. if none of them was false for the previous value of r_{1}), then rectangle corresponding to this sequence can be extended to the top and therefore it is certainly not perfect. So, for a given value of r_{1} we need to check not all maximal consecutive sequences of true values in isWhite, but only those sequences that contain at least one cell that has just recently changed from false to true. The algorithm for processing a fixed value of r_{2} can now be written as follows:
The only weak place in this algorithm is the part where we need to find the maximal consecutive sequence of true values containing some particular cell. If we are able to do such operation in O(1), the whole algorithm will run in O(N^{2}). In other words, we need to implement isWhite array as a data stucture that initially contains only false values and is able to perform the following operation in O(1): change value at a given position from false to true and return the maximal consecutive sequence of true values containing the given position. We can implement such data structure as an array of integers p satisfying to the following properties: if the value at position c is false, then p[c] = 1; for each maximal consecutive sequence of true values between positions l and r, inclusive, p[l] must be equal to r and p[r] must be equal to r; all other p values can be arbitrary. Having such an array p, the required operation can be implemented in O(1) using the following pseudocode: function changeValueAt(integer pos) if p[pos1] = 1 then l := pos else l:= p[pos1]; if p[pos+1] = 1 then r := pos else r := p[pos+1]; p[l] := r; p[r] := l; return the sequence between positions l and r, inclusive end function The idea for this code is simple. We find the maximal consecutive sequences of true values to the right and to the left from the given position and merge this sequences into one large sequence. The code also correctly handles cases when there is no sequence to the left and/or to the right from the given positions. Now we are ready to give complete Java implementation of this approach. import java.util.*; public class PerfectRectangles { int[][] sumRow, sumCol; // method for checking whether a given rectangle is perfect boolean isPerfect(int lx, int ly, int rx, int ry) { return sumRow[lx1][ry] != sumRow[lx1][ly1] && sumRow[rx+1][ry] != sumRow[rx+1][ly1] && sumCol[ly1][rx] != sumCol[ly1][lx1] && sumCol[ry+1][rx] != sumCol[ry+1][lx1]; } public int numberOfRectangles(int N, int M, int X0, int A, int B, int Y0, int C, int D) { // generate an initial table boolean[][] map = new boolean[N+2][N+2]; int x0 = X0 % N, y0 = Y0 % N; A%=N; B%=N; C%=N; D%=N; for (int i=0; i<M; i++) { map[x0+1][y0+1] = true; x0 = (x0 * A + B) % N; y0 = (y0 * C + D) % N; } // append black rows/columns from all 4 sides // (for simplicity of subsequent implementation) for (int i=0; i<=N+1; i++) for (int j=0; j<=N+1; j++) if (i==0  j==0  i==N+1  j==N+1) map[i][j] = true; // calculate arrays sumRow and sumCol sumRow = new int[N+2][N+2]; sumCol = new int[N+2][N+2]; for (int i=0; i<=N+1; i++) { sumRow[i][0] = (map[i][0] ? 1 : 0); for (int j=1; j<=N+1; j++) sumRow[i][j] = sumRow[i][j1] + (map[i][j] ? 1 : 0); } for (int j=0; j<=N+1; j++) { sumCol[j][0] = (map[0][j] ? 1 : 0); for (int i=1; i<=N+1; i++) sumCol[j][i] = sumCol[j][i1] + (map[i][j] ? 1 : 0); } int[] h = new int[N+2]; // heights of all columns int[] p = new int[N+2]; // data structure for isWhite array // the lists of moments when false changes to true in isRow // cnt is the number of moment for a given row // pos[r] contains the list of moment columns for the row r int[] cnt = new int[N+2]; int[][] pos = new int[N+2][N+2]; int res = 0; // iterate throw all values of r2 for (int i=0; i<=N+1; i++) { // update heights for (int j=0; j<=N+1; j++) if (!map[i][j]) h[j]++; else h[j]=0; // step 1 of the algorithm for a given r2 Arrays.fill(cnt, 0); for (int j=0; j<=N+1; j++) pos[h[j]][cnt[h[j]]++] = j; // step 2 of the algorithm for a given r2 Arrays.fill(p, 1); int L=1, R=1; for (int hh=N+1; hh>0; hh) for (int x=0; x < cnt[hh]; x++) { int pp = pos[hh][x]; L = (p[pp1]==1?pp:p[pp1]); R = (p[pp+1]==1?pp:p[pp+1]); p[L] = R; p[R] = L; if (isPerfect(i  hh + 1, L, i, R)) res++; } } return res; } } 
