Algorithm Competition Wildcard Summary

d000hgTuesday, May 13, 2008
Introduction by d000hg

Discuss this competition



tomek wins Wildcard round!


tomek wins Wildcard round!

The Wildcard play-by-play can be found here.



by lars2520

OptimalPlay

There are two sorts of decisions that the second player has to make in this problem: whether or not to call when bet at, and whether or not to raise when checked to. Imagine that the second player has card j and decided to call when bet at. We can easily calculate the expected value from this decision. When we are beat, we will lose $1. When we win, we will win $2. When we tie, we will win $0.5. Consider the case where the first player has card i, and bets this card with probability p. Card j either loses, ties or wins against card i, so we know how much we will win in this case. Now, the expected value of calling will be product of the winnings with the probability of the scenario. The probability of the scenario is just the product of the probabilities of the cards, 1/N2, with the probability that player 1 will bet, betProb[i]. If we sum this over all i, we can find the expected value of calling with card j. If we fold with card j, we neither win nor lose nothing, so we don't even have to consider this case.

If our opponent checks to us, the analysis is pretty much the same. We compute the expected value of betting and checking with each card, and pick the higher one. As in the calling case, the expected value is just the probability of each scenario, times the gain from that scenario.

double ret = 0;
for(int j = 0; j<bet.length; j++){//me
    double win1 = 0, win2 = 0, win3 = 0;
    for(int i = 0; i<bet.length; i++){//him
        if(i < j) win1 += 2 * bet[i];
        else if(i == j) win1 += bet[i] / 2;
        else win1 -= bet[i];

        if(i < j) win2 += 2*call[i];
        else if(i == j) win2 += call[i]/2;
        else win2 -= call[i];
        win2 += 1-bet[i]-call[i];

        if(i < j) win3 += 1-bet[i];
        else if(i == j)win3+= (1-bet[i])/2;
    }
    if(win1 > 0)ret += win1;//call
    if(win2 > win3) ret += win2;//bet
    else ret += win3;//check
}
return ret / bet.length / bet.length;

by ivan_metelsky

BSTConstruction

The first idea that can come to somebody's mind after reading the statement is just to implement the given pseudocode. Unfortunately, such approach can work too slow on some cases. For example imagine a case with N = 250,000 and limit = 0. It generates the permutation p = (0, 1, 2, ..., 250,000). You need to perform i steps to insert the i-th element of p into the tree, which gives totally like 250,000^2 / 2 steps. It's obviously too much. The cases with limit = 0 can be hardcoded, but there are plenty of other cases with relatively small values of limit, where the tree structure is more complex and the height is still quite large.

So we need more efficient approach to solve the problem. Let's make some helpful observations. Consider any vertex V of the tree and subtree T rooted at this vertex. Let m be the minimal integer in subtree T, M be the maximal one and R be the integer at V. The following facts are intuitively obvious and can be easily proved:

  • T contains each integer between m and M, inclusive, exactly once;
  • among all integers between m and M, inclusive, R has the smallest index in permutation p;
  • the left subtree of T contains all integers between m and R-1, inclusive;
  • the right subtree of T contains all integers between R+1 and M, inclusive.

Using these facts, we can change the process of tree construction to the following pseudocode:

Procedure construct(integer m, integer M)
    Find the value of R in the root of the tree
    If m < R then call construct(m, R-1) to get the left subtree
    If R < M then call construct(R+1, M) to get the right subtree
End

To construct the whole tree we just need to call construct(0, N - 1).

There are still 2 problems that need to be resolved. The first one is possible stack overflow. It can be resolved by replacing stack with queue. We first put the pair (0, N-1) into the queue. Then, until queue is not empty, we take a pair (m, M) from the queue, calculate R and put two (or less) pairs (m, R-1) and (R+1, M) into the queue.

The second problem is efficient calculation of R. If we check the whole permutation p each time to find R, it'll still be too slow. What can help us is the Range Minimum Query problem. Let's construct an array pos, where the i-th element gives the index of integer i in the permutation p. Now, to calculate R by m and M we need to find the smallest value minPos among pos[m], pos[m+1], ..., pos[M] and set R = p[minPos]. So each R calculation requires just one RMQ query in array pos, which allows to make it efficiently.

All problems are resolved and we can construct the whole tree in O(N * log N) time. To calculate the answer we can just keep the height during the construction and then sum all the heights. Alternatively, we can even not construct the tree itself and calculate the answer as the sum of (M - m + 1) over all tree vertices.


by ivan_metelsky

AlmostConvexPolygons

The first thing which we should do in this problem is to iterate through all subsets of given points and construct the convex hull for each subset (see the geometry tutorial for the algorithm of convex hull construction). We'll need to calculate convex hulls many times later, so it's faster to calculate them just once for each subset.

Now let's again iterate through all subsets of points and calculate for each subset how many almost convex polygons contain exactly all the vertices from this subset. To do this, we try all possible variants for diagonal, which splits the polygon into two convex polygons. Once the diagonal is fixed, we can check whether it's appropriate or not. Note that vertices of one of convex polygons must all lie to the left from the diagonal, and the vertices of the other polygon must lie to the right. So we can split the vertices into two subsets (including diagonal's endpoints into both subsets) and check whether the convex hull for each of 2 subsets contains all the vertices from the subset. If it's not true for any of subsets, the diagonal is not appropriate. Otherwise, it's appropriate and we can uniquely glue the two convex polygons we have into one almost convex.

Now we have constructed all possible almost convex polygons, but the problem is that some of them are possibly constructed more than once, so we need to remove duplicates, and it should be done quite efficiently. One possible way is to calculate the hash code for each polygon, sort all the codes to group the same codes together and then just find the number of groups. To calculate the hash code for a polygon, find the lowest-indexed vertex in it, start polygon from this vertex, proceed to the lowest-indexed of two neighbours, and then proceed to the other polygon's vertices in the chosen direction. Treating the obtained sequence of vertices as a 15-based integer and calculating its decimal value will give us the hash code for the polygon.