Accelerating Carrots
National Olympiad — National round
Submission name: gmo.cpp
Problem summary
Start at coordinate S on a line and reach E as quickly as possible. Initial speed is one coordinate unit per second. At each of N distinct listed coordinates there is a carrot that must be eaten on the first visit, instantly doubling the current speed. Each carrot can be eaten only once. You may travel in either direction and reverse at any time. Minimize the travel time.
Input
S E, then N, then N carrot coordinates.
Output
Minimum time with nine digits after the decimal point.
Constraints
0 ≤ N ≤ 50; all S, E and carrot coordinates are distinct integers in [0,10^9]. If |S−E|>10^6, N≥20.
Worked example
An independently prepared example for this explanation.
Input
0 10 1 4
Output
7.000000000
Solution analysis
- Sort carrots together with S. All collected carrots always form an interval around S.
- DP stores the earliest time after visiting interval [l,r] and standing at either endpoint. Its speed is 2^(r−l), since S is not a carrot.
- Expand to the next carrot on either side, charging distance divided by current speed.
- Finish directly at E when there is no uncollected carrot between the current endpoint and E.
Why it works
Between consecutive first visits to carrots, reversing without reaching a new carrot cannot help: speed is unchanged. Thus every useful move expands the collected interval at one side. The two endpoint states enumerate these possibilities, and earlier arrival at an identical state always dominates later arrival.
Watch out. This is not simply movement toward E: collecting a carrot in the opposite direction can reduce the total time.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
int main(){
int s,e,n;
cin>>s>>e>>n;
vector<int>x(n+1);
x[0]=s;
for(int i=1;i<=n;i++){
cin>>x[i];
}
sort(x.begin(),x.end());
int start=find(x.begin(),x.end(),s)-x.begin();
const double INF=1e100;
vector<vector<vector<double>>>d(n+1,vector<vector<double>>(n+1,vector<double>(2,INF)));
d[start][start][0]=d[start][start][1]=0;
double ans=INF;
for(int len=1;len<=n+1;len++){
for(int l=0;l+len<=n+1;l++){
int r=l+len-1;
if(l>start||r<start){
continue;
}
double speed=ldexp(1.0,len-1);
for(int side=0;side<2;side++){
double now=d[l][r][side];
int pos=x[side?r:l];
if(now==INF){
continue;
}
bool clear=(e>=x[l]&&e<=x[r])||(e<x[l]&&(l==0||x[l-1]<e))||
(e>x[r]&&(r==n||x[r+1]>e));
if(clear){
ans=min(ans,now+abs(double(e)-pos)/speed);
}
// Stop at E rather than continuing through it to a farther carrot.
if(l>0&&!(e>=x[l-1]&&e<=pos)){
d[l-1][r][0]=min(d[l-1][r][0],now+(pos-x[l-1])/speed);
}
if(r<n&&!(e>=pos&&e<=x[r+1])){
d[l][r+1][1]=min(d[l][r+1][1],now+(x[r+1]-pos)/speed);
}
}
}
}
cout.setf(ios::fixed);
cout.precision(9);
cout<<ans<<'\n';
}