Match Editorial

In Division 1, competitiors discovered the Easy and Medium problems to be easier than expected. Several coders solved them both in about 10-15 minutes. On the contrary, the Hard problem clearly justified its 1000 points. Only 23 of 64 submits were successful. Two Moscow guys, Egor (who placed second) and Petr (who came in third), were overtaken by misof like the Russian football team was bested by team Slovakia on the road to the FIFA World Cup 2006.

In Division 2, newcomer presley took 1904 rating points as a reward for a shining debut. Second and third went to xuecaijia and iRabbit, respectively.

The Problems

Value	250
Submission Rate	406 / 426 (95.31%)
Success Rate	393 / 406 (96.80%)
High Score	mahbub for 249.52 points (1 mins 15 secs)
Average Score	230.84 (for 393 correct submissions)

As we know from the school geometry, the shortest route between two points is a straight line. So, we need to try to go straight to each of the four rectangle's boundaries and choose the best.

Java code follows:

public int shortest(int x, int y, int w, int h) {
   return Math.min(x, Math.min(y, Math.min(w - x, h - y)));
}

Value	500
Submission Rate	168 / 426 (39.44%)
Success Rate	46 / 168 (27.38%)
High Score	nonethis for 397.94 points (15 mins 13 secs)
Average Score	260.91 (for 46 correct submissions)

In contrast to the Div1Hard, this problem could be solved using dynamic programming. So, I'll describe this approach here. Greedy approach is described in the Div1Hard section.

DP function returns the maximal number which can be created from n matches for the given n. It iterates over all digits that can be created using at most n matches, trying to lay out the next digit, remove the used matches and recursively calling itself to determine the maximal number that can be created using the rest of the matches. Then it chooses the best solution. To avoid troubles that can be caused by a zero digit, one may implement the named function in such a way that it creates the number from right to left, i.e. from the least significant digit to the most significant digit. Alternatively Java coders may use the BigInteger class.

brett1479's solution in Java follows:

public class MatchNumbersEasy {
   BigInteger[] cache = new BigInteger[500];
   BigInteger solve(int[] m, int n) {
   if (cache[n] != null) return cache[n];
   BigInteger best = BigInteger.ZERO, ten = BigInteger.valueOf(10);
   for (int a = 0; a < m.length; a++) if (m[a] <= n)
      best = best.max(ten.multiply(solve(m, n - m[a])).add(BigInteger.valueOf(a)));
   return cache[n] = best;
}

Value	1000
Submission Rate	56 / 426 (13.15%)
Success Rate	30 / 56 (53.57%)
High Score	N.M.Hieu for 927.90 points (8 mins 2 secs)
Average Score	709.35 (for 30 correct submissions)

Value	300
Submission Rate	260 / 337 (77.15%)
Success Rate	213 / 260 (81.92%)
High Score	tmyklebu for 298.12 points (2 mins 15 secs)
Average Score	254.73 (for 213 correct submissions)

Let's go through the cells of the matrix a in the row major order, i.e. from the top to the bottom and from the left to the right. First cell that we will meet is the cell in the top-left corner. The only way to change its value is to flip the 3 x 3 consecutive submatrix, located in the top-left corner (its center is located one cell to the right and one cell down from the named cell). So, if the corner cell's value is equal to the value of the corresponding cell of matrix b, we can't flip the named submatrix -- in the other case, we must flip it. Next cell that we will meet is managed by two flipable submatrices (if the given matrices have at least four columns, of course) one of which is already used (meaning that we have already decided wheter to flip it or not). So, we have only one variant again. Acting according to the described algorithm we will make the invariant consequence of flips. Once all necessary flips were made, we only need to check whether the resulting matrix is equal to the matrix b. Needless to say, flipping the same submatrix more than once is a not a good idea.

Java code follows:

static int[][] g;
static void push(int r, int c) {
   int i, j;
   for (i = r - 1; i < r + 2; i++) for (j = c - 1; j < c + 2; j++) g[i][j] ^= 1;
}
public int minPushes(String[] a, String[] b) {
   int ret, n, m, i, j;
   n = a.length;
   m = a[0].length();
   ret = 0;
   g = new int[n][m];
   for (i = 0; i < n; i++) for (j = 0; j < m; j++) g[i][j] = a[i].charAt(j) - '0'; 
   for (i = 0; i < n - 2; i++) for (j = 0; j < m - 2; j++)
      if (g[i][j] != b[i].charAt(j) - '0') {
         push(i + 1, j + 1);
         ret++;
      }
   for (i = 0; i < n; i++) for (j = 0; j < m; j++)
      if (g[i][j] != b[i].charAt(j) - '0') return -1;
   return ret;
}

Value	600
Submission Rate	209 / 337 (62.02%)
Success Rate	176 / 209 (84.21%)
High Score	misof for 586.29 points (4 mins 21 secs)
Average Score	374.31 (for 176 correct submissions)

This one can be solved using different methods. I'll describe the DP approach. Suppose we have a function long f(int x), which returns the sum of all the digits of all the numbers between 0 and x - 1, inclusive. Then the answer for the problem is f(upperBound + 1) - f(lowerBound). In order to implement the named funtion we need to fill the array long dp[10][11]. dp[i][j] contains the sum of all the digits of all the numbers, which have j significant digits and their first (most significant) digit is i. Let me describe how the function long f(int x) works. It goes through the number x from its most significant digit to its least sigificant digit. Suppose x = 527. First treatened digit is digit '5'. dp[3][4] must be added to the return value (which is intially equal to zero). Then we go to the digit '2'. Now we only consider the numbers from 500 to 526, inclusive (527 is not included according to the function's declaration). So we need to add to the return value the sum of all the digits from 0 to 26, inclusive, plus 5 (the first digit) multiplied by the amount of numbers between 0 and 26, inclusive. Interval [0, 27) is treatened in the same manner. We accumulate the previously treatened digits and add their sum (multiplied by the amount of numbers in the remaining interval) to the return.

Java code follows:

public class SumThemAll {
   
   static long dp[][] = new long[10][11];

   long f(int x) {
      String s;
      long ret, z;
      int i, j, k, y;

      // Variable z serves to store the amount of numbers,
      // which contains a particular number of digits.
      // Variable y serves to store the sum
      // of all currently treatened digits of x

      s = Integer.valueOf(x).toString();
      z = 1;
      for (j = 1; j < s.length(); j++) z *= 10;
      ret = 0;
      y = 0;
      for (j = 0; j < s.length(); j++) {
         k = s.charAt(j) - '0';
         for (i = 0; i < k; i++) ret += dp[i][s.length() - j] + y * z;
         y += k;     // Add just treatend digit to y
         z /= 10;
      }
      return ret;
   }
   
   public long getSum(int lowerBound, int upperBound) {
      long k;
      int i, j;
      for (i = 0; i < 10; i++) dp[i][0] = 0;
      k = 1;
      for (j = 1; j < 11; j++) {
         dp[0][j] = 0;
         for (i = 0; i < 10; i++) dp[0][j] += dp[i][j - 1];  
         // dp[0][j] contains the sum of all the numbers,
         // which have less than j digits
         // (like they can be precedeed with extra leading zero(s))
         for (i = 0; i < 10; i++) dp[i][j] = dp[0][j] + k * i;
         k *= 10;
      }
      return f(upperBound + 1) - f(lowerBound);
   }

Value	1000
Submission Rate	64 / 337 (18.99%)
Success Rate	23 / 64 (35.94%)
High Score	misof for 734.19 points (18 mins 33 secs)
Average Score	507.77 (for 23 correct submissions)

If Div2Medium can be solved using DP, this one requires a greedy approach. First of all, let's take care of two corner cases. First of them is the case when no digit can be created at all and the second is when the only digit that can be created is zero. After these cases have been properly treated, the general part begins to work.

First we need to find the digit, which requires the minimal amount of matches. In the case of a tie, choose the maximal digit. Imagine that we created as much such digits as possible. Let num = this digit, len = n / num and rem = n % num. So, we have this digit into num, amount of such digits, that can be created into len and the amount of the remaining matches into rem. Now we possibly have to treat the corner case num = 0. In this case it can be necessary to remove several zeros to create some non-zero digit.

This subproblem can be solved in the following way: find the minimal amount of matches necessary to create any non-zero digit, calculate how many zeros should be removed in order to create the "cheapest" non-zero digit, then find the maximal digit that can be created using the amount of matches that we will have after this removal and lie out this digit as the most significant digit of the resulting number.

After treating this zero-case, the main algorithm begins to work. Going through the resulting number from left to right, it tries to change the next digit to the most allowed digit, i.e. the digit that can be created using the current rem plus the amount of matches needed to create the digit which it currently treats. If at some step we can't "upgrade" the digit or len becomes equal to zero, it points that the job is done.