Codeforces Round #277.5 Div. 2 - Problem E Hiking

For complete discussion to this round: link to discussion

Problem Statement:
E. Hiking

Solution:
Very interesting problem, with a very interesting solution. It requires us to realize that we can binary search the best ratio (surprise!). Now, suppose that we are given a ratio R. How do we know whether this ratio can be fulfilled? Is there a way such that our path will lead to a ratio less than or equal to R?

The relationship between R, the total picturesqueness P and the total frustration F by the time we get to point i is:
\(\frac{F}{P} \leq R\), or \(F \leq P*R\).
The important thing here is we want to maximize the "lax" \(P*R - F\) by the time we get to camp i, which is the remaining values or margin before the ratio overshoot \(R\). Hence, by the time we get to the last camp, we will end up with the maximum margin possible, and if this margin is a positive value, we can conclude that there exist a path such that the ratio between F and P is less than R. Otherwise, R cannot be satisfied.



Hence ultimately we will do a binary search on R to find the smallest R that is satisfiable.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
double EPS = 1e-12;
double rem[1003];
int x[1003], b[1003];
int par[1003];
int N, L;

bool possible(double R){
    for(int i=0;i<N;++i){
        rem[i] = R*b[i] - sqrt(fabs(.0 + L - x[i]));
        par[i] = -1;
        for(int j=i-1;j>=0;--j){
            double cost = sqrt(fabs(x[i] - x[j] - L));
            if(rem[i] < rem[j] - cost + R*b[i]) {
                rem[i] = rem[j] - cost + R*b[i];
                par[i] = j;
            }
        }
    }
    return (rem[N-1] >= 0);
}

void printout(int i){
    if(par[i] == -1){
        printf("%d", i+1);
        return;
    }
    printout(par[i]);
    printf(" %d", i+1);
}

int main(){
    scanf("%d %d", &N, &L);
    for(int i=0;i<N;++i){
        scanf("%d %d", &x[i], &b[i]);
    }
    double lo = 0, hi = 1e10, mid;
    while(lo < hi) {
        mid = (lo+hi)/2;
        if(possible(mid)) {
            hi = mid - EPS;
        } else {
            lo = mid + EPS;
        }
    }
    possible(lo);
    printout(N-1);
    printf("\n");
    return 0;
}