SRM 624: Slooooooooow

I just did the most amazing c++ code, got to share.

Div1 250: The one with buildings

You are given a list of integers (building heights). The maximum number of integers possible is 4000 and the maximum integer possible is 4000. For each `0 <= i <= n`, find the minimum number of steps so that the final sequence has `i` equal integers. Every step is to increment a single integer by 1 (building a new floor in a building).

I had some difficulties getting to the right approach. At first trying to do things like sweeps and dynamic programmings :/ . Turns out the trick is to solve: What is the minimum cost to have `y` buildings of height `x` ? For each `x`, calculate those costs for all `y`, updating the values in a total cost function that considers all possible heights.

The trick is that there are only `O(N)` relevant values of `x` (those equal to the heights), and that it is easy to find, for each `y` the minimum cost to have `y` buildings of height `x`. Just pick the `y` largest buildings of height greater than or equal to `x` and increment them. This gives us an `O(N^3)` algorithm, however, for each `y`, you can reuse the result of `y-1` (you know the cost of fixing `y-1` buildings, just add a single building and we know the result for `y`.

This is an `O(N^2)` algorithm:

int minimum(vector<int> heights)
{
    int n = heights.size();
    // sort non-increasingly by height:
    sort(heights.begin(), heights.end());
    const int INF = 4000 * 4000;
    // cost[i] will have the cost to have i equal buildings
    vector<int> cost(n + 1, INF);
    cost[1] = 0;
    // for each height:
    for (int i = 0; i < n; i++) {
        int c = 0;
        // for each number of buildings i - j + 1:
        for (int j = i - 1; j >= 0; j--) {
            // the minimum cost to have i - j + 1 buildings of this height 
            c += heights[i] - heights[j];
            // remember the best
            cost[i - j + 1] = std::min( cost[i - j + 1], c);
        }
    }
    
    
    // the problem actually asks for the XOR of all values, but I suspect
    // this is because of limitations in the return value size.
    int res = 0;
    for (int i = 2; i <= n; i++) {
        res ^= cost[i];
    }
     
    
    return res;
}

Div1 450: The one with implementation

Classical problem. You are given a graph (no loops, bidirectional, connected, weighted, some weights are zero). Return the total number of shortest paths between vertices `0` and `N-1` modulo 1000000007. Note that zero-weight edges might make the number of shortest paths infinite, return -1 in that case. At most 2000 vertices and at most 2000 edges.

Okay, the complicated path is when paths are infinite. This can only happen if there is at least one shortest path that visits an edge with weight 0. So we need a way to know, for each edge, if it can belong to a shortest path.

The way to check if an edge `(u,v)` can belong to an optimal path requires us to know: The weight of the edge, the minimum distance `D` between 0 and `N-1`, the minimum distance `d` between 0 and `u` and the minimum distance `r` between `N-1` and `v`. If `d + w + r = D`, then the edge can be used in a shortest path. If any 0-weight edge is one of those, return -1.

The rest is to count the number of paths. How about `f(x)` which returns the number of shortest paths towards `N-1` starting with `x`. `f(N-1) = 1`, there is only one shortest path there. For the other vertices `x`, you find every `y` such that `(x,y)` can belong to a shortest path. Then `f(x) = sum(f(y))` , easy, right? . Just evaluate the vertices in non-increasing order of distance to `N-1`, since none of the edges used will have weight 0, we can do this sorting.

I broke a record with this problem. I used 4 lambdas in total. And I even nested lambdas this time, which is so unusual in c++ :).

const int MOD = 1000000009;



int count(int N, vector<int> A, vector<int> B, vector<int> C)
{
    // make the graph easier to use:
    vector<vector<int>> g(N);
    vector<vector<int>> w(N);
    vector<int> degree(N);
    for (int i = 0; i < A.size(); i++) {
        degree[--A[i]]++;
        degree[--B[i]]++;
    }
    for (int i = 0; i < N; i++) {
        g[i].resize(degree[i]);
        w[i].resize(degree[i]);
        degree[i] = 0;
    }
    auto addEdge = [&](int u, int v, int weight) {
        g[u][degree[u]] = v;
        w[u][degree[u]++] = weight;
    };
    for (int i = 0; i < A.size(); i++) {
        addEdge( A[i], B[i], C[i] );
        addEdge( B[i], A[i], C[i] );
    }
    
    //Dijkstra time!
    auto dijkstra = [&](int s, vector<int> &dist) {
        set<pair<int,int>> Q;
        const int INF = 2000000000; 
        dist.resize(N, INF);
        for (int i = 0; i < N; i++) {
            Q.insert( {INF, i} );
        }
        auto push = [&](int x, int d) {
            if (d < dist[x]) {
                Q.erase(Q.find( {dist[x],x}));
                dist[x] = d;
                Q.insert( {dist[x], x} );
            }
        };
        push(s, 0);
        while (! Q.empty()) {
            auto it = Q.begin();
            int x = it->second;
            Q.erase(it);
            
            for (int i = 0; i < degree[x]; i++) {
                int v = g[x][i];
                int we = w[x][i];
                push(v, dist[x] + we);
            }
        }
    };
    vector<int> dist, rdist;
    dijkstra(0, dist);
    dijkstra(N-1, rdist);
    
   
    // if any of the shortest paths visits an edge of weight 0, the result
    // is -1. It is possible to have 0s in the input and result diff to -1
    for (int i = 0; i < A.size(); i++) {
        if (C[i] == 0) {
            int u = A[i], v = B[i];
            for (int r = 0; r < 2; r++) {
                if (dist[u] + rdist[v] == dist[N-1]) {
                    //critical
                    return -1;
                }
                swap(u,v);
            }
        }
    }
    
    // And now the part in which we actually count the roads.
    vector<long> dp(N);
    vector<int> byRDist(N);
    for (int i = 0; i < N; i++) {
        byRDist[i] = i;
    }
    sort(byRDist.begin(), byRDist.end(), [&](int a, int b) {
        return rdist[a] < rdist[b];
    });
    for (int u: byRDist) {
        dp[u] = 0;
        if (u == N-1) {
            dp[u] = 1;
        }
        for (int i = 0; i < degree[u]; i++) {
            int v = g[u][i];
            int we = w[u][i];
            if ( (rdist[v] < rdist[u]) && (dist[u] + rdist[v] + we == dist[N-1]) ) {
                dp[u] += dp[v];
            }
        }
        dp[u] %= MOD;
    }
    return dp[0];
}

The rest

I was very slow, everybody else has a much better score. I hope many of them fail. I am confident in the correctness of my solutions and I don't suspect of any likely implementation bug. Typing this as the challenge phase begins.

During challenge phase: 8 minutes of challenge phase, and I doubt I'll score a successful challenge, there are some tough challengers in my room and they are very quick to find errors. There seem to be many ways to get 450 wrong.

Regarding c++ vs. python (in algorithm contests)

Reddit...

Dear people from reddit. Someone linked this blog to you. And it was wrong for it to happen. Because the intended audience of this blog is *not* software developers/ programmers at /r/programming. The intended audience is people who participate in programming contests. Specifically TopCoder. This blog post was made for those people in mind. For example, chances are that you have no idea what an editorial is in this context. The blog is also extremely tongue-in-cheek as I write it using my vexorian persona.

We already know very well about performance. Python runs around 10x slower in comparison to c++ in these contests. Since that's a known fact about the whole thing that's why I didn't even mention it or include "benchmarks".

One thing that you must understand is that the contests are basically designed around C++. This comparison has nothing, absolutely nothing, to do with what language is better than the other for general usage. This is no ammo in some language supremacy flame war. In other words: There is absolutely no need to come to insult me. If you just want to know which language is better for general usage: Just pick the one you are more experienced with and that fits your needs better; If you are undecided, go look for more professional comparisons or something...

--------------------------

So, yesterday I was writing an editorial and things were going ok. I was solving a problem when I decided to include both c++ and python code, like I've been doing plenty of times lately. In this occasion, I wanted the c++ not to rely on libraries or built-in functions, so that someone who just started reading on the syntax understands the code. For the python one, I wanted to make a one-liner, because it was totally possible.

I was aware that this choice would make python 'look good". What I didn't expect was to wake up today to the news that TopCoder's facebook account decided to use those codes as the preview image when talking about my editorial... So now we have this image circulating around that seems to make the point that python allows much shorter code than c++ and it is in part because of me. This was the final trigger that made me write this post, I was planning to write something like this since a while ago.

Python - good?

My relationship with python started on rocky ground. Once upon a time, I was a lame programmer who was obsessed with speed and performance. Python, along with Java and many others was a language that was very slow. So there was no way I would ever use it. Worse, python specifically had syntactically-relevant indentation, which also meant it didn't have brackets or begin/end or something similar. Block depth was implicit. For a good while, this feature made python code make me feel dizzy. It is like the code is floating without something that holds it!. It actually still annoys me, but not as much as before.

Eventually, I did some maturing as a programmer. I learned many languages. Learned about good practices. I even made my own languages as an attempt to fix a very bad language (And discovered many things about what works and what doesn't). So I eventually gave python a chance. It helps to have an editor with code-folding or indentation guides. It removes that feeling of things floating without being held :).

My learning process was slow because I never had any project that I had to write in python. But it did become my main calculator application. I also use it for small scripts and to generate test cases for programming contest problems.

There are many good things about python. There are also some things I am not a fan off. What I like about python is that instead of trying to be a better C++ (*cough* Java and C# *cough*), it tries to be a better language. It is also free and not tied to some evil mega-corporation (*cough* Java and C# *cough*). By the time I heard they were going to add python to the list of languages in Topcoder SRMs, I was excited because I would get to use it in editorials, and it seems like a great tool for them.

Python in editorials

And so, began the journey. I started to use python to solve SRM problems and include the code in editorials. I now have some things to say about using python in TopCoder contests.

Small code

Python really shines in problems that need little code. The stuff other languages need to do the simplest of operations, is usually very easily-implementable if not completely built-in. The code from the problem in the image I first talked about is a good example.

class GooseTattarrattatDiv2:
 def getmin(self, S):
    return len(S) - max( S.count(ch) for ch in S )

It is even self-documented. The result is equal to the length of the string, minus the maximum number of times a character appears in S.

It is actually very fun, and a major source of procrastination, to try to come up with the smallest possible python code to solve a problem.

class InsertZ:
 def canTransform(self, init, goal):
    return "Yes" if (goal.replace('z','') == init) else "No"

If the goal is equal to the init after removing all Zs from it, return Yes.

Making readable code

So the division 2 problem of SRM 588 was a typical "bit masks" problem. You had to iterate through all the subsets of songs. More so, songs had two attributes: length and tone. Typically , the code for this looks very messy in c++ or Java. You end up using bitmasks, which means that you will have beautiful things like (1<<i)& in your code, then for each i, you check if it is in the bitmask, if so, call duration[i], etc, etc... You need a formula between the maximum, minimum tones and the sum of durations and other things

The python code, however, looks like this:

import itertools, collections
 
class GUMIAndSongsDiv2:
 def maxSongs(self, duration, tone, T):
    n = len(tone)
    #making this a named tuple is not needed, but it adds readability:
    Song = collections.namedtuple('Song', ['tone', 'duration'] )
    # Make a list of song objects:
    songs = [ Song(tone[i], duration[i]) for i in range(0,n) ]
    res = 0
    for c in xrange(1, n+1):
        # c is a number from 1 to n, increasing order
        for picked in itertools.combinations(songs, c):
            # "picked" is a set of c songs:
            durationSum = sum( s.duration for s in picked )
            minTone     = min( s.tone     for s in picked )
            maxTone     = max( s.tone     for s in picked )
            if durationSum + maxTone - minTone <= T:
                res = c
    return res

itertools.combinations creates an iterator from the iterator that you pass to it, in this case the songs. The new iterator will contain all the combinations of c songs. So if you try c in increasing order, you can easily get all the subsets. In order to easily divide the songs in subsets, we actually made a list of the song objects. To create and define those objects, we only needed a single line to call collections.namedtuple...

There are many ways in which this code is amazing (to me). And it baffles me how readable it is. It is almost a description of the algorithm for the problem, instead of being code. The alternative in c++ or worse, Java , would be much messier. Check it:

int maxSongs(vector <int> duration, vector <int> tone, int T)
{
    int n = tone.size();
    int best = 0;
    // for each subset of songs represented by a bit mask:
    for (int mask=1; mask<(1<<n); mask++) {
        int maxTone = -1, minTone = 200000, durationSum = 0, c = 0;
        // find the minimum/maximum tone, the sum of durations and the
        // number of songs in the subset:
        for (int i=0; i < n; i++) {
            if (mask & (1<<i)) { //is song i in the subset?
                maxTone = max(maxTone, tone[i]);
                minTone = min(minTone, tone[i]);
                durationSum += duration[i];
                c++;
            }
        }
        // If selected songs in optimal order fit the time constraint, this is valid:
        if ( durationSum + maxTone - minTone <= T) {
            best = std::max(best, c);
        }
    }
    return best;
}

Being able to use functions

Most large algorithms will need you to use many functions and call them. You know what this means? In c++ / Java this means that you will have to copy some variables and the arguments as global variables or class members so that the functions can use them. To me, this is very annoying and has been a source of bugs because if you forget to actually make the copy or assign it correctly, you are screwed. c++11 allows lambdas, and I was able to use them to avoid this issue somehow, like in test SRM #2. But c++ lambdas have a very big issue, you cannot (easily) have recursion with them. You need to work around it somehow. The current best answer to the problem I have is to use std::function explicitly when declaring the lambda and it is very messy.

Python has nested functions instead of lambdas, so making them recursive is not hard at all. It is quite normal. Check the codes in the post about SRM 589 and you will see what I mean.

Some more obvious advantages

Sure, there are some obvious things like how overflow is not possible. That whole stuff about tuples is nice to have. Too many times you are dealing with points or coordinates so you are using tuples, so something like (x,y) = ... makes more sense than x = ... ; y = ... The native set() and dict() types. Etc.

Some bad things

After I started to apply this python knowledge to make code at topcoder, I couldn't avoid thinking. What if this is more convenient during a contest? What if I move to python?

Then I try to use this python thing for a larger problem and start to notice a darker side...

My pet peeve against dynamic languages

This is not something new that I just found, or that is specific to programming contests. I have to mention it. Languages that allow you to declare and use variables in the fly. Languages that are not compiled. They have this annoyance, and it is that your typos won't be discovered until the line with the typo is executed. You write these 100 lines of code and run your program. It is not until a few seconds of execution, that the program reaches a line of code in which you type blok instead of block. Sorry, do it again.

Multidimensional "arrays"?

Python doesn't have that array concept, it has tuples and lists. Lists are one-dimensional, but of course, you can make a list of lists and it can be indexed like a bi-dimensional array - a matrix. You can go out of your way and do the same for a list of lists of lists of lists of lists, and you have something with 5 dimensions!

In the Real World™ Programming world, this is likely not a big issue. In the algorithm/programing contests world, specifically the Topcoder world, it can be quite a pain. We have those dynamic programming problems with 4 dimensions and it is like nothing to write home about. You might even have 6 dimensions.

What in c++ looks like :

int dp[w][h][t][n][2][3];    // Just a typical day in topcoder land
memset(dp, -1, sizeof(dp));
dp[x][y][f][p][1][0] = 6;

In python looks like:

dp = [[[[[ [-1]*3 for i in xrange(2) ] for j in xrange(n)] for k in xrange(t)] for a in xrange(h)] for b in xrange(w)]
dp[x][y][f][p][1][0] = 6

Of course, that's ridiculous. Maybe the real problem is that we are approaching it the wrong way. We could use a dictionary?

dp = dict() 
dp[ (x,y,f,p,1,0) ] = 6

But then, since it is a dictionary it will have overhead in accessing the elements... Maybe a list but we will translate the indexes to a single integer? This is what C arrays do anyway.

dp = [-1] * w*h*t*n*2*3 
dp[ (x*h*t*n*2*3 + y*t*n*2*r + f*n*2*3 +  p*2*3 +  1*3 + 0 ] = 6

Yeah, a bit complicated... too, back to square one.

The petty default recursion limit

Speaking of dynamic programming and memoization in functions. I attempted to use python for FlippingBitsDiv2 and it worked... except that it was actually reaching the recursion depth limit way too quickly. In that problem, the recursion depth is as large as 2500, which doesn't really strike me as too high. Specially not for these contests... But that's the default.

Turns out it is perfectly possible to raise the depth limit with a call to a sys. function. So this problem isn't a big deal. Except that you need to be conscious of it when solving something using recursion.

Memory...

I knew of the obvious weakness. Speed. Python's dynamism comes at that price. Actually, I tried to do some tests and it seems like the time factor is 6 times or even 10 times slower. I haven't actually found a division 1 hard problem that can be solved in python yet.

What I didn't expect was the memory usage. This happened to me while solving GameInDarknessDiv2. It needed a depth-first search on a large graph. If you take a look at the c++ code, there are plenty of implementation bottlenecks. My first idea was to use python code for this solution. Because it can make easier to read code if you work for it. The result is beautiful:

def check(field, moves):
    # useful dictionary from move char to position offset:
    move = {'R':(1,0), 'L':(-1,0), 'U':(0,-1), 'D':(0,1) }
    
    # given a position and a move character, return the new position:
    def doMove( (x,y), ch):
        return (x + move[ch][0], y + move[ch][1])

    # find Alice and Bob's initial positions:
    (w,h) = ( len(field[0]), len(field) )
    for y in range(0,h):
        for x in range(0,w):
            if field[y][x] == 'A':
                (ax,ay) = (x,y)
            elif field[y][x] == 'B':
                (bx,by) = (x,y)

    # Save Alice's positions for each of Bob's turns:
    moves = string.join(moves, '')
    alice = [ doMove( (ax,ay), moves[0] ) ] 
    for ch in moves[1:]:
        alice.append( doMove(alice[-1], ch ) )
    # if in the first move, Alice moves towards Bob, it is game over for Bob:
    if (bx,by) == alice[0]:
        return "Alice wins"

    #And the DFS:
    T = len(alice)
    
    visited = [ [ [False]*(T+1) for i in xrange(0,h) ] for j in xrange(0,w) ]
    winner = ["Alice"]
    
    def dfs( (x,y), t):
        if not visited[x][y][t]:
            visited[x][y][t] = True
            if t == T:
                winner[0] = "Bob"
            else :
                for ch in "URDL":
                    (nx, ny) = doMove( (x,y), ch)
                    if (0 <= nx < w) and (0 <= ny < h) and (field[ny][nx] != '#'):
                        if (alice[t] != (nx,ny) ) and ( (t+1 == T) or (alice[t+1] != (nx,ny)) ):
                            dfs( (nx,ny), t+1 )
                            
    #oops, default recursion limit is too conservative for our DFS:
    sys.setrecursionlimit(T+10)
    #call DFS:
    dfs( (bx,by), 0 )
    #and done:
    return winner[0] + " wins"

The amount of code that is not wasted in boring activities is very relevant, at least to me. The use tuples also makes many things make more sense. It is more self-documenting. However, when I actually run system tests on that solution, I found plenty of issues. The need for a 3D "array" was the first. Then the recursion limit. But the one thing that I couldn't fix was the fact that this code was reaching the 64 MB limit.

The memory usage of this approach is `O(w*w*h*h)`, for `w,h <= 50`, such a memory complexity didn't usually seem like a problem to me when using c++ or Java. So I didn't expect this coming at all. 2500*2500 indexes in a boolean array take around 5.96 MB. In python, however, it turns out that lists holding 2500*2500 elements are too heavy (They are still too heavy even if I use the single-list approach that converts 3D indexes to a single dimension). What is going on?

It is not so surprising. Python is dynamic, a single index in a list can describe plenty of things, not just a number or a boolean. The reserved memory is probably at least 4 bytes for each index, that means 23.84 MB instead of just 5. It is more than that. I discovered a secret python function called __sizeof__, it tells me that a list of 2500*2500 False values is worth 47.68 MB (somehow). That is a good chunk of our 64MB. So apparently, not only is the available time around 10 times smaller, it seems like memory is 3 times smaller in practice too.

In codejam

In google codejam, python is the third most popular language and it is very close to Java, in fact, in round 1A it beat Java in popularity for the top 20% contestants. In TopCoder, python isn't working so well (But at least it has beaten Visual Basic and seems to be on its way to beat C# :) ). Python is quite a recent addition, we have had it for 4 official SRMs so far..., there may still not be many coders who know about its availability and the python coders that didn't give TopCoder a try because of the lack of python probably haven't heard of the change yet. It is no surprise usage is low right now. But will it ever reach a popularity level similar to what it has in google code jam?

Codeforces has had python since inception and python's numbers don't seem to match Codejam's (Although a tool like go-hero.net for codeforces language statistics would definitely be great to have, I couldn't find such thing). Codeforces and TC have an audience that is more focused on ACM-ICPC than the Codejam, though, so that skews things up. I have an alternative theory though: Hard time and memory limits like those in TopCoder and Codeforces just don't work well if you want a language agnostic contests. Making the time limits different is not a good solution either, as it would be difficult to pick good limits. What codejam does well is that, with 4 minutes/8 minutes time limits and using your computer's memory instead of google's, the constant factor is quite irrelevant. That allows plenty of more languages to work, including python.

Move to python?

I think python is a great language. But I don't think I will move to using python during contests. At least not for the time being. I am still not as good with python as I am with c++.

Also, although python has a powerful expression power. c++ has also improved a big deal with c++11. The big advantage I would have assigned to python over c++ would be the support for functions as first-class objects and closures. But now c++ has it too. So...

Remember the initial dilemma? In reality the true c++ version, using more of the available features would look like this:

int getmin(string S) 
{
    int n = S.length(), m = 0;
    for (char ch : S) {
        m = max(m, (int)count(S.begin(), S.end(), ch) );
    }
    return n - m;
}

It is still ugly, but not so bad:)

A bonus: Swapping integers

Last week, there was a image circulating around. How to swap two integers without using an additional variable. The "C version": a=a+b; b=a-b;a=a-b;. Then one of those obnoxious meme faces throws a misogynist slur and says that python has: a,b = b,a. Ahahahaha, so python is better, supposedly.

Let me introduce to you, the c++ way: swap(a,b). It has a nice advantage: It is self-commenting. It also follows [once and only once]. But the reason I like is because of what it says about c++. (a,b) = (b,a) is cool, but it is an builtin language feature that was introduced precisely to fix this problem and similar ones. The std::swap is a library function.

template <class T> void swap ( T& a, T& b )
{
  T c(a); a=b; b=c;
}

It is a result of things like templates, and also by reference arguments. Powerful features that also solve plenty of other problems and not just swap. std::swap works with any data types too - Unlike the C approach. :)

Test SRM #2 : Revenge of the C++11

So, there is another test SRM scheduled for Saturday. This is great news. Whilst TC will be testing new compiler versions for c++ and python, I will be testing a new code environment.

It looks like TopCoder is getting gcc-4.8.1. This is quite serious. Because the c++11 support will be enabled. Take a look to the list of c++11 features available in gcc-4.8.1: http://gcc.gnu.org/gcc-4.8/cxx0x_status.html. Compare it with the puny gcc-4.4 list: http://gcc.gnu.org/gcc-4.4/cxx0x_status.html. Of course, some things like threads will not be supported in SRMs, but otherwise the list of syntax candy will be increased greatly. gcc-4.8.1 is so new, that ubuntu 12.04 repositories don't support it. The list of new features is humongous. If you thought auto and tuples were a big deal. Brace yourselves...

range-based for loops

string canTransform(string init, string goal)
{
    string x = "";
    //Beautiful:
    for (auto ch : goal) {            
        if ( ch != 'z') {
            x += ch;
        }
    }
    return (x == init) ? "Yes" : "No";
}

You could use char ch too if that's your taste.

Lambda expressions

Remember sorting in c++? When the ordering is not a trivial one, you often had to declare a whole struct with strange syntax inside and then use the struct in the call to sort. This is an alternative to all that:

// How to sort elements in a vector by their absolute value:
vector<int> v = {5, 0,-1,-5, -3,3,2, -5};
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);
});
// shows: 0 -1 2 -3 3 5 -5 -5
for (auto &y : v ) {
    cout << y << ", ";
}
cout <<endl;

Lambdas are anonymous functions that you can create inside code blocks. In the example we use the [](int a, int b) { return boolean } syntax to create a function pointer that is then used and called by sort. The world of lambdas is a huge one. And their usefulness is understated the first time you hear about them. Here is a page that explains them throughly.

Closures

One of the good things about lambda syntax is that it enables closures. Aaaand things just got crazy...

For example, what if you want to sort some numbers `x` by the values `y[x]` in some array?

vector<int> y = {10, 7, 8, 3, 5, 1 ,1};    

vector<int> x = {0, 1, 2, 3, 4, 5 ,6};
// sort x[i]s by y[x[i]]:
sort(x.begin(), x.end(), [=](int a, int b) {
    return (y[a] < y[b]);
});
// note the [=] syntax, we are making copies of vector<int> y.

// display 5, 6, 3, 4, 1, 2, 0,
for (int z : x ) {
    cout << z << ", ";
}
cout <<endl;
// we can use int z : x
// If we did int &z: x, they would be references
//   (modifiable and maybe faster)

So...

It's hard to overstate my satisfaction.

If only the python version was python 3, everything would be 110% perfect

More about c++11 - tuples, tie and make_tuple

Remember that last post about new C++ features enabled in TopCoder's servers? These new features (and far more) are also available in Codeforces if you choose GNU c++0x 4 as language (instead of plain GNU c++) and in those contests in which you can compile locally by just using a recent g++ version with the -std=c++0x modifier.

But there is more about the improvements in C++. Have I ever told you about how much I like std::pair? Let me introduce pair's younger brother, std::tuple:

Why and how were tuples added?

One flaw about std::pair was how it stores only two values. Which made it of limited use. There were plenty of times during contests where I had to use nested pairs. Ugly code like queue<pair<int, pair<int,int> > >. The optimal would be to have something that behaves like std::pair, but allows more than two values. A solution like a std::triple would have been a poor solution though, because it would still be limited. But of course, templates with variable argument number would be crazy, right man?

Enter variadic templates, a c++11 killer feature, in my opinion. Templates with variable number of arguments. They allow these tuples and plenty of other things through recursion. It is amazing the sort of things c++ will be able to do at compile time with these. Imagine a strongly typed printf-like function, for example. The good news is that these templates work in TopCoder's ultra old g++ 4.4, and CodeForces' compiler is even more recent. So they are fair game. While C++, the language, adds variadic templates, the STL, the standard template library, is the one responsible of adding tuples.

Let us get to use them

Just add the include: #include <tuple>

Now we basically use std::tuple the same way we used std::pair in the past, except that we can now use more than two arguments. Let us start with an easy one, imagine that you are running a BFS (Breadth-first-search) on a graph that is described by three dimensions, so imagine that it is a 3D grid with x, y and z. (So typical).

queue<tuple<int,int,int> > Q;
bool visited[X][Y][Z];
memset(visited, 0, sizeof(visited));

visited[0][0][0] = true;
Q.push( make_tuple(0,0,0) );
while (! Q.empty()) {
    tuple<int,int,int> node = Q.front(); Q.pop();
    int x = get<0>(node), y = get<1>(node), z = get<2>(node);
    //... etc
    // augment edges from node (x,y,z)?
}

The first bad news is that things like get<index> are needed to access the tuples. They are a bit verbose for my taste. Also note that although they use integers as a matter of indexing, they have to be constants. (Although if you really need variable indexes, you probably need a vector and not a tuple). However, there was possibly no choice in this case, because in order to implement variadic templates, you need some recursion, which means that indexing is likely needed...

But let us go on. Although the get>0> seems heavy, compare with the alternatives. Coding a whole struct? Using a nested pair like I did in one of the first paragraphs? So verbosity could be worse.

The reality is that tuples (or pairs) are not meant to be a replacement of structs or classes, but just something that will help you in some peculiar cases. Like in the post about std::pair, let us deal with a comparison problem: John wants to pick between two strings. He prefers strings that have a larger number of even letters (b,d,f,...). If two strings have the same number of even letters, he prefers the one with a smaller length, if two strings have the same number of even letters and the same length, he prefers the lexicographically smallest one. As simple as:

int even(const string & x)
{
    // count the number of even characters
    int c = 0;
    for (int i=0; i<x.size(); i++) {
        c += ( x[i] % 2 == 0);
    }
    return c;
}

// Given a and b, picks the string that John likes the most:
string johnLikesString(string a, string b)
{
    auto q = std::min( make_tuple(-even(a), a.length(), a), 
                       make_tuple(-even(b), b.length(), b) );
    
    return get<2>(q);
}

Like with std::pair, tuples can be compared using the common relational operators (They implement lexicographical comparison for the values in the order in which they are in the tuple, so element 0 is compared first, if both are equal, element 1 is compared and so and so). Which means that we can use std::min() to pick the smaller of two tuples. Since we wanted the string with the larger number of even characters to be picked, we call -even(...) instead of just even(). At the end, the tuple that is picked by std::min will contain John's preferred string as element #2.

Thanks to relational operators like `<` , `>` , `<=` , `>=`, being implemented automatically for our tuples, we can sort tuples using std::sort. We can also use tuples in std::set, or as keys in std::map.

Also note the cameo by the auto keyword. A great feature. In this case, we don't even need to know the type of the q variable in order to use it. After some inspection, we can see that its type is: tuple<int,int,string>.

std::tie

std::tie is an interesting thing, it does something similar to std::make_tuple, but it uses "lvalue references" instead of creating copies of the values. For simple types, like ints it is not important. Big deal, you are creating a copy of number 5 in memory. But what if you want to compare data structures that could be sort of big? Like in the previous example, what if the strings could be 10000000 characters long? Creating new copies of the strings could be too expensive, so expensive that you reach a memory limit in a problem. But it is not only memory, creating copies of objects takes time.

string johnLikesString(string a, string b) //using by value-arguments sorts of makes
                                           // the following optimization a bit worthless,
                                           // I know.
{
    // tie uses references, but we can't use a reference to a temporary
    // object. So we couldn't use a.length() directly inside of std::tie
  
    int aeven = -even(a), alen = a.length();
    int beven = -even(b), blen = b.length();
    
    // Comparing without creating a copy of the strings:
    if (std::tie(aeven,alen, a) < std::tie(beven, blen, b) ) {
        return a;
    } else {
        return b;
    }
}

Pitfalls and a bonus

Nothing is perfect, specially not c++, not even c++11. Actually, c++11 follows the long tradition that coding in c++ is a lot like operating riding a rocket. A rocket is a fast method of transportation and it is the product of plenty of work and research. But god, if you ride it, it will explode in your face eventually.

The usual std::pair issues stand, although they seem to behave a bit better. But for example, the following line of code will make your compiler throw hundreds of syntax errors at you:

tuple<int,int,string> a = make_tuple(4,5,"ssss");

Well, of course, the issue is that "sss" is a const char*, did you expect the tuple to know that it can cast const char* to std::string? hahaha. And since the error occurs in the third step of the tuple recursion, your compiler will be very confused. There are ways to fix this.

// make the typeo f the argument explicit:
tuple<int,int,string> a = make_tuple(4,5, string("sss") );

// use make_tuple with explicit types:
tuple<int,int,string> a = make_tuple<int,int,string>(4,5, "sss" );

// use make_tuple with explicit types and abuse auto:
auto a = make_tuple<int,int,string>(4,5, "sss" );

// Also abuse the new { } initializer:
auto a = tuple<int,int,string>{4,5, "sss" };        

// Now that I think about it, the whole thing was very silly:
tuple<int,int,string> a(4,5,"sss");  

But don't be sad. Here is an eastern egg for you. Swapping the values of two variables, python style:

int x = 5, y = 7;
//swap x and y:
tie(x,y) = make_tuple(y,x);

// All possible because tie uses references and make_tuple creates copies

int z = 6;
//cycle x,y,z = (y,z,x)
tie(x,y,z) = make_tuple(y,z,x);


//Greatest common divisor, the way Euclid intended:
int gcd(int a, int b)
{
    while (b != 0) {
        tie(a,b) = make_tuple(b , a%b);
    }
    return a;
}

TopCoder Test SRM, new c++ features

Have you heard, there will be a Test SRM in just a couple of hours. The intention of the SRM is to test new* compiler versions. (* Relatively speaking). But if you want to practice, a test SRM is a good chance, because the problems will be reused but a surprise, and the time limit will simulate a real contest. It also introduces Python as an usable language. Unfortunately for python coders though, Arena plugins shall take a while to get updated to work with python.

Speaking of the new language versions. The new version for the g++ compiler is 4.4. It is a bit old, but at least it can be found in most Linux repositories (unlike the ultra old version that was in use before). The admins say that even newer versions will be used later.

The upgrade will remove some deprecated features. Most notably, the cool min/max operators like <?, >?, <?= and >?=.

Most importantly, there are new features! Specially because g++ is called with -std=c++0x. In other words, some features planned for c++0x will be available in TopCoder SRMs in the future and in today's match. Of course, not all of them. g++ 4.4 only has some of them implemented. But I found a list: http://gcc.gnu.org/gcc-4.4/cxx0x_status.html

There are a couple of things that C++ coders should know.

auto keyword

While it is in terrible taste to use the word auto instead of var, the new auto keyword will prove to be very useful when dealing with the STL.

void doSomething( vector< pair<string, pair<int,int> > > toocomplex ) 
{
    auto copy = toocomplex; //makes a copy of toocomplex.
    //blah blah blah...
    
    

read more

Initializer lists

This is now possible:

// a quick array:
int A[] = {1,2,3,4,5,6};
cout << A[3]<<endl;

// a vector<int>:
vector<int> B = {5,6,7,89};
cout << B[2] << endl;

// Or how about a set?
set<int> B = {1,2,3,7,8,9};
// Is 3 in the set? (will show 1)
cout << B.count(3) << endl;
// Is 4 in the set? (will show 0)
cout << B.count(3) << endl;

// Yep, you can use any expression, not just constants:
int x = 5, y = 7, z = 8;
set<int> b = {x,y,z};

// Forget about make_pair:
pair<int,int> v = {2,3};

Nuff said.

long

Have I ever complained about having to type long long instead of just long? Yes, yes I did.. Fear not, because long is 64 bits now, without having to type long long.

More

Plenty of changes for templates, look at the gcc 4.4 table linked above for more. Most of these template features would be useful if you are coding data structure libraries. static assertions could be nice to avoid some pit falls. Also, vector<int, pair<int,int>> is valid syntax. That double closing > has caused plenty of problems in the past to people that are just starting getting hold of the STL.

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...