Match Editorial

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

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)

C = a + (a + 1) + (a + 2) + ... + (a + k - 1) 
= a + a + ... + a + 0 + 1 + 2 + ... + (k - 1) 
= k * a + k * (k - 1) / 2.

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;
    }

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 2¹⁸. 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.

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)), 

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.