Outrageous: for_each #define

When people think of C++, over-verbose is not usually the first thought. But it actually can really get so when dealing with the STL. Things like .begin() and .end() are really good at breaking your willing suspension of disbelief when you want to believe that C++ is a language that is there to help you :). The c++0x standard will improve c++ in many ways, but I fear it does not really enough new ways to save the problem of typing .begin() and .end().

Here is my problem. You have a set of pair<int, pair<int,int> > . That sort of STL abuse happens just about any time you are in a programming contest and wish to avoid having to make your own class with three elements and tie breaking comparisons. The pair and set templates are very useful when implementing some algorithms. The set template can function as a priority queue and also as a range tree if you know how to extract juice out of it. The thing is that it happens too frequently, that I need to iterate through the elements of a set of some complex data structure.

set<pair<int,pair<int,int> > > s;
for(set<pair<int,pair<int,int> > >::iterator q = s.begin(); q!=s.end(); q++) {
    cout<< q->first <<", " << q->second.first << ", " << q->second.second<<endl;
}

If that did not induce you a headache, it is because you have been over exposed to c++. I love c++, so I consider it a good thing, but things can always be better.

The one million question is why does not c++0x seem to introduce anything close to Java's for(:) syntax, which allows you to iterate through containers very easily. I really, really dislike defines, but for some reason, c++ uses them as an excuse not to implement some features, because supposedly you can make them yourself by abusing macros. Well, in this case, I am starting to think that a macro is the cleanest solution. That is the reason I have begun typing it during topcoder matches, and I think I will add it to my template by default and do something to make a script remove it from my submission when it is not in use. The for_each macro I am using is as follows:

#define for_each(s,v) for(typeof((v).begin()) s=(v).begin(); s!=(v).end(); s++)


Most special thing is the use of the g++ extension typeof(). It may eventually get removed from g++, but that is probably going to coincide with the day c++0x auto keyword gets added. (auto q=v.begin() is even better).

The previous code becomes much clearer:

set<pair<int,pair<int,int> > > s;
for_each(q,s) {
    cout<< q->first <<", " << q->second.first << ", " << q->second.second<<endl;
}

The benefit is that for_each should work with every STL container. But you would need a different macro if you want to, for example, iterate a vector in reverse order.

Member SRM 503 - Div2 250, Div2 900

ToastXRaspberry
Link to problem statement
This problem is very simple, so much that I don't think an explanation would actually help. I think this is a great problem to solve alone when you are starting the path to programming, and I won't ruin that experience.


KingdomXCitiesandVillagesAnother
Link to problem statement
After solving some problems, this problem will give you a Minimum spanning Tree vibe. That is because the problem asks you to connect many things together in a way that the cost of connecting them all together is minimum. You would notice that the final connected result does not need to have cycles, because cycles would usually mean that you are doing more connections than necessary. The main difference though, is that you we are not allowed to connect cities together (because of the way the rules explained in the statement work) and it is not necessary to do it. We want to connect each village directly or indirectly to a city and nothing else. Basically, each city will end up being the center of a network of villages that are connected to the city and also to each other, directly or indirectly. Because there won't be cycles, each city will belong to a different tree. The solution will be a set of trees, a forest.

In problems that are initially so similar to the minimum spanning tree problem, it is usually a good idea to try to find a way to reduce the problem to the MST problem, because that is a known problem that is not so hard to implement. As mentioned, the main issue is that each city will have its own tree of villages attached to it. When connecting a village to a city, the rules described specify only that the cost to connect a village to the city is the minimum. How about simply considering all cities a single node? If all cities were joined together, all the trees in the forest will then become a single tree because they would all have the city node in common. The trick in here is to note that the distance between a village and this special city node is the minimum distance between the village and any city.

If we used this special city node instead of the cities, we could then use a MST algorithm to connect all the villages and the city node together in a single tree of minimum cost. Here comes some imagination: After this MST is found, you can return to the case that has many cities and a tree per city. Simply consider any resulting edge between a village and the special city node, and find a city whose cost to connect the village to it is the same as the cost of the edge picked to connect the village and the special city node, then replace the edge with one that connects the village to the normal city. This loosely allows us to see that the minimum spanning tree when there is a combined city node as we mentioned will also result in the minimum cost to solve the original problem.

There are other ways to see the problem, one is to consider all the cities already connected to each other. This means that the cost to connect the cities has already been considered and we do not have to include it in our calculation. We can translate this as there being many edges of cost 0 connecting the cities together. We can then, again, find the minimum spanning tree. After this, we can delete all of those cost 0 edges and we would find a forest as the one the original problem wants.

What is left is to implement the minimum spanning tree algorithm after creating the new graph that either contains those 0-cost edges or a single combined city node. The usual tools of the trade are Prim's algorithm or Kruskal's algorithm. For this problem, it does not really matter which of them you pick. I picked Kruskal by preference, it needs an efficient way to do union, but it is also useful sometimes when you need to find the minimum cost forest of n trees instead of the minimum cost tree. The c++ implementation follows:

#define for_each(q,v) for(typeof(v.begin()) q=v.begin(); q!=v.end(); q++)
struct KingdomXCitiesandVillagesAnother
{
    // We use this for Kruskal's union find:
    // Finds the grand parent of x, assigns it as parent
    // for all the ancestors of x to avoid repeating the process
    // a next time. This is just a Disjoint-set forest with
    // flattening 
    // (http://en.wikipedia.org/wiki/Union_find#Disjoint-set_forests)
    void toRoot(int *parent, int &x) {
        int y = x;
        while (parent[y] != y) {
            y = parent[y];
        }
        while (x != y) {
            int z = parent[x];
            parent[x] = y;
            x = z;
        }
    }

    double determineLength(vector <int> cityX, vector <int> cityY, 
                           vector <int> villageX, vector <int> villageY)
    {
        int vn = villageX.size();
        int n = vn + 1;
        
        // Make a custom graph with vn+1 nodes.
        // The first vn nodes are villages.
        // The last node is the conjunction of all cities.
        // Cost to connect a village to the conjunction of all cities
        // is equal to the minimum road between the village and any city.
        set< pair<double, pair<int,int> > > edges;
        
        for (int i=0; i<vn; i++) {
            for (int j=0; j<i; j++) {
                double dx, dy;
                dx = villageX[i] - villageX[j];
                dy = villageY[i] - villageY[j];
                edges.insert( make_pair(sqrt(dx*dx + dy*dy), make_pair(i,j) ) );
            }
            double toCityCost = 1e100;
            for (int j=0; j<cityX.size(); j++) {
                double dx, dy;
                dx = villageX[i] - cityX[j];
                dy = villageY[i] - cityY[j];
                toCityCost = std::min(toCityCost, sqrt(dx*dx+dy*dy) );
            }
            edges.insert( make_pair(toCityCost, make_pair(i,n-1) ) );
        }

        //
        // Let us do Kruskal's algorithm on the custom modified graph.
        // parent array for union algorithm
        int parent[n];
        for (int i=0; i<n; i++) {
            parent[i] = i;
        }

        double total = 0;
        // try all edges in ascending order of cost.
        for_each( e, edges ) {
            int u = e->second.first, v = e->second.second;
            toRoot(parent,u);
            toRoot(parent,v);
            if ( u != v ) { //different sets, join them by
                            //adding the edge to the tree
                parent[u] = v;
                total += e->first;
            }
        }
        return total;
    }
};

Member SRM 503 - KingdomXCitiesandVillages

It was a nice problem set, I think the difficulties were all all right, except for the div1 1000 that was not solved by anyone. The div1 250 had perhaps more images than needed and they were a little distracting, but that's my only nitpick, really.

KingdomXCitiesandVillages

Link to problem statement

It becomes a habit, in expected value problems, it is sometimes possible to separate the calculations and then add them up, because of the expected value's linearity property. This was not an exception. Let us call the length of each road a cost. When building a road, the cost of building it is the length of the road. The order of villages is random, but eventually each of the villages will be picked exactly once. And for each of the villages, exactly one road will be built. Expected_Length( all roads) can be rephrased to Expected_Length( road1 + road2 + ...) and since each road is added for each village, then it can become : Expected( cost_to_connect(village1) + cost_to_connect(village2) + ...). Because of the aforementioned linearity property, we have that the result can be seen as:

Expected(Cost to connect village1) + Expected(Cost to connect village2) + ... Expected(Cost to connect villageN)

Then if it is possible to find the expected cost for each village, we can just add them up to find the wanted result.

Expected cost to connect each village
Since we can treat each village independently, assume we are working with a village i. The road that will be built will have the minimum length among all the roads that can connect the village to cities or to villages that are already connected. Then the cost depends greatly on which villages have been picked before village i. The definition of the expected value tells us that it is equal to: Sum( x * prob_x ) for each x. This means that for each possible road cost X, we need to find the probability that road cost is picked and multiply them. The sum of all those products is the expected cost.

For a given cost X, what is the probability we will pick that value? X would have to be the minimum road length possible between village i and any city or village that is already connected. The minimum distance between village i and the cities will never change, let us call this constant dcity. It is always possible to build a road between the village and a city such that the cost is dcity, regarding X vs. dcity, there are three possibilities:

• X > dcity: Since it is always possible to build a road from the village to a city, then the minimum cost will never be greater than dcity. The probability to have minimum = X is 0.


• dcity = X : If we want the minimum cost to be dcity, then no village with a distance to i smaller than dcity should be picked before village i. If such a city was picked, the minimum distance would be smaller than X = dcity


• X < dcity : For the minimum would have to be equal to X, then no village with a distance to village i smaller than X should be picked. However, it is also necessary to pick at least one village such that the distance between it and village i is X, so that the minimum can be X.

We just need to calculate two probabilities:

• Probability no village with a distance to village i smaller than dcity is picked before village j is picked.


• Probability only villages with a distance to village j that are greater than or equal to X are picked before i and at least one the villages with a distance equal to X is picked before i.

It is possible to calculate those probabilities in many ways. I will use a dynamic programming-like approach. Let us begin with the first case, there are n villages. Among them, we have village i, a set of good villages that can be picked before j and the remaining villages are bad = (n - good) villages that may not be picked before picking village i. We will find a recurrence that simulates the process. This process can be represented by variables good and bad, because we can tell that n = good + bad + 1 (the 1 is village i). At any moment, there is a (1/n) probability to pick each of the villages. So, there is a (1/n) probability to pick village i. If village i is picked, then the event is one of those we want to include in the probability. For each of the good village, there is a probability of (1/n) that it will be picked, so there is a probability of (good/n) that a good village is picked. If a good village is picked, then there will be (good-1) remaining good villages, and village i and the bad villages will stay, so the simulation can continue and in fact, becomes a sub-instance of the problem we are solving, with a different value of good. If a bad village is picked, the event is not one to consider in the probability we want, so we should not include it. In total, the recurrence works as follows:

f(good, bad) {
    n = good + bad + 1
    result = (1/n) + (good/n) * f(good-1, bad)
}

The other case contains some villages such that at least one of them must be picked before the ball. Let us call the number of those villages need. Those villages
are also valid to be picked before i, so they will be a subset of the good villages. Therefore n is still = good+bad+1. In this case, if village i was picked (with 1/n probability) before the needed villages, it is not a valid event. If one of the needed villages is picked (with probability need/n), then we no longer need to pick any more of them, so good=good-1 and need becomes 0, and then the case becomes one with a group of good and bad villages that is the same as the basic recurrence we solved above. If one of the good villages that is not one of the needed ones is picked (probability (good-need)/n), then good = good-1 , need stays the same and the situation becomes a sub-case with different values of good,need,bad. As usual, picking a bad village would make the event not a valid one to consider in the calculation of this probability. The recurrence becomes something like:

g(good, need, bad) {
    n = good + bad + 1
    return (need/n) * f(good-1, bad) + ((good-need)/n) * g(good-1,need,bad)
}

Both recurrences can be joined in a single one. Just make it so when need=0, the case we are dealing with is one in which it is not needed to get any specific village of the good ones.

The recurrences are acyclic. Which means we can just use memoization (Cache the result for each group of arguments, so that the result for each group of arguments is evaluated exactly once). good , need and bad can be at most equal to the number of villages vn , so the total complexity of getting all the calls to the recurrences is O(vn * vn * vn). With vn <=50, that is very fast.

In reality, many people could find it easier or cleaner to just spend some time analyzing the problem (good, need,bad) and calculate the probabilities without a recursion but by other means. In my specific case it is easier to think of recursions, for some reason.

Thanks to the recurrences, we can get the probabilities for each X by first counting the amount of villages that are good, bad and needed for the specific value of X. We can of course not just iterate through all possible values of X from 0 to infinite, so instead we will only focus on those that are possible distances. dcity is a possible value of X. Then we can tell that for every distance between a village j and village i, we can consider it a possible distance. Then there are at most O(vn*vn) such distances. Special care should be put so that we don't evaluate each distance more than once.

In order to get the probabilities, you need to count the number of distances that are greater than or equal to a value, the distances are doubles and that may add some risk to greater than or equal checks. A way to avoid this issue is to notice that Euclidean distances are :

squareRoot((x1-x2)² + (y1-y2)²)

The values of x and y are always integer in this problem. When comparing:

squareRoot(A) < squareRoot(b).

It is equivalent to (A<B) . Assuming they are both non-negative integers. This means that you can just use (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) in comparisons instead of its square root. This way you will always use integers in comparisons. This was not really necessary in this problem. But it is just a habit I made to avoid doubles when possible.

Another thing is, that the coordinates in the input can be as large as 1000000, and that makes the Euclidean distance overflow 32 bits integers. Simply use 64 bits integers to avoid overflow. The final implementation follows:

using namespace std;
#define for_each(q, v) for(typeof(v.begin()) q = v.begin(); q!=v.end(); q++)
struct KingdomXCitiesandVillages
{
    bool seen[51][51][51];
    double mem[61][51][51];
    //memoized recursion that finds the probability to pick
    //a village i given some conditions:
    // good: Amount of villages that can be picked
    //       before the village i.
    // bad: Amount of villages that cannot be picked before i.
    // need: If need!=0, then at least one of these villages
    //       must be picked before i. They are a subset of good
    //
    double probDo(int good, int need, int bad) {
        double &res = mem[good][need][bad];
        if (! seen[good][need][bad] ) {
            seen[good][need][bad] = true;
            //total amount of vilalges available to pick:
            double n = good + bad + 1;
            if ( need == 0) {
                // pick the wanted village
                res = 1 / n;
                
                // pick a good village
                if ( good ) {
                    res += (good / n) * probDo(good-1,0,bad);
                }
            } else {
                // pick a needed village:
                res = (need / n) * probDo(good-1, 0, bad);
                // pick a good village that is not needed:
                if ( good > need ) {
                    res += ( (good-need) / n) * probDo(good-1, need, bad);
                }
            }
        }
        return res; 
    }
    double determineLength(vector <int> cityX, vector <int> cityY,
                           vector <int> villageX, vector <int> villageY)
    {
        //initialize memoization.
        memset(seen,0,sizeof(seen));
        
        int vn = villageX.size(), cn = cityX.size();

        double sum = 0;
        for (int i=vn; i--;) {
            long long d2city = numeric_limits<long long>::max();
            for (int j=cn; j--;) {
                long long dx,dy;
                dx = cityX[j] - villageX[i];
                dy = cityY[j] - villageY[i];
                d2city = std::min(d2city, dx*dx + dy*dy);
            }
            set<long long> pick;
            pick.insert(d2city);
            long long d2[vn];
            for (int j=vn; j--;) {
                long long dx,dy;
                dx = villageX[j] - villageX[i];
                dy = villageY[j] - villageY[i];
                d2[j] = dx*dx + dy*dy;
                if ( j != i) {
                    pick.insert(d2[j]);
                }
            }
            double villageExpected = 0.0;
            // = sum( X * prob_X )
            for_each(p, pick) { //iterate through all possible X
                //We are using a std::set in this case to
                //avoid checking a X twice. You can use whatever is
                //most  comfortable for you.
                long long x = *p;
                double prob;
                //Find the probability x was the minimum distance:
                if ( *p > d2city ) {
                    prob = 0;
                } else if (*p == d2city ) {
                    // number of villages with
                    // a distance greater than or equal to d2city
                    int c = 0;
                    for (int j=vn; j--;) {
                        if ( i!= j ) {
                            if (d2[j] >= d2city ) {
                                c++;
                            }
                        }
                    }
                    // probability only a subset of the c
                    // villages are picked before j
                    prob = probDo(c,0,vn-1-c);
                } else {
                    // number of villages with
                    // a distance greater than x
                    int cg = 0;
                    // number of villages with
                    // a distance equal to x
                    int ce = 0;
                    for (int j=vn; j--;) {
                        if ( i!= j ) {
                            if (d2[j] == x ) {
                                ce++;
                            } else if (d2[j] > x) {
                                cg++;
                            }
                        }
                    }
                    // probability at least one of the
                    // ce villages is picked and only
                    // villages of cg and ce are picked
                    prob = probDo(cg+ce, ce, vn-1-cg-ce);
                    
                }
                villageExpected += (prob * sqrt(x) );
            }
            sum += villageExpected;
        }
        return sum;
    }
};