Wednesday, July 12, 2006 Match summary
In Division 1, competitiors discovered the Easy and Medium problems to be easier than expected. Several coders solved them both in about
1015 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.
The ProblemsEscapeFromRectangleUsed as: Division Two  Level One:
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. public int shortest(int x, int y, int w, int h) { return Math.min(x, Math.min(y, Math.min(w  x, h  y))); }MatchNumbersEasy Used as: Division Two  Level Two:
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. 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; }MatrixTransforming Used as: Division Two  Level Three: Used as: Division One  Level One:
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 topleft corner.
The only way to change its value is to flip the 3 x 3 consecutive submatrix,
located in the topleft 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. 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; }SumThemAll Used as: Division One  Level Two:
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. 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); }MatchNumbersHard Used as: Division One  Level Three:
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. 
