Qanat

Introduction

Link to problem: http://speedyguy17.info/data/finals/2015/icpc2015.pdf

This problem appeared as H on the 2015 ICPC World Finals. We are given two integers 1 <= h <= w < 10000, and a number 1 <= n <= 1000

We consider the right triangle with vertices (0,0), (w,0), and (w,h), and must excavate dirt from it to form a structure known as a Qanat. This requires us to remove all of the dirt from the horizontal leg of the triangle, from the vertical leg of the triangle, and n additional vertical shafts connecting the hypotenuse of the triangle to the horizontal leg. The cost of removing a particle of dirt is equal to the arc-length of the path we transport it to the surface along. Note that the placement of the vertical shafts in the middle of the triangle shortens the path to the surface for the dirt near the middle of the horizontal leg. For an example of the cost of moving some dirt, if we are excavating a segment of dirt connected to the surface, of length l, then the total cost is the integral from 0 to l of l, which is equal to l^2/2.

We are tasked with finding the locations in which we must place the n vertical shafts, and computing the total cost of excavation.

Solutions

All in One Go

First note that we may without loss of generality the case where w is 1, and h is a double (scaled to preserve w/h), since we can just scale our positions by a factor of w to get the true positions, and scale the cost by a factor of w^2. To determine the optimal locations, we shall come up with a cost function for the dirt, given a set of well locations, a_1, ..., a_n, and minimize this. The key insight in computing this cost function is that dirt is transported to the nearest of the surface points (i.e., the tops of the vertical shafts, (0,0), or (w,h)). Thus we see the following. First we solve the situation of two vertical shafts, and the dirt between them. Call the left shaft a=x and the right shaft b=x. Then the total length is (remember that h has been rescaled) ah+bh+(b-a). Each half of the curve goes to its nearest shaft (the nearest point is the midpoint by arc-length), so we get a total cost of f(a,b) = (ah+bh+b-a)^2.

Now notice that we may, by adopting the convention a_0 = 0, a_{n+1} = w, write the total cost of the excavating a qanat with vertical shafts at a_1,...a_n as: C(a_1,...,a_n) = sum_{i=0}^{n} f(a_i,a_i+1) - sum_{i=1}^{n}(a_i h)^2/2 The subtracted sum corresponds to the fact that we double counted the cost of excavating each of the vertical shafts. We may compute the optimal shaft placement by computing the derivative of the cost function with respect to each of the shaft locations, setting the derivatives all to 0, and solving. Doing so, we get a recurrence relation between the a_i that defines our solution. We may solve this recurrence relation with a generating function, and we are done. (We omit the details here intentionally, since one only learns to use generating functions effectively after having solved a problem on their own).

Runtime

The end result is an equation for each of the a_i, and for C, so we can solve the problem in time linear in the size of the output, that is O(n).

Code

Solution - C++

/**
 * 
 * @author Created by Samadwara Reddy
 *
 */

#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

double c;

double L(double x, double y) {
    return .25 * pow(((c+1.)*y + (c-1.)*x), 2.);  
}

int main() {
    int iw, ih, in;
    scanf("%d %d %d", &iw, &ih, &in);
    double w = (double) iw;
    double h = (double) ih;
    double n = (double) in;
    c = h/w;
    double a = (1. - c*c)/2.;
    double b = pow((1./(a*a)) - 4, .5);
    double d = pow((1./a) + b, n+1.);
    double e = pow((1./a) - b, n+1.);
    double f = (d-e)/b;
    double g = f / pow(2.,n+1.);
    vector<double> locs;
    locs.push_back(0.);
    locs.push_back(w/g);
    for (int i = 2; i <= in; i++) {
        locs.push_back((locs[i-1]/a) - locs[i-2]);
    }
    locs.push_back(w);
    double total = 0.;
    for (int i = 0; i <= n; i++) {
        total += L(locs[i], locs[i+1]);
        if (i) {
            total -= .5 * L(locs[i], locs[i]);
        }
    }
    printf("%f\n", total);
    for (int i = 1; i <= min(in, 10); i++) {
        printf("%f\n", locs[i]);
    }
    return 0;
}

DP and Binary Search

We can trivially solve for one shaft by binary searching the location of the shaft. Solving for 2 shafts can then be done by binary searching the location of one shaft, where the excavation cost of the lower part of the Qanat is solved by the scaled down version of our first binary search. We just repeat this until we have enough shafts. Note that this is simply an iterative method which can be calculated explicitly as in the "All in one go" solution above. This is the medium implementation and algorithm, whereas the other is the hard algorithm with the trivial implementation.