SRM551: slowness

Nothing like a TopCoder SRM with an ultra easy problem set to make you feel like a turtle. I solved both problems yet I am in position 230-th. (Starting to write this 5 minutes before the coding phase ends).

Div1 450 : The one with the wolves

Anyway, a wolf changes colors at night, when the wolf has a certain color, there is a list of available colors for it to change to. The wolf always picks the smallest color available. You are allowed to remove some of the possibilities to change from a color to another. What is the minimum number of removals you need so that a wolf starting at color 0 eventually reaches color N-1? (Does not have to stay in that color).

For some incredibly stupid reason, my old reflexes came back and I started with the medium problem. I really did not intend this to happen. This problem was so easy that I think I should have first warmed up on the division I 250 to be able to solve this one faster.

As my brain was just starting to function I was first lost on the idea that it was a maximum flow problem. Because in a way it asks you to cut roads. To the point that even when I thought of the cost function to make you go from a color to another, I decided to use min cost max flow instead of the obvious Dijkstra / or Floyd-Warshall. I would only discover my mistake after I made the code for the flow network...

Anyway, the wolf will always pick the smallest color available. It is always possible to force the wolf to pick any of the colors that are possible, you just need to remove the availability of the smaller colors. In order to force wolf color i to always turn into wolf color j, just remove all the available changes to colors of smaller value. This is the cost to move from color i to color j. You end up with a list of costs to move from each color to another. What is the cost to reach N-1 starting at 0? This is just a min-cost path problem. The paths are weighted. I just used Floyd-Warshall.

int getmin(vector <string> colormap) 
{ 
    int n = colormap.size(); 
    int cost[n][n]; 
    const int INF = 1<<20; 
    // Find the cost matrix 
    for (int i=0; i<n; i++) { 
        for (int j=0; j<n; j++) { 
           // infinite cost path means there is no path between the two colors 
            cost[i][j] = INF; 
            if (colormap[i][j] == 'Y') { 
                cost[i][j] = 0; 
                for (int k=0; k < j; k++) { 
                    cost[i][j] += (colormap[i][k] == 'Y'); 
                } 
            } 
        } 
    } 
    // Floyd-Warshall finds all minimum total costs, and is very simple to code: 
    for (int k=0; k<n; k++) { 
        for (int i=0; i<n; i++) { 
            for (int j=0; j<n; j++) { 
                cost[i][j] = std::min( cost[i][j], cost[i][k] + cost[k][j] ); 
            } 
        } 
    } 
    return ( (cost[0][n-1] == INF) ? -1 : cost[0][n-1]); 
} 

Div1 250 : The one with the string of colors

You are given a string, like "AABACAA", what is the maximum number of adjacent characters in a string you get by modifying the original one using at most maxSwaps swaps of adjacent characters?

A O(n⁵) algorithm: For each value of the number of adjacent characters. Try each possible starting index of the adjacent characters. For each of them, try the character of those. For each of them, find the minimum cost to have it that way.

The minimum cost can be found in O(n²), just find the starting point of the wanted letters used in the original string. Then you find the positions of the (spread) letters in the original string that have to be moved to the adjacent area.

It is much easier to do than explain.

Let us say that the X mark original positions of the characters we are interested in:

X.X....X.X

Somehow we want the final string to be "...XXXX...". What is the minimum cost? The first X in the string has to be the first X in the wanted area. That involves a distance and a cost. The second X has to be the second X and so and so. This is simple. The complication is when there are far more Xs than wanted:

X.X.X....X.X.X

If we still want ....XXXX..... , then we have to pick which of the original X is the first one.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) 
int maximumSpread(string chocolates, int maxSwaps) 
{ 
    //set some stuff up: 
    vector<char> colors; //available colors 
    {  
        set<char> chset(chocolates.begin(), chocolates.end()); 
        for_each(ch, chset) { 
            colors.push_back(*ch); 
        } 
    } 
    //  
    vector<int> cnt(256, 0); //number of times each color appears. 
    for_each(ch, chocolates) { 
        cnt[*ch] ++; 
    } 
    int n = chocolates.size(); 
     
    // For each possible spread: 
    for (int spread=n; spread > 1; spread--) { //O(n) 
 
        // for each starting index: 
        for (int start=0; start+spread <= n; start++) { //O(n*n) 
            // for each color :             
            for_each(ch, colors) {  //O(n*n*n) 
                if (cnt[*ch] >= spread ) { 
                    // for each starting index in the original string of that color: 
                    for (int o=0; o<n; o++) { //O(n*n*n*n) 
                        if ( chocolates[o] == *ch ) { 
                            int x = 0; 
                            int pos = o; 
                            int cost = 0; 
                            // find the costs to move each letter: 
                            while (pos < n && x < spread) {  //O(n*n*n*n*n) 
                                if ( chocolates[pos] == *ch ) { 
                                    cost += abs(start + x - pos); 
                                    x++; 
                                } 
                                pos++; 
                            } 
                            // the minimum cost is possible, return it 
                            if ( (cost <= maxSwaps) && (x == spread) ) { 
                                return spread; 
                            } 
                        } 
                    } 
                } 
            } 
        } 
    } 
    // 1 is always possible: 
    return 1; 
} 

This O(n⁵) solution can be easily improved to reduce the exponent, but that is not needed. For example, we can move the loop for o upwards and replace the color with it. In fact, this code is already O(n⁴) because there are O(n) valid pairs of (o, color).

The rest

I was severely dissappointed that everyone was solving both problems much faster. I don't like matches that are determined solely on speed. When the problems are this easy, speed tends to be almost indistinguishable from luck, imho.

I opened the 1000, but it seemed harder, and the targets who got plenty of time as solved the first two problems very fast did not solve it yet. So I instead tried to find possible mistakes in 250 and 450. But it seems that the example cases were very strong. Specially in 250. I thought that a common mistake would be to assume that the result adjacent area has to start at position that already includes the letter. This is not true, but it turns out the second example already catches that corner case.