Match Editorial

Match summary

The last SRM in this year gathered together not so many participants - 1088, 488 in Div-I and 600 in Div-II. In Div-I 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 DII-Medium problem, the SRM was not rated in Div-II.

The Problems

Value	250
Submission Rate	553 / 600 (92.17%)
Success Rate	481 / 553 (86.98%)
High Score	yash_iiith for 248.65 points (2 mins 5 secs)
Average Score	205.22 (for 481 correct submissions)

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 2-digit 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 4-digit number, 1000, is obviously not mega cool, so what's left is to generate 3-digit 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
    List megaCool = new ArrayList();
	
    // add all 1 and 2-digit numbers
    for (int i=1; i<100; i++)
      megaCool.add(i);
    // add all 3-digit numbers
    for (int a=1; a<=9; a++)
      for (int b=0; b<=9; b++)
        for (int c=0; cv=9; c++)
          if (b - a == c - b)
            megaCool.add(100 * a + 10 * b + c);
    // check how many mega cool numbers does not exceed N
    int res = 0;		
    for (int num : megaCool)
      if (num <= N)
        res++;
    // return result
    return res;
  }
}

Value	500
Submission Rate	486 / 600 (81.00%)
Success Rate	194 / 486 (39.92%)
High Score	yash_iiith for 498.91 points (1 mins 20 secs)
Average Score	318.09 (for 194 correct submissions)

Let y[i] be the final y-coordinate for the i-th 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[i-1], let's calculate y[i]. The i-th 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[i-1], y[i-1]) is equal to R. We can write this in form of mathematical equation and do some simple transformations:

  sqrt((X[i] - X[i-1])^2 + (y - y[i-1])^2) = R
  (X[i] - X[i-1])^2 + (y - y[i-1])^2 = R^2
  (y - y[i-1])^2 = R^2 - (X[i] - X[i-1])^2

The last equation doesn't have solutions if R^2 - (X[i] - X[i-1])^2 < 0 or, equivalently, |X[i] - X[i-1]| > R (because the left part of the equation is always non-negative and the right part is negative). In this case i-th point will just fall down, i.e. y[i] = 0. Otherwise, we can take square root from both sides of the equation:

  y - y[i-1] = +/-sqrt(R^2 - (X[i] - X[i-1])^2)
  y = y[i-1] +/- sqrt(R^2 - (X[i] - X[i-1])^2)

Since we would like to know the highest possible value of y, we can deduce that y[i] = y[i-1] + sqrt(R^2 - (X[i] - X[i-1])^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[i-1]) > R)
        y[i] = 0;
      else
        y[i] = y[i-1] + Math.sqrt(R * R - (X[i] - X[i-1]) * (X[i] - X[i-1]));
    return y;
  }
}

Value	1000
Submission Rate	91 / 600 (15.17%)
Success Rate	16 / 91 (17.58%)
High Score	xianchao for 692.18 points (15 mins 25 secs)
Average Score	440.03 (for 16 correct submissions)

We need to find the smallest n for which there exist n numbers x₁, x₂, ..., x_n > 0 such that x₁ + x₂ + ... + x_n = S and x₁x₂...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 non-negative 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₁ = 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² - Sx + A = 0. The discriminant of this equation is D = S² - 4A. The equation has a solution if D > 0 <=> A ≤ S²/4. Assuming A ≥ 0, it's easy to check that this solution x = S +/- sqrt(S² - 4A) is non-negative.

So, we've proved that using 2 numbers, we can obtain any product between 0 and S²/4. Note that the maximum product S²/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)ⁿ.

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)ⁿ, it's only left to prove that for any A, 0 ≤ A ≤ (S/n)ⁿ, it's possible to obtain the product A. We can do this constructively. Take a number B = A / (S/n)^n-2. It's easy to see that 0 ≤ B ≤ (S/n)². Therefore we can choose two numbers x₁ and x₂ such that x₁ + x₂ = 2S/n and x₁x₂ = B. Now it's enough to add numbers x₃ = x₄ = ... = x_n = S/n to obtain the required n numbers: x₁ + x₂ + ... + x_n = 2S/n + (n-2)S/n = S and x₁x₂...x_n = B(S/n)^n-2 = A / (S/n)^n-2 * (S/n)^n-2 = 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)ⁿ, 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)ⁿ < 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¹⁰ > 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;
  }
}

Value	250
Submission Rate	463 / 488 (94.88%)
Success Rate	453 / 463 (97.84%)
High Score	blueblimp for 249.21 points (1 mins 36 secs)
Average Score	200.67 (for 453 correct submissions)

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₁ and a₂ - 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₁ and a₂. 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₁, a₂), max(a₁, a₂)] of length L = max(a₁, a₂) - min(a₁, a₂). 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;
  }
}

Value	500
Submission Rate	52 / 488 (10.66%)
Success Rate	39 / 52 (75.00%)
High Score	AS1_PML30 for 409.92 points (13 mins 58 secs)
Average Score	252.67 (for 39 correct submissions)

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 N-digit 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 A-1, 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 non-decreasing 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 non-decreasing 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 i-digit 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₀. To calculate the information for i = i₀ + 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:

• For each number from class (pow, 9, last) we can add any next digit d, last ≤ d ≤ 9, extend the current progression by this digit and obtain a number from class (pow, d - last, d).
• For each number from class (pow, diff, last), 0 ≤ diff < 9, we can add any next digit d, last ≤ d ≤ 9. If d - last = diff, we can extend the current progression and will obtain a number from class (pow, diff, d), otherwise we must start a new progression and the number will be from class (pow + 1, 9, d).

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 i-digit 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][d-last][d] += F[i][pow][9][last];
            F[i+1][pow][d-last][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;
  }
}

Value	1000
Submission Rate	30 / 488 (6.15%)
Success Rate	11 / 30 (36.67%)
High Score	qizichao for 702.02 points (20 mins 25 secs)
Average Score	497.64 (for 11 correct submissions)

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₁, c₁) and (r₂, c₂), r₁ ≤ r₂, c₁ ≤ c₂, is perfect if it can't be extended in any of four possible directions. In other words, the part of row r₁-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₂+1 directly under the rectangle, the part of column c₁-1 directly to the left from the rectangle and the part of column c₂+1 directly to the right from the rectangle. This can be written as mathematical inequalities: map_r1-1,c1 + map_r1-1,c1+1 + ... + map_r1-1,c2 > 0, map_r2+1,c1 + map_r2+1,c1+1 + ... + map_r2+1,c2 > 0, map_r1,c1-1 + map_r1+1,c1-1 + ... + map_r2,c1-1 > 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 2-dimensional 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,j1-1. 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_i1-1,j. Therefore, we can precalculate tables sumRow and sumCol in time O(N²) and then be able to check perfectness in O(1) for a single rectangle.

Now, let's describe an O(N³) 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²) and we'll show how to do this. Let's iterate through all pairs of rows (r₁, r₂), r₁ ≤ r₂, and calculate the number of perfect rectangles where the topmost row is r₁ and the bottommost row is r₂. For a fixed pair (r₁, r₂) we can calculate an array of booleans isWhite, where isWhite[c] = true if and only if the part of column c between rows r₁ and r₂, inclusive, contains only white cells. This array can be calculated in O(N) using cumulative sums in sumCol. Now, rectangle between columns c₁ and c₂, c₁ ≤ c₂, can potentially be perfect only if isWhite[c] = true for all c, c₁ ≤ c ≤ c₂ (otherwise it contains at least one black cell), isWhite[c₁-1] = false (otherwise it can be extended to the left) and isWhite[c₂+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³), because we need to check O(N²) pairs (r₁, r₂).

To get an O(N²) solution, let's try to process all pairs of rows (r₁, r₂), where r₂ is fixed, in linear time O(N). We will process all values of r₁ in increasing order. Consider isWhite arrays for two consecutive r₁ values. The difference between them is that some false values in an array for a lower r₁ can turn to true in an array for a higher r₁ (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₂, c) and going up (i.e. cell (r₂-h(c)+1, c) is still white, but cell (r₂-h(c), c) is black). It's not hard to see that isWhite[c] changes from false to true when we consider r₁ = r₂ - h(c) + 1.

These changes in isWhite from false to true are very important. Suppose we have isWhite array for some value of r₁ 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₁), 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₁ 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₂ can now be written as follows:

1. For each value of r₁ create a list of cells where isWhite changes from false to true. To do this, for each value of c, add it into the list for r₁ = r₂ - h(c) + 1.
2. Process r1 from top to bottom. For each value of r1 check all cells from the list builded at the previous step. For each such cell find the maximal consecutive sequence of true values in array isWhite containing this cell and check whether it corresponds to a perfect rectangle or not.

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²). 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[pos-1] = -1
    then l := pos
    else l:= p[pos-1];
  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[lx-1][ry] != sumRow[lx-1][ly-1] &&
           sumRow[rx+1][ry] != sumRow[rx+1][ly-1] &&
           sumCol[ly-1][rx] != sumCol[ly-1][lx-1] &&
           sumCol[ry+1][rx] != sumCol[ry+1][lx-1];
  }
  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][j-1] + (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][i-1] + (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[pp-1]==-1?pp:p[pp-1]);
          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;
  }
}