Today's TopCoder Test SRM

So I wanted to take this SRM seriously as it would be good practice. It didn't help that I remembered to have solved two of these problems before. But there we go.

I wanted really hard to try the new c++ features, but there wasn't that much of a chance to do it, I still managed to pull some tricks.

RPSTournament

Problem statement

I didn't remember this problem. I likely didn't see it before. This old problem had a very confusing problem statement (So a competitor defeats people with both larger and smaller seeds within range? But then what decides which of the two competitors wins? I gave up.

WebsiteRank

Problem statement

I remembered solving this problem before, but I of course don't have such a precise memory to remember the solution. I did remember that after SRM 357, there were tons of discussion about how trivial Floyd-Warshall passed (There can be around 800 website names.)

I actually had difficulty with the problem because I initially read the statement wrongly. The statement actually tells you to ignore points from pages that link to a site, if the site directly or indirectly links to them. I initially understood it as making the website ignore only the points "that come from it".

Once you read the problem correctly. You should be able to use Floyd-Warshall to quickly find which sites link directly or indirectly to each website. Once you ignore links between sites that do this - You are basically removing cycles from the graph. The graph becomes a directed acyclic graph. You could top-sort it, but it is not needed to. The total number of points each website receives is equal to the total number of paths that finish in the website (which is easy to calculate, even with a Floyd variation, because the graph is acyclic).

If the 800 website names bother you, just notice that there are only at most 51 relevant website names. (Websites that are the query's website or websites that are linked by other websites), so you can ignore the other websites and just consider them as extra initial points for each website. So in addition to counting the number of paths, you multiply the number of paths between each website i to the query website by the number of initial points of i.

// Using long (instead of long long) without a define!
long countVotes(vector <string> votes, string website)
{
    //maximum number of website names is around 50/3 * 50 ~=  833
    int n = votes.size(), t = 0;
    map<string,int> websiteId;
    vector<vector<string>> data;
    
    // Convert the votes array of strings to a data[][] 2d array of a
    // vector of strings. Note the auto keyword:
    for (auto q = votes.begin(); q!=votes.end(); q++) {
        istringstream st(*q);
        string x;
        // Look at this!:, pushing an empty vector:
        data.push_back( {} );
        auto & v =  *data.rbegin();
        while (st >> x) {
            v.push_back(x);
        }
        if (websiteId.count(v[0]) == 0) {
            websiteId[v[0]] = t++;
        }
    }
    if (websiteId.count(website) == 0) {
        websiteId[website] = t++;
    }
    vector<long> initialVotes(t, 1);

    int adj[t][t];   //Adjacency matrix
    int reach[t][t]; //Direct or indirect adjacency matrix (After Floyd-Warshall)
    long ways[t][t]; //Number of paths between each pair of nodes)
    memset(adj, 0, sizeof(adj));
    memset(reach, 0, sizeof(reach));
    memset(ways, 0, sizeof(ways));
    // First, setup the adjacency matrix: 
    for (int i=0; i<n; i++) {
        for (int j=1; j<data[i].size(); j++) {
            if (websiteId.count( data[i][j] ) == 0) {
                initialVotes[i]++;
            } else {
                int u = websiteId[ data[i][j] ], v = websiteId[ data[i][0] ];
                reach[u][v] = 1;
                adj[u][v] = 1;
            }
        }
    }
    // Find what nodes can be reached indirectly:
    for (int k=0; k<t; k++) {
        for (int i=0; i<t; i++) {        
            for (int j=0; j<t; j++) {        
                reach[i][j] |= (reach[i][k] & reach[k][j]);
            }
        }
    }
    // Now count the number of paths between each pair of nodes:
    for (int i=0; i<t; i++) {        
        for (int j=0; j<t; j++) {
            if (adj[i][j] && ! reach[j][i]) {
                ways[i][j] = 1;
            }
        }
    }

    for (int k=0; k<t; k++) {
        for (int i=0; i<t; i++) {        
            for (int j=0; j<t; j++) {
                ways[i][j] += ways[i][k]*ways[k][j];
            }
        }
    }

    // Done and multiply:
    long c = initialVotes[ websiteId[website] ];
    for (int i=0; i<t; i++) {
        c += initialVotes[i] * ways[i][websiteId[website]];
    }
    return c;
}

It seems I took longer to solve this problem than back in 2007, but this time I got the problem correct. I failed system tests in 2007.

PalindromeMaker

Link to statement

I still used my new strategy of waiting till there are less than 10 minutes before the end of the match before opening the easy problem.

This problem gives you a string of upper case letters. Return a palindrome permutation of those letters. If there are multiple solutions, return the lexicographically first one. If there are no solutions, return "".

Forget about the lexicographical condition. If we were to take any string like AABB and turn it into a palindrome, we would usually need each letter to appear an even number of times, so you can do ABBA or BAAB. There is one exception, when the length of the string is odd, then exactly one of the letters must appear an odd number of times. This letter should be used in the middle position.

Let us now deal with the lexicographically-first decision. Try each of the pairs of repeated letters. It is always better to place the lexicographically-smallest letter of those available in the smallest available position. So, for each letter from A to Z, in that order, pick every two of that letter, and push one to the left end and another to the right end. Remember the letters that appear an odd number of times. Then we can put the left, right (and maybe middle) ends together.

string make(string baseString)
{
    string left, right, odd;
    for (char ch='A'; ch <= 'Z'; ch++) {
        // Count the number of times letter ch appears:
        int c = count(baseString.begin(), baseString.end(), ch );
        // If it is odd, save it as the odd letter:
        if ( c % 2 == 1) {
            // Don't allow more than one odd letter:
            if (odd != "") {
                return "";
            }
            odd = ch;
        }
        // Half goes to the left end, other half to the right end.
        string rep = string( c / 2, ch );
        left += rep; right = rep + right;
    }
    // An odd letter must exist if and only if the string has odd length:
    if ( (baseString.size() % 2 == 1) == (odd != "") ) {
        return left + odd + right;
    } else { 
        return "";
    }
}

The end

It was an ok match, old problems feel very easy in comparison to current contests. Six years! That is depressing...