Online Round 2C October 11, 2006 Match summaryNow we know all 150 coders who will fight for the final 48 spots in TCCC Round 3 on Saturday. A lot of red coders performed below their level today  and some of them got eliminated  but not daveagp. The finalist at the 2005 TCO won this round with a solid 1345 points, more than 75 points ahead of algostorm and krijgertje. The ProblemsConstitutiveNumbersUsed as: Division One  Level One:
This problem required only an ability to calculate the sum of arithmetic sequence. Consider a consitutive number C  by definition, it can be split into a sum of k positive numbers: C = a + (a + 1) + (a + 2) + ... + (a + k  1)Transforming this equation, we get the following: C = a + (a + 1) + (a + 2) + ... + (a + k  1) = a + a + ... + a + 0 + 1 + 2 + ... + (k  1) = k * a + k * (k  1) / 2.As you can see from this formula, the number C is a sum of k consequtive numbers if the difference (C  k * (k  1) / 2) is positive and is divisible by k. This gives us the idea for the solution. For each number C between A and B, and for each possible value of k (such that k * (k  1) / 2 is less than C) check if the number C can be split into the sum of k consequtive numbers. Implementation of the algorithm follows: public int count(int A, int B) { int ans = 0; for (int i = A; i <= B; i++) for (int k = 3; k * (k  1) / 2 < i; k++) if (((i  k * (k  1) / 2) % k) == 0) { ans ++; break; } return ans; }MatrixPainting Used as: Division One  Level Two:
Let's iterate through all possible sets of rows and columns to be painted. The total number of variants is not more than 2^{18}. We need to determine for a given set of rows and columns if it is possible to paint the corresponding rows and columns in some order. It is possible to do so by iterating several times through rows and columns from the set and painting all rows and columns in which the number of black cells is more than 4. The given set of rows and columns is called valid if it is possible to paint all the rows and columns from the set and there are no white cells in the matrix remains after that. Accordingly, from all the valid sets of rows and columns we need to choose the smallest one. DominoesFallingUsed as: Division One  Level Three:
Let F(i) be equal to 0 if the ith place is occupied by a tile in the initial arrangement and be equal to 1 in the opposite case. So, F(i) is the number of moves required to place the domino tile on the ith position. Let A(i, n) be the number of tiles to be moved to make such position with the domino effect, that the ith place is occupied and there is exactly n  1 dominoes to the left from the ith place. Clearly, A(i, 1) = F(i). A(i, n) can be calculated using following formula: A(i, n) = Min(A(i  k  1, n  1) + F(i)),where k is the number of empty cells immediately before the ith position, 1 ≤ k ≤ 4. We can start calculation of A(i, n) from the first element of the given cells because we can always put the tile on the right side instead of putting it to the left of the initial segment. 
