These are the notes for Competitive Programming episode 12. An original problem, Meeting Point, asks where friends on a road should meet so the last one arrives as early as possible. Checking whole-number points gives the wrong answer (the best point is 2.5), and tiny steps get Time Limit Exceeded. The time function goes down, then up, like a valley: it is unimodal. There is no yes/no to binary search on, so two scouts at a third and two thirds compare heights and we drop the third beyond the higher one: ternary search. You also see two floating-point traps with real outputs, the shape where ternary search breaks (flat parts), and the integer version. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The problem: Meeting Point
Problem L · Meeting Point (written for this course).
nfriends stand on a straight road; friendiis atx[i]and walksv[i]metres per second. They choose a meeting pointp(any real number) and all start walking at once. Minimise the time when the last friend arrives:
f(p) = max over i of |x[i] − p| / v[i]. Print it with 6 decimals; an absolute error up to 10^-6 is accepted.
1 ≤ n ≤ 10^5,|x[i]| ≤ 10^9,1 ≤ v[i] ≤ 10^9.
| Sample input | Sample output |
|---|---|
30 110 34 2 |
2.500000 |
At p = 2.5: the friend at 0 needs 2.5 s, the friend at 10 needs 7.5 / 3 = 2.5 s, the friend at 4 needs 0.75 s.
Brute force 1: whole-number points (Wrong Answer)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<double> x, v;
double f(double p) {
double t = 0;
for (int i = 0; i < n; i++) t = max(t, fabs(x[i] - p) / v[i]);
return t;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
x.resize(n);
v.resize(n);
for (int i = 0; i < n; i++) cin >> x[i] >> v[i];
double L = *min_element(x.begin(), x.end()), R = *max_element(x.begin(), x.end());
double best = 1e18;
for (ll p = L; p <= R; p++) best = min(best, f(p));
printf("%.6f\n", best);
return 0;
}
Output on the sample:
2.666667
The best point is 2.5, between two whole numbers; the closest integer, p = 2, gives max(2, 8/3) = 2.666667.
Brute force 2: tiny steps (Time Limit Exceeded)
Stepping by 10^-6 (for (double p = L; p <= R; p += 1e-6)) prints 2.500000 on the sample. On two friends a whole road apart (-1000000000 1 and 1000000000 3) it needs 2·10^15 points and got Time Limit Exceeded in the SyntaxPilot compiler. Precise or fast: not both.
The shape: a valley
| p | 0 | 1 | 2 | 2.5 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|---|
| f(p) | 3.33 | 3.00 | 2.67 | 2.50 | 3.00 | 4.00 | 5.00 | 6.00 |
Left of 2.5 the friend at 10 is the last to arrive, and moving right helps; right of 2.5 the friend at 0 is last, and moving right hurts. Unimodal: strictly down, then strictly up, one lowest point. Each friend's time |x − p| / v is a V shape, and the maximum of V shapes (convex functions) is convex: one valley.
The idea: two scouts in a foggy valley
| In a foggy valley | In code |
|---|---|
| You can't see the floor; you can only measure where someone stands | evaluate f(p) at one point |
| Two scouts at 1/3 and 2/3 report their heights | f(m1) vs f(m2) |
| The higher scout is on a slope; the floor isn't beyond him | drop that outer third: hi = m2 or lo = m1 |
| Repeat until you're at the bottom | 100 rounds: (2/3)^100 ≈ 2.5·10^-18 |
The first rounds on the sample, searching between the friends (lo = 0, hi = 10):
| round | lo | m1 | m2 | hi | f(m1) | f(m2) | next |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 3.33 | 6.67 | 10 | 3.33 | 6.67 | hi = 6.67 |
| 2 | 0 | 2.22 | 4.44 | 6.67 | 2.59 | 4.44 | hi = 4.44 |
| 3 | 0 | 1.48 | 2.96 | 4.44 | 2.84 | 2.96 | hi = 2.96 |
| 4 | 0 | 0.99 | 1.98 | 2.96 | 3.00 | 2.68 | lo = 0.99 |
Ternary search
repeat 100 times:
m1 = lo + (hi − lo) / 3
m2 = hi − (hi − lo) / 3
if f(m1) < f(m2): hi = m2 // the minimum is not right of m2
else: lo = m1 // the minimum is not left of m1
answer = f(lo)
Each round keeps 2/3 of the range and costs two evaluations of f (each O(n)): 100 rounds = 200·n ≈ 2·10^7 steps at n = 10^5.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<double> x, v;
double f(double p) {
double t = 0;
for (int i = 0; i < n; i++) t = max(t, fabs(x[i] - p) / v[i]);
return t;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
x.resize(n);
v.resize(n);
for (int i = 0; i < n; i++) cin >> x[i] >> v[i];
double lo = -1e9, hi = 1e9;
for (int it = 0; it < 100; it++) {
double m1 = lo + (hi - lo) / 3;
double m2 = hi - (hi - lo) / 3;
if (f(m1) < f(m2)) hi = m2;
else lo = m1;
}
printf("%.6f\n", f(lo));
return 0;
}
| Input | Output |
|---|---|
| the sample | 2.500000 |
2 / -1000000000 1 / 1000000000 3 |
500000000.000000 (instantly) |
Check the second: meeting at −5·10^8, friend 1 walks 5·10^8 m at 1 m/s and friend 2 walks 1.5·10^9 m at 3 m/s: both 5·10^8 s.
Trap 1: too few rounds (real output)
With 30 rounds (it < 30) the sample prints:
3504.658854
(2/3)^30 ≈ 5·10^-6, but the range is 2·10^9 metres: about 10^4 metres of uncertainty is left. The number of rounds must depend on the range and the required precision; 100 is safe here (2·10^9 · 2.5·10^-18 ≈ 5·10^-9).
Trap 2: while (hi - lo > 1e-9) never ends (real verdict)
On the sample this version prints 2.500000. On the two-friends input it got Time Limit Exceeded. A double holds about 16 significant digits; near 5·10^8, neighbouring doubles are 2^-24 ≈ 6·10^-8 apart, so hi − lo can never drop below 10^-9 and the loop never ends. Use a fixed number of rounds with floating point.
Where it breaks: flat parts
Heights 5 5 5 1 5 5 5: both scouts can stand on the flat 5s. Equal heights say nothing, and the search may drop the third that contains the 1. Ternary search needs a strictly unimodal function (strictly down, then strictly up). Convex functions with a flat bottom are fine (the flat part is the minimum), but flat parts away from the minimum are not.
The integer version: binary search on the slope
On whole numbers, compare f(m) with f(m + 1): if f(m) < f(m + 1) we are on the rising side, so the minimum is at m or to its left (hi = m); otherwise lo = m + 1. That is episode 11's binary search with the slope as the yes/no. Example: the best tower height h minimising Σ (a[i] − h)² for a = 1 2 9:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> a = {1, 2, 9};
ll f(ll h) {
ll s = 0;
for (ll x : a) s += (x - h) * (x - h);
return s;
}
int main() {
ll lo = 0, hi = 1000000;
while (lo < hi) {
ll m = lo + (hi - lo) / 2;
if (f(m) < f(m + 1)) hi = m; // rising side: minimum is at m or left
else lo = m + 1;
}
cout << lo << " " << f(lo) << "\n";
}
Output: 4 38.
Solutions in C++, Java and Python
C++: the ternary-search program above.
Java
import java.io.*;
import java.util.*;
public class Main {
static int n;
static double[] x, v;
static double f(double p) {
double t = 0;
for (int i = 0; i < n; i++) t = Math.max(t, Math.abs(x[i] - p) / v[i]);
return t;
}
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); n = (int) st.nval;
x = new double[n];
v = new double[n];
for (int i = 0; i < n; i++) {
st.nextToken(); x[i] = st.nval;
st.nextToken(); v[i] = st.nval;
}
double lo = -1e9, hi = 1e9;
for (int it = 0; it < 100; it++) {
double m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
if (f(m1) < f(m2)) hi = m2;
else lo = m1;
}
System.out.printf("%.6f%n", f(lo));
}
}
Python
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
x = list(map(float, data[1:2 * n + 1:2]))
v = list(map(float, data[2:2 * n + 2:2]))
def f(p):
return max(abs(xi - p) / vi for xi, vi in zip(x, v))
lo, hi = -1e9, 1e9
for _ in range(100):
m1 = lo + (hi - lo) / 3
m2 = hi - (hi - lo) / 3
if f(m1) < f(m2):
hi = m2
else:
lo = m1
print(f"{f(lo):.6f}")
main()
All three print 2.500000 on the sample and 500000000.000000 on the two-friends input.
Brute force vs optimal
| Whole numbers | Steps of 10^-6 | Ternary search (100 rounds) | |
|---|---|---|---|
| Evaluations of f | up to 2·10^9 | up to 2·10^15 | 200 |
| Time at n = 10^5 | TLE | TLE | ≈ 2·10^7 |
| Correct? | no (2.666667) | yes, if it finishes | yes |
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
it < 30 |
3504.658854 instead of 2.500000 |
2·10^9 × (2/3)^30 ≈ 10^4 | 100 rounds |
while (hi - lo > 1e-9) |
Time Limit Exceeded | doubles near 5·10^8 are 6·10^-8 apart | fixed number of rounds |
| Ternary search on a function with flat parts | wrong answer | f(m1) == f(m2) says nothing |
only strictly unimodal functions |
cout << answer |
5e+08 |
default 6 significant digits | printf("%.6f\n", ...) or fixed << setprecision(6) |
| Searching only integer points | 2.666667 |
the optimum can be fractional | search over doubles |
Practice
-
Each friend also needs
t[i]seconds to get ready. Does ternary search still work?Answer
Yes. Each time is <code>t[i] + |x[i] − p| / v[i]</code>, still a V shape (shifted up), and the maximum of V shapes is still one valley. -
Integer ternary search: best
hfora = 1 2 9minimisingΣ (a[i] − h)².Answer
<code>h = 4</code>, cost <code>38</code> (real output of the program above). -
lo = 0, hi = 9, f(3) = 7, f(6) = 4. Next range?
Answer
[3, 9]: f(m1) > f(m2), so the minimum is not left of m1. -
Why can't we binary search Meeting Point directly?
Answer
Binary search needs a monotonic yes/no question. f itself goes down then up; you can binary search the <i>slope</i> (is f still decreasing at p?), which is what ternary search and the integer version effectively do. -
Find the smallest range where 30 rounds already fails the 10^-6 check.
Answer
The final uncertainty is about range × (2/3)^30 ≈ range × 5.2·10^-6, so ranges above roughly 0.2 already risk an error above 10^-6; on the sample's full road (2·10^9) it printed 3504.658854.
Quick quiz
lo = 0, hi = 9, m1 = 3, m2 = 6, f(3) = 7, f(6) = 4, f strictly unimodal. Next range?
A) [0, 6] · B) [3, 9] · C) [3, 6] · D) [0, 3]
Answer
B. The scout at 3 is higher, so he is on the falling slope: the minimum is not to his left. lo = m1 = 3.
Interview questions
- When does ternary search work? On a strictly unimodal function (strictly decreasing then strictly increasing), for example the maximum or sum of convex functions.
- Ternary vs binary search? Binary search needs a monotonic yes/no; ternary search finds the extremum of a unimodal function by comparing two inner points.
- How many iterations for doubles? Enough that range × (2/3)^k is below the required precision; a fixed count like 100 is standard.
- Why not loop until
hi − lo < eps? Doubles have limited precision; for large values the gap can't get that small, so the loop may never end. - Integer unimodal function? Binary search on
f(m) < f(m + 1).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Unimodal function | Strictly down, then strictly up (one lowest point) | f(p) on the sample |
| Convex function | Any chord lies above the graph; a single valley | |x − p| / v |
| Ternary search | Comparing f at 1/3 and 2/3 and dropping a third | 100 rounds |
m1, m2 |
The two inner points of the range | 3.33 and 6.67 |
| Plateau / flat part | A stretch where f doesn't change | 5 5 5 1 5 5 5 |
double |
64-bit floating point, about 16 significant digits | 1e9 |
| Precision | How close the printed answer must be | 10^-6 |
| Epsilon (eps) | A tiny tolerance like 10^-9 | hi − lo > 1e-9 |
fabs |
Absolute value of a double | fabs(x − p) |
printf("%.6f") |
Print a double with 6 decimals | 2.500000 |
Summary
- Whole-number points gave
2.666667(WA); tiny steps gave TLE on a 2·10^9 road. - f goes strictly down then up: unimodal (max of V shapes).
- Ternary search: m1, m2 at 1/3 and 2/3; drop the third beyond the higher one; 100 fixed rounds.
- 30 rounds printed
3504.658854;while (hi - lo > 1e-9)never ended near 5·10^8. - Flat parts break it; on integers compare
f(m)andf(m + 1).
Next episode: sorting tricks and custom comparators.