Fastest 1000 Meters: Max Average Speed from 5-Second Distance Splits
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A runner's workout is recorded as a list of integers `distances`, where `distances[i]` is the number of meters covered during the `i`-th consecutive 5-second interval. Interval `i` covers the time from second `5 * i` to second `5 * i + 5`.
Find the runner's fastest 1000 meters: the maximum average speed, in meters per second, over any continuous stretch of time during which the runner covered exactly 1000 meters.
A stretch may begin and end part-way through an interval. The original assessment required linear interpolation in that case without spelling out the details; this version fixes them as follows: within an interval the runner moves at a constant speed, so after `t` seconds of interval `i` (with `0 <= t <= 5`) the runner has covered `distances[i] * t / 5` meters of that interval.
### Function Signature
```python
def fastest_1000m_speed(distances: list[int]) -> float:
```
### Rules
- A valid stretch is a contiguous time span `[a, b]` with `0 <= a < b <= 5 * len(distances)` during which the runner covers exactly 1000 meters under the constant-speed-within-an-interval model.
- The average speed of a stretch is `1000 / (b - a)` meters per second. Intervals with 0 meters that lie inside a stretch still add their time.
- A stretch may lie entirely inside one interval when that interval alone covers at least 1000 meters.
- Return the maximum average speed over all valid stretches.
- The exact optimum is a single real number. A returned value is accepted if its relative error from the exact optimum is at most 1% (0.01), matching the tolerance of the original assessment.
### Constraints
- `1 <= len(distances) <= 10^5`
- `0 <= distances[i] <= 10^5`
- `sum(distances) >= 1000`, so at least one valid stretch always exists.
- `sum(distances)` can reach `10^10`, which exceeds `2^31 - 1`; use 64-bit or arbitrary-precision integers for running totals. All values stay well within `2^53`.
### Examples
**Example 1**
```text
Input: distances = [200, 200, 200, 200, 200]
Output: 40.0
```
The only stretch covering exactly 1000 meters is the whole 25-second run: `1000 / 25 = 40`.
**Example 2**
```text
Input: distances = [100, 400, 400, 300]
Output: 75.0
```
Intervals 1 and 2 cover 800 meters in 10 seconds. The remaining 200 meters come from the start of interval 3, where the runner moves at `300 / 5 = 60` meters per second, which takes `10/3` seconds. The stretch lasts `40/3` seconds, so the speed is `1000 / (40/3) = 75`. No other stretch is faster.
**Example 3**
```text
Input: distances = [1500]
Output: 300.0
```
The single interval is run at `1500 / 5 = 300` meters per second, so any 1000 meters inside it take `10/3` seconds: `1000 / (10/3) = 300`.
Overview: Given the meters a runner covers in each consecutive 5-second interval, find the highest average speed over any continuous stretch of exactly 1000 meters, where stretches may start or end mid-interval. Tests sliding-window reasoning, linear interpolation at boundaries and edge cases such as one interval exceeding 1000 meters.
Community answers
Answer by ishrox
public static double fastest1000mSpeed(int[] distances) {
int n = distances.length;
long[] prefix = new long[n + 1];
for (int i=0; i < n; i++) {
prefix[i+1] = prefix[i] + distances[i];
}
double minTime = Double.MAX_VALUE;
int l = 0;
for (int r = 0; r < n; r++) {
while (l <= r && prefix[r + 1] - prefix[l] >= 1000) {
long distanceBeforeR = prefix[r] - prefix[l];
double time;
if (distanceBeforeR >= 1000) {
l++;
continue;
}
time = (r-l)*5.0;
double remaining = distanceBeforeR - 1000;
double speed = distances[r] / 5.0;
if (speed > 0) {
time += remaining / speed;
minTime = Math.min(minTime, time);
}
}
l++;
}
return 1000.0/minTime;
}
Answer by vanthon256
#include
using namespace std;
double get_speed(int dis_start, int dis_end, double start, double end, double distance_in_window) {
if(distance_in_window == 1000) {
return 1000 / ((end - start + 1) * 5);
} else if(distance_in_window > 1000) {
if(dis_start > dis_end) {
return 1000 / ((end - start + 1) 5 - ((distance_in_window - 1000) / dis_end 5));
} else {
return 1000 / ((end - start + 1) 5 - ((distance_in_window - 1000) / dis_start 5));
}
} else {
return -1;
}
}
double fastest1000speed(const vector& distances) {
int start = 0;
int end = 0; // [start, end]
int distance_in_window = 0;
double min_speed = 0;
int min_time = INT_MAX;
int min_start = 0;
int min_end = 0;
for(int i = 0; i < distances.size(); i++) {
distance_in_window += distances[i];
end = i;
if(distance_in_window >= 1000) {
while(distance_in_window >= 1000) {
distance_in_window -= distances[start];
start++;
}
start--;
distance_in_window += distances[start];
if(end - start + 1 < min_time) {
min_time = end - start + 1;
min_start = start;
min_end = end;
min_speed = get_speed(distances[min_start], distances[min_end], double(min_start), double(min_end), double(distance_in_window));
} else if(end - start + 1 == min_time) {
double speed = get_speed(distances[start], distances[end], double(start), double(end), double(distance_in_window));
if(speed > min_speed) {
min_start = start;
min_end = end;
min_speed = speed;
}
}
}
}
return min_speed;
}
int main () {
vector distances = {1500};
cout << fastest1000speed(distances) << endl;
Answer by chavdi38
jh
Answer by rowerman
// 对总用时做二分查找
#include
using namespace std;
double fastest_1000m_speed(const vector& distances) {
int n = (int)distances.size();
// prefix[i] = 前 i 个完整区间覆盖的总距离
vector prefix(n + 1, 0.0L);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + (long double)distances[i];
}
long double totalTime = 5.0L * n;
// 计算从时间 0 到时间 x 累计跑过的距离
auto getDistance = & -> long double {
if (x <= 0.0L) return 0.0L;
if (x >= totalTime) return prefix[n];
int idx = (int)(x / 5.0L);
if (idx >= n) return prefix[n];
long double rem = x - 5.0L * idx;
return prefix[idx] + (long double)distances[idx] * rem / 5.0L;
};
// 判断是否存在长度为 T 的时间窗口，覆盖距离 >= 1000
auto check = & -> bool {
long double maxDist = 0.0L;
long double limit = totalTime - T;
auto consider = & {
if (a < -1e-12L || a > limit + 1e-12L) return;
if (a < 0.0L) a = 0.0L;
if (a > limit) a = limit;
long double d = getDistance(a + T) - getDistance(a);
if (d > maxDist) maxDist = d;
};
// 候选窗口起点：
// 1. a = 5 * k
// 2. a + T = 5 k，即 a = 5 k - T
for (int k = 0; k <= n; ++k) {
long double boundary = 5.0L * k;
consider(boundary);
consider(boundary - T);
}
consider(0.0L);
consider(limit);
return maxDist >= 1000.0L - 1e-9L;
};
// 二分最小耗时
long double lo = 0.0L;
long double hi = totalTime;
for (int iter = 0; iter < 80; ++iter) {
long double mid = (lo + hi) / 2.0L;
if (check(mid)) {
hi = mid;
} else {
lo = mid;
}
}
// 最大平均速度 = 距离 / 最小耗时
return (double)(1000.0L / hi);
}
int main() {
vector a = {200, 200, 200, 200, 200};
cout << fixed << setprecision(10) << fastest_