Member Count: 483,944 - May 22, 2013  [Get Time]
 Match Editorial
2006 TopCoder Collegiate Challenge
Online Round 2C

October 11, 2006

## Match summary

Now 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 Problems

ConstitutiveNumbers
Used as: Division One - Level One:
 Value 250 Submission Rate 114 / 133 (85.71%) Success Rate 107 / 114 (93.86%) High Score eleusive for 248.10 points (2 mins 29 secs) Average Score 201.86 (for 107 correct submissions)

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:
 Value 550 Submission Rate 90 / 133 (67.67%) Success Rate 66 / 90 (73.33%) High Score reid for 493.47 points (9 mins 50 secs) Average Score 367.86 (for 66 correct submissions)

Let's iterate through all possible sets of rows and columns to be painted. The total number of variants is not more than 218. 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.

DominoesFalling
Used as: Division One - Level Three:
 Value 1000 Submission Rate 15 / 133 (11.28%) Success Rate 7 / 15 (46.67%) High Score Ying for 839.39 points (12 mins 57 secs) Average Score 630.33 (for 7 correct submissions)

Let F(i) be equal to 0 if the i-th 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 i-th position. Let A(i, n) be the number of tiles to be moved to make such position with the domino effect, that the i-th place is occupied and there is exactly n - 1 dominoes to the left from the i-th 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 i-th 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.

By Andrew_Lazarev
TopCoder Member

 Home  |   About TopCoder  |   Press Room  |   Contact Us  |   Careers  |   Privacy  |   Terms Competitions  |   Cockpit Copyright TopCoder, Inc. 2001-