## Tuesday, November 18, 2014

### 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;
}