tomek takes Room 1

by lbackstrom,
TopCoder Member
Thursday, March 10, 2005

The competitors got off to a slow start on a tricky easy problem. Before long though, many of them had moved on to the medium problem. misof and tomek were the first two to submit it, and they moved on to a hard problem with plenty of time to spare. Eventually, they both submitted the third problem, and tomek had the lead over misof going into the challenge phase. ante was in third place, as the only other competitor to submit all three problems. Despite a flurry of challenges during the challenge phase, only one of them was successful, but it was significant in that it gave misof the lead over tomek going into system tests. That lead turned out to be short lived though, as only tomek's medium survived testing. In the end, tomek won as expected, and misof and ante moved on to the wildcard round.

Buoyancy

There are 4 different cases to think about. The object may be either less dense than water, or more dense than water, and it may either rest on the bottom and stick out of the water, or not. Rather than coding for each of the four cases separately though, we can solve the problem with only two cases. First, calculate the amount of water that the object can displace. This is equal to the minimum of its volume and its weight. Then, determine if the object will rest on the bottom or not, and return the appropriate value:

    double displace = objWt > objHt ? objHt : objWt;
    if(wid*len*waterHt/(wid*len-1)>displace){
        return waterHt+displace/wid/len;
    }else{
        return wid*len*waterHt/(wid*len-1);
    }

Symbolic

There were two aspects to this problem. The first thing you had to deal with was precision. The input is a string with up to 19 digits after the decimal point, and even long double in C++ won't cut it. However, the operations are fairly simple to code yourself, and you can just work with numbers as strings. Once you do that, its simply a matter of simulating the itinerary of the input. As long as the simulated itinerary agrees with the input itinerary, just continue the simulation. Once you get to the first disagreement, you need to either return -1 or 1. Which of these you return depends just on the number of 1's in the input itinerary up to an including the disagreement. If the number is 0 modulus 2, return 1, otherwise return -1. This works because when the number is 0 modulus 2, it means that a larger starting value gives a larger value at the point of disagreement.

Disaster

This problem required a combination of a graph algorithm with a little bit of calculus. The expected amount of corn delivered along a particular route is the product of the amount of corn, the goodnesses of the segments of the route, and (1-b*load)^len, where len is the number of segments in the route. We can compute the maximal goodness for a route from 0 to j of length k with some fairly simply dynamic programming:

    double[] best = new double[g.length];
    best[0] = 1;
    double ret = 0;
    for(int k = 1; k<=50; k++){
        double[] next = new double[best.length];
        for(int i = 0; i<g.length; i++){
            for(int j = 0; j<g.length; j++){
                next[j] = Math.max(next[j],best[i] * g[i][j]);
            }
        }
        best = next;
        //best holds the maximal probability for a route to each
        //vertex of length k
    }

Once we know the maximal probability of a route to city 1 of length k, we can use calculus to find the best load. The expected amount of corn delivered is:

    expected(load) = load * best[1] * (1-b*load)k

Taking the derivative of this and solving for 0 gives us the maxima. If you chug through the equations, you'll find that load = 1/(b+b*k).