USACO FEB09 Problem 'cruel2' Analysis

by Rob Kolstad

This problem, which might seem intimidating at first, is really just a "half-interval search". One sets up boundaries (conveniently given in the problem), and then finds the middle of those boundaries and decides whether the middle belongs with one boundary or the other.

We know the y value signs differ and must keep choosing new boundaries so that this property continues to hold true.

The routine below includes a polynomial evaluator in the f(x) routine and the half-interval searcher (with a tighter boundary than the problem required). A cleverer xhigh/xlow routine would just check the sign of y and the signs of possible pairings. My solution (below) is simple enough, though.

#include<stdio.h>

double coef[100];
int d;

double f(x)
double x;
{
    double sum = 0.0, x2;
    int i;
    x2 = 1.0;
    for (i = 0; i <= d; i++) {
        sum += coef[i] * x2;
        x2 *= x;
    }
    return sum;
}

int main() {
    FILE *fin = fopen ("cruel2.in", "r");
    FILE *fout = fopen ("cruel2.out", "w");
    double xhigh, xlow, x, y;
    int i, reverse;
   
    fscanf (fin, "%d", &d);
    for (i = 0; i <= d; i++)
        fscanf (fin, "%lf", &coef[i]);
    xlow = -1000000.0;
    xhigh = 1000000.0;

    reverse = f (xlow) > f(xhigh);
    while (xhigh > xlow+0.0001) {
        x = (xhigh + xlow)/2.0;
        y = f(x);
        if (reverse) {
            if (y < 0)  xhigh = x;   /* y too high */
            else        xlow = x;       /* y too low */
        } else {
            if (y > 0)  xhigh = x;   /* y too high */
            else        xlow = x;       /* y too low */
        }
    }
    fprintf (fout, "%d\n", (int)(1000.0 * x));
    exit (0);
}