std::pair is good

The editorial for the Topcoder Open 2011 qualifcation round 1 is up, but there is something that I don't like about it. To avoid having to explain off-topic STL features, I didn't make the solution for 1000 as simple as it should have been. The culprit is this function:

// Compares two sequences, returns the better one using the tie-breaking
// describing in the statement. 
string better( const string& a, const string &b) {
    if (a == "...") {
        return b;
    } else if (b == "..." ) {
        return a;
    }
    if (a.length() < b.length()) {
        return a;
    }
    if (a.length() > b.length() ) {
        return b;
    }
    if (a < b) {
        return a;
    } else {
        return b;
    }
}

Innocent enough eh? But isn't it the most repetitive, boring code you will ever have to type? Everything with non-trivial tie breaking rules involves doing something like that. In this problem's case, you need to tie break between "..." , smaller strings and lexicographically-first ones.

For a long time I was skeptical of std::pair and I didn't use it. Neither did I get why the people in the top kept using it. Let us accept it, vector<pair< pair<int,int>, string > > looks almost like obfuscation - Why not use a struct containing named ints and a string?. I eventually learned what was so great about.

• 1. STL pairs can be created very easily with make_pair.


• 2. STL pairs implement the < and > operators, and they do it in a rather standard way - First compare the first element, and if the two first elements are equal, use the second for tie breaking. They also implement == and = in a logical way.


• As a case of great synergy, std::min works when comparing any type that supports = and <.
  

Where does this take us? Well, for starters it makes pairs very useful for these over-complicated tie breaking days. The following is a way to implement the better() function:

// Compares two sequences, returns the better one using the tie-breaking
// describing in the statement. 
string better( const string& a, const string &b) {
    if (a == "...") {
        return b;
    } else if (b == "..." ) {
        return a;
    }
    return std::min(make_pair(a.length(),a), make_pair(b.length(), b) ).second;
}

Explaining: make_pair(a.length(), a) . Will magically make a pair< string::size_t*, string > that has a.length() as first element and a as second element.

* string::size_t is a fancy way to say unsigned int. It causes a lot of issues that things like .length() is declared as unsigned int instead of just a simple int. So many that perhaps this was the main reason Java does not support unsigned.

std::min, will compare both pair< string::size_t, string >s, if the first elements are equal it will compare the second elements. Then it will return the one pair that is the smallest. In other words, if the lengths of the strings are different, it will return the pair with the smaller string, and if they are equal, it will return the pair with the lexicographically-first string. (Because std::string implements < that does lex-first check).


But there is more, what about dealing with "..." ? The main problem with doing that comparison is that "..." has three characters, when it should be the equivalent to the maximum possible result. So, how about we make "..." a pair that first contains a very high number and second "..." ? Then if we use pair<int,string>s to represent possible results, we would just need to return the second element of the best pair we found. Such as the following code:

const int MAX_SEQUENCE_LENGTH = 199;
const int MAX_SQUARE_SIZE = 149;

typedef pair<int,string> result;
const result IMPOSSIBLE = make_pair(2* MAX_SEQUENCE_LENGTH,string("..."));

struct SquareSeries
{   
    // We use these tables to memoize the results.
    bool visited[MAX_SEQUENCE_LENGTH+1][MAX_SQUARE_SIZE+1][26];
    result mem[MAX_SEQUENCE_LENGTH+1][MAX_SQUARE_SIZE+1][26];

    // constants   
    string pattern;
    int rightStart, lastLength;

    //----------    
    // Returns a sequence that:
    // * starts at position p of the pattern.
    // * If the square previous to the sequence had size prevsz and
    //   color prevc, the last square of the sequence
    //   will have size = lastLength
    //
    result rec(int p, int prevsz, char prevc) {
        //memoize the results:
        result & x = mem[p][prevsz][prevc-'A'];
        if ( visited[p][prevsz][prevc-'A'] ) {
            return x;
        }
        visited[p][prevsz][prevc - 'A'] = true;
        
        x = IMPOSSIBLE;
        
        if(p == pattern.size()) {
            //The end of the pattern. The last size
            // should match the one we want.
            x = (prevsz == lastLength )? make_pair(0,string("")) : IMPOSSIBLE;
            return x;
        }
        
        bool alloww = false, allowb = false;
        if (pattern[p] != '?') {
            //forced to use pattern[p] color
            alloww = (pattern[p]=='W');
            allowb = ! alloww;
        } else {  //?
            //we can skip to right side:
            x = rec(rightStart, prevsz, prevc);
            // Allow any of the colors
            alloww = allowb = true;
        }
        for (char ch = 'B'; ch<='W'; ch+='W'-'B') {
            // If not allowed to use a color, don't use it
            if ( ((ch=='B') && !allowb) || ((ch=='W') && !alloww) ) {
                continue;
            }
            // Change the size according to last color.
            int sz = prevsz + ( (ch!=prevc) ? 1: -1 );
            if ( sz == 0 || sz > MAX_SQUARE_SIZE ) {
                //Skip when size is invalid.
                continue;
            }
            // Continue the recursion for the next character positions
            result y = rec(p+1, sz, ch);
            x = std::min(x, make_pair(y.first + 1, ch + y.second) );
        }
        
        return x;
    }
    string completeIt(string pattern, int lastLength)
    {
        // Find the question mark.
        int q = 0;
        while ( pattern[q] != '?' ) {
            q ++;
        }
        //Split in left and right parts.
        string left = pattern.substr(0,q);
        string right = pattern.substr(q+1);
        
        //max size of added sequence:
        int qw = MAX_SEQUENCE_LENGTH - left.size() - right.size();

        //Position at which the right side starts
        rightStart = q + qw;

        //The new pattern with extra '?' for each possible
        //location of a new character.
        this->pattern = left + string(qw,'?') + right;
        
        this->lastLength = lastLength;
        
        //Fill visited with 0s.
        memset(visited,0,sizeof(visited));
        
        //Starting at position 0, the last square had size 0 and color 'Y'
        //the wanted last size is lastLength.
        return rec(0, 0,'Y').second;
    }

   
};

pitfalls
make_pair does the type checking automatically. But the problem is that implicit type casts between different std::pairs do not work correctly (or at all). For example:

string y = "hello" ; // This works fine, "hello" is a const char*
// but const char*s can get typecasted as std::strings thanks to constructors.

pair<int, string> p = make_pair(0, "fail"); // This does not work fine.
// make_pair(0, "fail") believes it has to make a pair<int, const char*>
// pair<int, const char*> does not get casted automatically as 
// pair<int, string>.

//Possible alternatives:
pair<int,string> q = make_pair<int, string>(0, "fail"); //explicitely use
                                                        //the correct make_pair

pair<int,string> r = make_pair(0, (string)"fail");
//cast the const char* to string before passing it to make_pair

pair<int,string> r = make_pair(0, string("fail") );
//a nicer looking way to cast it...

Read More

Bugs that come back to haunt you.

The funniest thing happened to me today while finalizing an editorial. I obviously used my handle tag script. But today, the old reliable script was crashing. At the end I found the source of the problem:

RATING_CLASSES = [ (-1,-1,'coderTextOrange'), (0,0,'coderTextBlack'), (1,899,'coderTextGray'), (900,1199,'coderTextGreen'), (1200,1499,'coderTextBlue'), (1500,2100,'coderTextYellow'), (2200,1e100,'coderTextRed') ] 

See the problem? What happens when a yellow coder has a rating between 2101 and 2199 ? ...

Then another issue appeared, one of the coders was not being recognized. I tried the profile search at topcoder and it turns out _ is actually a wild card in that search feature. So, _sunny will not return _sunny member profile, it will list a page of all the profiles that are 6 characters long and end with sunny. The workaround was simple, I just guessed that If I add a escape \ to the _ , it will no longer be considered a wildcard. So, searching for \_sunny leads directly to _sunny's profile. That is nice.

The point of this post is, I had to update the script in case anyone actually used it.

Read More

Some thoughts after SRM 506.

It was good match for me. This is officially the first time I am actually able to solve a max flow problem during the match. I also gained 72 points and am back to 1900-2000 range in topcoder. However, I made many blunders and was victim of past hindsight.

Note 1: Know your STL.
You can find the following in my code for div1 600:

// If you know a better way to append a 0 to the beginning of
// this, I am listening...
reverse(districts.begin(), districts.end());
districts.push_back(0);
reverse(districts.begin(), districts.end());

I knew I had to insert a 0 to the beginning of the vector<int> but I could not think of a quick STL way to do it. I was later able to find it, the (actually intuitive for a STL feature):

districts.insert(districts.begin(), 0);

It is a little strange it needs an iterator when it is a non-static method. As always with the STL you will type the same thing more times than needed.

Note 2: Don't code, think!
At one point of the code, you need to get the time to move from a district i to j using no cars and also to calculate the time using each of the available cars. Coding this is actually where I spent most of the 58 minutes I used to solve this problem. The reason is that I, for some reason decided to use a Bellman-Ford (instead of Dijkstra) that starts at district i, may decide to pick the car (if it exists) and then goes to district j. In total it is
a complicated minimum path problem in which the state has two dimensions for its vertices (district, are we inside car?) and thus the transitions are also complicated to code. After using the car, the cost uses the inverse drive velocity instead of the walk velocity.

The one blunder here was to rush into coding that Bellman-Ford. It was better to just stop for a second, and note that you can multiply inverseWalkSpeed or inverseDriveSpeed after the minimum distance is calculated instead of during. What this means is that if you
just had precoded a dist[x][y] matrix that yielded the minimum distance between districts x and y. Then the minimum time without using a car is:
dist[x][y]*inverseWalkSpeed and the time using a certain car z that is in district c is simply: (dist[x][c]*inverseWalkSpeed + dist[c][y]*inverseDriveSpeed). This helps because the dist array is very easy to generate by using Floyd-Warshall on the original road cost matrix (the one in the input).

A similar issue is with the max flow part. In my original analysis, I first calculate the total cost without using cars, and then I make a max-benefit matching to maximize the reductions in cost (for each pair (transition, car) calculate the reduction in cost between not using any car and that option). Max benefit is the same as min cost when the cost is negative, and although it is possible to do that in min cost max flow, the implementation is harder (you need Bellman-Ford instead of Dijkstra for the first iteration, then stick to slow Bellman-Ford or do a trick with "potentials" to use Dijkstra. The min-cost-max-flow algorithm can be done much simpler without negative costs.

Instead of diving into negative costs that quickly, I could have tried to get rid of the negative part. Which is perfectly possible. Just include the cost to use no car and the costs to use each car in the network. Not using any car should have infinite capacity, alternatively, just connect each transition directly to the sink with capacity 1 and cost = cost of normal travel. Either way, what follows is what my code could have been if I stopped to improve the analysis of the problem instead of just starting to type quickly:

int travel(vector <int> cars, vector <int> districts, vector <string> roads,
           int inverseWalkSpeed, int inverseDriveSpeed)
{
    t = roads.size();
    iws = inverseWalkSpeed;
    ids = inverseDriveSpeed;
    this->roads = roads;
    
    districts.insert(districts.begin(),0);

    int n = districts.size()-1;
    int m = cars.size();
    
    // Floyd-Marshall to get the minimum distances.
    int dist[t][t];
    for (int i=0; i<t; i++) {
        for (int j=0; j<t; j++) {
            dist[i][j] = roadCost(i,j);
        }
    }
    for (int k=t; k--;) {
        for (int i=t; i--;) {
            for (int j=t; j--;) {
                dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j] );
            }
        }
    }
    
    network * G = new network;
    for (int i=0; i<n+m; i++) {
        G->addVertex();
    }
    G->sink = G->addVertex();
    G->source = G->addVertex();
    for (int i=0; i<n; i++) {
        int u = districts[i], v = districts[i+1];
        G->addEdge(G->source, i, 1, 0);
        for (int j=0; j<m; j++) {
            //Time to travel from u to v using car j:
            int costUsingCar = dist[u][cars[j]]*iws + dist[cars[j]][v]*ids; 
            G->addEdge(i, j+n, 1, costUsingCar );
        }
        //Time to travel from u to v not using any car:
        G->addEdge(i, G->sink, 1, dist[u][v]*iws );
    }
    for (int j=0; j<m; j++) {
        G->addEdge(j+n, G->sink, 1, 0);
    }
    
    int flow; long long cost;
    G->minCostMaxFlow(flow, cost);
    delete G;
    
    assert(flow == n);
    
    return (int)(cost);
}

It is a lot more concise than what I submitted during the match.

Mantain your own code library.
I had to use min-cost max flow to solve this problem. It is a particularly complicated algorithm and for that reason I use a library code. Unfortunately, It seems had not updated nor used that code in years. It seems that the last few years I have only used min-cost-max-flow in editorials and problems of my own, and that means Java. I could not have used my Java implementation either because I needed negative costs (thanks poor analysis!). So, I used the c++ code I've written before.

The horror. It seems that back when I wrote that code, I was a lot less concise, and also liked code hacks like avoiding the use of {} brackets when not necessary (That is silly, they are ALWAYS necessary, else it will take you more time to update the code after you want to add lines to your if-then-else that only used one line... =) . Worse, it was particularly abusive of the >? <? g++ extensions (Very useful min and max operators, that were removed from more modern versions of g++). So I could not compile the code locally. After thinking that I should not waste time redoing such code, and remember that the VERY OLD g++ version in Topcoder's server does support those g++ extensions. I decided to switch to manual compilation and tests using the compile and test button from the arena. But that turned out to be very slow, specially because I had to correct some syntax errors when building the network.

Focus, please focus
I finally implemented the min-cost max flow. And the sweetest thing happened. All results were wrong. I was getting 44 instead of 36. I knew that the normal cost without using any car is 40, so the min cost flow should have returned -4. So, what happened? I came to conclude that, unlike what I remembered about my precoded min cost flow solution, it did not support negative numbers. Panic. So, what was I supposed to do. I needed negative costs (I thought I did, but it turns out it was not true) and I had no min cost flow implementation that solves it.

Then I remembered that I had a Hungarian algorithm code lying around, since I was doing min-cost Bipartite matching, that was actually a useful thing. The problem is that my Hungarian algorithm code was much older and I did not remember how to use it... I was in the process of analyzing it, when I noticed something funny...

When I was coding the thing that uses min-cost max flow. I was multiply the costs by -1, because that is what you do. But then, the returned cost would be -BENEFIT. But I was doing MaxBonus = result of cost flow. And finally (total - result). Do you see it? I was multiplying by -1 twice.

I tried, I really tried to restore the solution to when the min-cost-max-flow algorithm was implemented. But Kawigi Edit's undo limit turned out to be smaller than I needed. I had to reimplement min-cost-max-flow, again, and also using manual compilation and examples because local tester did not work, again.

Mantain your code library, really
It also does not hurt if you left some documentation comments regarding how to actually use your code. Just because you wrote it, it does not mean you won't forget how to use it after 5 years. You should also practice more and make sure to keep your library code clean and to practice using it. After changing your local compiler's version, make sure your personal library of code for contest actually compiles with it.

It does not hurt to try to simplify and minimize the size of your pre-made code. Because when you actually get to use it, and it makes your code look like a Behemoth, it is very embarassing.


Rule #1, again
Smaller issue, I had a failed challenge, which as you may remember from very old blog posts, breaks my topcoder rule #1. Do not challenge. (Rule #2 is DO NOT challenge). The solution I challenged was correct, for some reason It seemed wrong to me. I even tried it mentally and thought that the case I provided would make it case, that was not true. This was a unnecessary risk, if I failed any of my solutions to the problems, I would have gotten a very bad score because of this failed challenge.

Read More

Google code jam qualification round

This one had two surprises for me: Usually in the qualification round there are three problems and the score rules are such that you have to pass at least one large input to pass. In this case, the qualification cut-off was 25, yet each of the small inputs was worth 10 points. So I knew I qualified much earlier. The second surprise was that there were a couple of non-trivial problems. They are still 'easy' problems but they may be very tricky to think of the solution.

I actually started the match at the whole beginning. I did have to use around 30 minutes in the middle of solving D-large to go to have dinner. That was only because I didn't plan to take so long. Anyway, I ended up in position 93-th. Which is unimpressive seeing how I could notice some people with a better ranking that clearly started solving the problem set after me...

A and B
I am not going to explain problems A and B because... well, they are mostly implementation. A is interesting in that you really need to think about the implementation before dividing, and is tricky, but B is more straightforward. I am not sure I understand why A large gives less points than B large. I really think that B was the easier of the two.

Still, here are some commented versions of my solutions to A and B:

A:

// They contain the input after reading from I/O
int N;
char bot[100];
int  button[100];

// Returns the needed time for a test case:
int solve() {
    int ox = 1, ot = 0; //The last position and the last time we remember
                        //about the orange bot
    int bx = 1, bt = 0; // Same about the blue bot.
    int t = 0;
    for (int i=0; i<N; i++) {
        if (bot[i] == 'O' ) {
            //Orange
            ot += abs(button[i] - ox)+1; //Time required to move to the button
                                         //and push it.
            ox = button[i];         //update position
            ot = std::max(ot, t+1); //wait to time t before pushing if necessary
                                    //(so that the push is done after
                                    // the previous one)
            t = ot;
        } else {
            //Blue
            bt += abs(button[i] - bx)+1;
            bx = button[i];
            bt = std::max(bt, t+1);
            t = bt;
        }
    }
    return t;
}

B:

// The variables that hold the input after reading the input file...
int C;
char base1[36];
char base2[36];
char result[36];
int D;
char opos1[28];
char opos2[28];
int N;
string spells;

// Uses the variables and returns the contents:
// Another function converts "AA" to [A, A] after this one is called...
string solve() {
    string contents = "";
    char transition[26][26];
    memset(transition, '#', sizeof(transition));
    bool opposed[26][26];
    memset(opposed, 0, sizeof(opposed));
    
    // Load the input into a table of transitions.
    for (int i=0; i<C; i++) {
        int a = base1[i]-'A';
        int b = base2[i]-'A';
        transition[a][b] = transition[b][a] = result[i];
    }
    // And a table of opposed characters
    for (int i=0; i<D; i++) {
        int a = opos1[i]-'A';
        int b = opos2[i]-'A';
        opposed[a][b] = opposed[b][a] = true;
    }
    for(int i = 0; i<spells.size(); i++) {
        // Simulate the addition of each element
        if (contents == "" ) {
            contents += spells[i];
        } else {
            //transition?
            char cur = spells[i];
            int x = cur-'A';
            char ls =  *contents.rbegin();
            char & r = transition[ls-'A'][x];
            if ( r != '#' ) {
                //Yes, transition, do the transformation!
                contents.resize( contents.size()-1);
                contents += r;
            } else {
                //opposed?
                bool op = false;
                for_each(ch, contents) {
                    op |= opposed[*ch-'A'][x];
                }
                if (op) {
                    //Yep, opposed = clear it.
                    contents = "";
                } else {
                    //not opposed just append new element.
                    contents += cur;
                }
            }
        }
    }
    return contents;
}

C (small)
This was funny, I was just about to read C's statement and SkidanovAlexander already got his 100 points. Then I read the statement, and I was surprised, it was actually a interesting problem. (Already? In the qualification round?). Anyway, the first thing I noticed is that adding two binary numbers without carriage is the same as a xor operation. I didn't note this as much as remembering it because it is a common theme in some problems. After that it got harder. Usually these problems are solved using dynamic programming. But since the little kid uses xor instead of +, there was not (I thought) an easy way to represent the current "Difference" which you would have to equal to 0... After a while, I decided that since only 25 points were needed, I may as well solve the easy version of C first and ensure myself the qualification...

The easy version of problem C is simple: The maximum number of candy pieces is 15, which means that you can try all 215 ways to split the candy in two parts, get the xor of each of them and then remember the one that gave Patrick the best outcome.

After that, I decided to take a look to D.

D
Now that was shocking, I thought to myself that they were really set to make the match interesting for those that would find the previous problems easy. This problem at first seemed impossible.

I tried a (wrong) approach. I thought that it was always optimal to pick pairs of elements to shuffle. And wait until they are sorted - To sort pair by pair. So, in fact, if you could find the minimum number of swaps and multiply by 2 that would be the result. This approach turned out to fail the small input. I decided to switch to C-large.

C (large)
Leaving that problem for a while was useful because I was able to see with a fresher head when opening it again:

Actually: We want two partitions of the original candy bag. The xor of the first partition must be equal to the xor of the second partition. We have something like:

Xor of Side A = Xor of Side B

The equal operator (x==y) can be seen as : (x^y)==0 . (Where ^ is the binary xor operation). Try it yourself. xor is 0 whenever both bits are equal.

So we have:

( (Xor of Side A) ^ (Xor of Side B) ) == 0

( (a1 ^ a2 ^ a3 ^ ...) ^ (b1 ^ b2 ^ b3 ^ ...) ) == 0

Now xor is associative and distributive. And the sets {a1,a2,...} {b1,b2,...} are both partitions of the original set (When uniting {a1,a2...} with {b1,b2,...} we get the original set, and they are disjoint). Which leads us to concluding:

C1 ^ C2 ^ C3 ^ ... C4 == 0

Yes, that's right, the xor of all the values in the bag must be 0 and it does not matter which candy goes to the little brother and which to the big brother. I was at first skeptical, then I noticed that in the second example, every partition will yield two equal Patrick values... 3^5 = 6. 5^6=3, 3^6 =5, 3^5^6 = 0. This means that as long as the xor of all the values in the bag is 0, every partition is valid. And if the xor is not 0, no partition is valid.

If the xor is 0, then we can just pick any partition. We want one that gives the big brother the best value, and the subset given to the little brother must be non-empty. There is no need to pick more than one element for the little brother, and it is convenient to keep the element we give to him as small as possible. - Just pick the minimum and give it to him. Give the rest to the big brother and this will maximize his loot.

// Contain the input after read from i/o:
int N;
int C[1000];

// Returns the maximum loot size or -1 if it is impossible
int solve() {
    int x= 0; //xor of all elements
    for (int i=0; i<N; i++) {
        x ^= C[i];
    }
    if ( x == 0) {
        // Every partition is always valid
        // Sum of all minus the smallest value:
        return accumulate(C,C+N,0) - *min_element(C,C+N);
    } else {
        // No partition is valid
        return -1;
    }
}

Funny anecdote: When I coded a solution very much like that code, I could not compile the accumulate. I wasn't sure what was going on, I re-wrote the pronunciation of accumulate a lot of times and I double checked the #includes in my template - <algorithm> was there all right. I ended up giving up and doing the sum manually. Later when my head was colder I noticed that my template c++ file did not #include <numeric>, and numeric and not algorithm is the #include file that has std::accumulate. (Which is not very intuitive, considering that accumulate is purely algorithmic and it works with strings and any class that overloads +, not just numbers).

Back to D
I went to dinner, and when I came back I started trying many different cases. I eventually learned something about the result. that something turned out to be true. I won't explain what because I don't want to spoil the problem for no reason and I right now cannot explain why it worked, so it would be unnecessary as an explanation.

I didn't really like this problem, rewarding not doing a proof is the opposite thing to what you want in a programming contest. At first I thought that maybe I was the only one that didn't bother proving it but after the match it was clear that most people just guessed the solution. Problems should punish those that don't prove stuff before implementing, not the other way around.

Read More