TopCoder SRM 566: The road to blue

If you recall, I am going with a "suicidal" strategy, to never open the division 1 easy before there are less than 10 minutes left for the end of coding phase. The results so far are not very surprising. I have the feeling that 250s are lately becoming longer. This is my second 0.00 in a row.

Div1 1000: The one with penguins, a circle and colors

Skipped this one quickly after reading the statement. Seems to be the typical div1 hard that I won't solve until after a couple of hours and with admin help. This one will stop me from finishing the editorial quickly...

Div1 500: The one with a mountain and cities

You have numCities total cities all in the border of a circle. You start at city 0. You make numSteps steps in total. In step 1, you move 1 city clockwise or counterclockwise. In step 2, two cities clockwise or counterclockwise. ... In step k , k cities clockwise or counterclockwise... Count the number of different sequences of numSteps steps such that you end back in city 0 modulo 1000000007.

At first I thought I was gonna to solve this problem. It seemed like a standard matrix multiplication one. Then I noticed that there can be at most 350 cities. That changes things... Let us explain the matrix approach though.

When the step number k is too big, the clockwise or counterclockwise distance between your current city and the new one is (k % numCities). This means that every numCities steps, we basically repeat the same thing. Over and over again.

Let us describe a transition matrix for step 1: For each i, there is one way to move from vertex i to vertex (i+1)%numCities and one way to move from vertex i to vertex (i-1+numCities)%numCities. This works for step k: One way to move from vertex i to (i+k)%numCities and one way to move from i to (i-k+numCities)%numCities. Note that if the two vertices are the same, there is only one way in total (Two paths are different not because of the direction you move but because of the city you move to).

If we multiply together the first numCities matrices. You will get a matrix that represents numCities moves. You can raise this one to the x-th power. Let x be numSteps / numCities. Then you can multiply the result to the product of the first numSteps % numCities matrices. Then this will be the total transition matrix.

The problem is that there are numCities matrix multiplications we have to use. This yields a O(n^4) algorithm and it is too slow for n=350. In fact, n seems to be crafted with this in mind.

The solution is that if you take a look to the matrices, you will see that each element inside the matrix is at most 1, and each row contains at most 2 ones. If you tweak the matrix formula a bit, you can actually do each multiplication in O(n^2) instead of O(n^3). This is very nice and clever...

When I finished coding that optimization I began to have issues. Apparently, my classic matrix exponentiation library might have some seg fault bug that happens when the matrixes are larger than usual. Then I had the other issue that it was timing out, apparently the number of steps is so large that even O( log(numSteps) * numCities ^ 3) is too much.

I thought of the solution for the time out issue when it was too late to code it. It turns out that the product of the numCities matrixes tends to generate very dull matrixes. Containing the same numbers repeated over and over again in the matrix and following some pattern. There is also symmetry in the matrix, so the same row is repeated over and over again, just slided a bit in each new row... I think that you can turn the matrix idea into a vector idea and turn the whole thing O(n^2).

Div1 250: The one with points and crossing

With less than 10 minutes left I open this problem and it turns out to be a bit tough to read. (long).

Ok, so you have at most 50 points. And some segment definitions that connect pairs of the points. You do not know the actual positions of the points. You can remove 0 or more segments. Count the total number of subsets of segments such that it is GUARANTEED that no two segments will ever cross, regardless of the position of the points.

After thinking for a while and looking at the statement images you can make some conclusions:

• Empty set (no segments at all) is always possible and valid.
• Whenever there is more than one connected component of segments, it is possible they would cross (take two separated segments and make them cross).
• When there is only one segment. It is valid.
• Star patterns are valid. A point that acts as a center and is connected to other points by a segment each.

We can count the pattenrs (single segment, star) that can be made using only the input segments. It is easy to count the segments. The stars are a bit harder: Pick a center point, then count the number of points that are initially connected with that center, each combination (use the binomial) of 2 or more points connected to it can make a star pattern.

I coded that stuff and had a bit of debug issues (again). Some seg faults and stuff that I could only fix after the end of the coding phase. That is when I noticed that the logic was failing the last test case...

It turns out that I forgot of yet another valid pattern: A single polygon of exactly three connected points (A triangle, a cycle of 3, etc). It is impossible to cross this pattern too. So you also pick the number of triples in whcih each pair is connected. This fixes the issue, you pass system tests and all is good

long long countDesigns(int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2) 
{ 
    int n = numCheckpoints; 
 
    // make an adjacency matrix. The original input format is a bit hazardous: 
    bool con[n][n] ; 
    memset(con, 0, sizeof(con)); 
    for (int i=0; i<checkpoint1.size(); i++) {  
        con[ checkpoint1[i] -1][ checkpoint2[i] -1] = true; 
        con[ checkpoint2[i] -1][ checkpoint1[i] -1] = true; 
    } 
    // Pascal triangle to generate the binomials we will need: 
    long long C[50][50]; 
    memset(C, 0, sizeof(C)); 
    for (int i=0; i<50; i++) { 
        C[i][0] = 1; 
        for (int j=1; j<=i; j++) { 
            C[i][j] = C[i-1][j] + C[i-1][j-1]; 
        } 
    } 
 
    long long res = 1 + checkpoint1.size(); // the empty set + the number of segments 
                                            // all are valid 
                                             
    // Count stars with center i: 
    for (int i=0; i<n; i++) { 
        int x = 0; 
        for (int j= 0; j < n ; j++) { 
            if (con[i][j]) { 
                x++; 
            } 
        } 
        for (int y = 2; y <= x; y++) { 
            res += C[x][y]; 
        } 
    } 
    // Count triangles: 
    for (int i=0; i<n; i++) { 
        for (int j=i+1; j<n; j++) { 
            for (int k=j+1; k<n; k++) { 
                if (con[i][j] && con[j][k] && con[i][k]) { 
                    res++; 
                } 
            } 
        } 
    } 
    return res; 
     
} 

Conclusion

The problems were good and interesting. My rating will suffer. Any comments?