SyntaxPilot
Courses/Competitive Programming/Lesson 12

Competitive Programming · Lesson 12 of 90 · 10 min

Ternary search

queued

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). n friends stand on a straight road; friend i is at x[i] and walks v[i] metres per second. They choose a meeting point p (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
3
0 1
10 3
4 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
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

  1. 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.

  2. Integer ternary search: best h for a = 1 2 9 minimising Σ (a[i] − h)².

    Answer <code>h = 4</code>, cost <code>38</code> (real output of the program above).

  3. 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.

  4. 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.

  5. 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

  1. When does ternary search work? On a strictly unimodal function (strictly decreasing then strictly increasing), for example the maximum or sum of convex functions.
  2. 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.
  3. How many iterations for doubles? Enough that range × (2/3)^k is below the required precision; a fixed count like 100 is standard.
  4. 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.
  5. 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) and f(m + 1).

Next episode: sorting tricks and custom comparators.