These are the notes for Competitive Programming episode 42, the second part of the DP optimisation block. Last time the minimum ran over a sliding window. This time the cost of a transition multiplies something about i with something about j, and a window cannot help. Arjun rides auto-rickshaws along a highway: every stop has an auto with a booking fee F and its own rate per kilometre, and the rates never go up towards the city. An original problem, Auto Hops, asks for the cheapest way to reach the last stop. Switching greedily whenever the rate drops prints 113 instead of 104. The O(n²) DP is right but gets TLE at n = 10^6. One line of algebra rewrites every earlier stop j as a straight line y = r[j]·x + (dp[j] − r[j]·x[j]), so dp[i] = F + the lowest line at x[i]. Because the slopes arrive in decreasing order and the queries x[i] only grow, a deque keeps the lower envelope in O(n) total: the convex hull trick. 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 real-life hook
Arjun lives in a village on a highway and wants to reach the city. Along the highway there are n stops; stop j is at kilometre x[j]. At every stop there is an auto-rickshaw stand. Booking an auto costs a fixed fee ₹F, and then that auto charges its own rate ₹r[j] per kilometre for as far as you ride it. Closer to the city there is more competition, so the rates never go up. Arjun may get off at any stop and book a new auto. A lower rate saves money per kilometre, but every switch costs F again.
You have solved the same kind of question when choosing a phone data plan: each plan is a fixed monthly fee plus a rate per GB, so the bill is rate · GB + fee, a straight line. Light users pick a small fee, heavy users pick a low rate, and the cheapest plan at each usage traces the lowest edge of all the lines.
Problem S · Auto Hops
(Written for this course, in the style of an AtCoder Beginner Contest problem.)
Stops 0 … n−1 lie at kilometres x[0] = 0 < x[1] < … < x[n−1]. A ride that books the auto at stop j and gets off at a later stop i costs F + r[j] · (x[i] − x[j]). The rates never increase: r[0] ≥ r[1] ≥ … ≥ r[n−1]. Print the cheapest total cost to travel from stop 0 to stop n−1.
- Input: n and F, then x[0 … n−1], then r[0 … n−1].
- Constraints: 1 ≤ n ≤ 10^6, 0 ≤ x ≤ 10^9, 1 ≤ r ≤ 10^6, 0 ≤ F ≤ 10^9.
- Output: one integer (it can exceed 2^31: use
long long).
| Input | Output | Note |
|---|---|---|
5 10 / 0 3 4 10 20 / 9 8 3 2 1 |
104 |
sample 1 (S1) |
1 5 / 0 / 7 |
0 |
one stop: you are already there (EDGE) |
9 19 / 0 9 18 23 25 26 30 36 39 / 20 15 14 12 9 8 4 3 2 |
577 |
the input that catches the division bug (S779) |
For sample 1 the best plan rides the first auto (rate 9) to stop 2: 10 + 9 · 4 = 46, then the rate-3 auto to the end: 10 + 3 · 16 = 58. Total 104.
Attempt 1: switch whenever the rate drops (Wrong Answer)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
ll F;
cin >> n >> F;
vector<ll> x(n), r(n);
for (ll &v : x) cin >> v;
for (ll &v : r) cin >> v;
ll cost = F; // hire at stop 0
int cur = 0;
for (int i = 1; i < n; i++) {
cost += r[cur] * (x[i] - x[i - 1]);
if (i < n - 1 && r[i] < r[cur]) { // cheaper rate? switch!
cost += F;
cur = i;
}
}
cout << cost << "\n";
return 0;
}
Sample 1 prints 113 (expected 104). It paid the fee four times, at stops 0, 1, 2 and 3: each switch saved a little per kilometre but cost a whole F. The greedy also has a second bug: the single-stop input 1 5 / 0 / 7 prints 5 (expected 0), because it books an auto before checking that there is anywhere to go. A greedy that only looks at the rate ignores the fee; we need to compare whole plans.
Attempt 2: the O(n²) DP (correct, Time Limit Exceeded)
dp[i] = the cheapest way to reach stop i. The last ride into stop i was booked at some earlier stop j, so try every j:
dp[0] = 0, dp[i] = min over j < i of ( dp[j] + F + r[j] · (x[i] − x[j]) )
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
ll F;
cin >> n >> F;
vector<ll> x(n), r(n);
for (ll &v : x) cin >> v;
for (ll &v : r) cin >> v;
vector<ll> dp(n, LLONG_MAX); // dp[i] = cheapest way to reach stop i
dp[0] = 0;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++) // last ride: from j to i
dp[i] = min(dp[i], dp[j] + F + r[j] * (x[i] - x[j]));
cout << dp[n - 1] << "\n";
return 0;
}
| Input | Output |
|---|---|
| S1 | 104 |
| EDGE | 0 |
| S779 | 577 |
Correct. Now the worst case, n = 10^6, built inside the program (x[i] = 1000·i, r[i] = 10^6 − i, F = 10^9):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 1000000; // worst case, built here
ll F = 1000000000;
vector<ll> x(n), r(n);
for (int i = 0; i < n; i++) { x[i] = 1000LL * i; r[i] = 1000000 - i; }
vector<ll> dp(n, LLONG_MAX);
dp[0] = 0;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
dp[i] = min(dp[i], dp[j] + F + r[j] * (x[i] - x[j]));
cout << dp[n - 1] << "\n";
return 0;
}
It was still running after 10 seconds and had to be killed: Time Limit Exceeded. The double loop does n²/2 = 5 · 10^11 transitions. The DP is right; the transition is too slow.
Step 1: every earlier stop is a line
Multiply one transition out:
dp[j] + F + r[j] · (x[i] − x[j]) = F + r[j] · x[i] + (dp[j] − r[j] · x[j])
Last episode we could pull the i-part out of the min. Here we cannot: r[j] · x[i] mixes i and j. But look at the shape. Once stop j is known, r[j] is a fixed number: call it the slope m. The bracket dp[j] − r[j]·x[j] is fixed too: call it the intercept b. Only x[i] changes from query to query. So
stop j is the line y = m·x + b with m = r[j], b = dp[j] − r[j]·x[j] dp[i] = F + (the lowest line at x = x[i])
Every earlier stop j is a line, every stop i is a query at the point x[i]. In phone-plan language: the earlier stops are the plans, x[i] is the usage, and dp[i] − F is the cheapest bill.
The four lines of sample 1
dp = 0, 37, 46, 74, 104 for stops 0 … 4, which gives these lines (stop 4's line, x + 84, is never queried):
| Stop j | dp[j] | Line m·x + b |
|---|---|---|
| 0 | 0 | 9x |
| 1 | 37 | 8x + 13 |
| 2 | 46 | 3x + 34 |
| 3 | 74 | 2x + 54 |
Each query asks for the lowest of the lines that exist so far:
| Query x[i] | 9x | 8x + 13 | 3x + 34 | 2x + 54 | Lowest | dp[i] = F + lowest |
|---|---|---|---|---|---|---|
| x[1] = 3 | 27 | – | – | – | 9x | 37 |
| x[2] = 4 | 36 | 45 | – | – | 9x | 46 |
| x[3] = 10 | 90 | 93 | 64 | – | 3x + 34 | 74 |
| x[4] = 20 | 180 | 173 | 94 | 94 | tie: 3x + 34 and 2x + 54 | 104 |
Two things to notice. Stop 1's line 8x + 13 is never the lowest: it crosses 9x at x = 13, but 3x + 34 has already gone below 9x at x = 34/6 ≈ 5.67. And the steep line 9x is lowest only for small x: once the queries pass 5.67 it is beaten forever, because the queries only move right.
Step 2: the lower envelope
If you draw all the lines, the lowest value at each x traces a broken line made of pieces of some of the lines: the lower envelope. It is the lower boundary of the convex hull of the lines, which gives the trick its name. Going from left to right, the envelope uses lines with decreasing slopes (steep lines win for small x, flat lines win for large x).
Two promises of this problem make the envelope cheap to maintain:
- Slopes arrive in decreasing order (rates never go up), so each new line is the flattest so far and belongs at the right end of the envelope.
- Queries only increase (stops go along the road), so a line that is beaten at the front is beaten for good.
Keep the envelope in a deque, steepest line at the front:
- Query x: while the second line is at least as low as the first at x,
pop_front. Then read the front line. - Add a line l3: while the last line l2 has become useless (test below, with l1 = the line before it),
pop_back. Thenpush_back(l3).
The same pattern as the monotonic queue: every line is pushed once and popped at most once, so the total work is O(n), amortised O(1) per stop.
Trace on sample 1 (lines named by their stop):
| i | x[i] | pop_front | line used | dp[i] | pop_back | deque after push |
|---|---|---|---|---|---|---|
| 1 | 3 | – | 0 | 37 | – | 0, 1 |
| 2 | 4 | – | 0 | 46 | 1 | 0, 2 |
| 3 | 10 | 0 | 2 | 74 | – | 2, 3 |
| 4 | 20 | 2 (tie: 94 ≤ 94) | 3 | 104 | – | 3, 4 |
Step 3: when is the middle line useless? (bad(), cross-multiplied)
Take the last two lines on the deque, l1 then l2, and the new line l3, with slopes m1 > m2 > m3. Line l2 can only be the lowest on the stretch after it crosses l1 and before l3 takes over. If l3 crosses l1 at or before the point where l2 crosses l1, that stretch is empty and l2 is never the lowest.
Two lines cross where m1·x + b1 = m2·x + b2, that is at x = (b2 − b1) / (m1 − m2). So l2 is useless when
(b3 − b1) / (m1 − m3) ≤ (b2 − b1) / (m1 − m2)
Both denominators are positive (m1 > m2 and m1 > m3), so multiply both sides by them without flipping the sign: cross-multiplication.
(b3 − b1) · (m1 − m2) ≤ (b2 − b1) · (m1 − m3)
No division, no rounding, and no division by zero when two slopes are equal (equal rates are allowed). With m2 = m3 the test becomes b3 ≤ b2: a parallel line that is at least as low replaces the old one, which is exactly right.
Why __int128? dp reaches about F·n + r·x ≈ 10^15 + 10^15, and r·x reaches 10^15, so intercepts and their differences are around 10^15. A slope difference can be up to 10^6. The product is around 10^21, far above the long long limit of 9.22 · 10^18. g++ has a 128-bit integer type, __int128 (limit about 1.7 · 10^38), so cast one factor of each product to it. Here is the long long version of the test:
struct Line { ll m, b; ll at(ll x) const { return m * x + b; } };
// l2 is useless if l3 crosses l1 no later than l2 does
bool bad(Line l1, Line l2, Line l3) {
return (l3.b - l1.b) * (l1.m - l2.m)
<= (l2.b - l1.b) * (l1.m - l3.m);
}
On the input 5 578854154 / 0 162574135 174629359 288178837 288180293 / 985670 831177 426737 173789 102042, compiling with the undefined-behaviour sanitizer (-fsanitize=signed-integer-overflow) prints, for real:
FAST_LL.cpp:8:26: runtime error: signed integer overflow: 93571279089789 * 252948 cannot be represented in type 'long long int'
FAST_LL.cpp:9:26: runtime error: signed integer overflow: 72894839315630 * 324695 cannot be represented in type 'long long int'
218722594048918
The final answer happened to come out right on this input (and in our random tests), but signed overflow is undefined behaviour: the comparison is done on garbage and the compiler may assume it never happens. Do not rely on luck; use __int128.
The accepted solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line { ll m, b; ll at(ll x) const { return m * x + b; } };
// l2 is useless if l3 crosses l1 no later than l2 does
bool bad(Line l1, Line l2, Line l3) {
return (__int128)(l3.b - l1.b) * (l1.m - l2.m)
<= (__int128)(l2.b - l1.b) * (l1.m - l3.m);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll F;
cin >> n >> F;
vector<ll> x(n), r(n);
for (ll &v : x) cin >> v;
for (ll &v : r) cin >> v;
vector<ll> dp(n, 0); // dp[0] = 0
deque<Line> hull; // the lower envelope, slopes decreasing
hull.push_back({r[0], dp[0] - r[0] * x[0]});
for (int i = 1; i < n; i++) {
while (hull.size() >= 2 && hull[1].at(x[i]) <= hull[0].at(x[i]))
hull.pop_front(); // x only grows: beaten for good
dp[i] = F + hull[0].at(x[i]);
Line nw{r[i], dp[i] - r[i] * x[i]};
while (hull.size() >= 2 && bad(hull[hull.size() - 2], hull.back(), nw))
hull.pop_back();
hull.push_back(nw);
}
cout << dp[n - 1] << "\n";
return 0;
}
| Input | Output |
|---|---|
| S1 | 104 |
| EDGE | 0 |
| S779 | 577 |
| worst case n = 10^6 (built in the program, as above) | 501414212250000 in 0.18 s |
The same worst case that ran for more than 10 s with the O(n²) DP now finishes in a fraction of a second. Reading 10^6 numbers is helped by ios::sync_with_stdio(false); cin.tie(nullptr);.
Stress test: the hull against the O(n²) DP
A thousand random small highways with non-increasing rates. Random rates from 1 to 20 for up to 10 stops produce many ties, so equal slopes are tested too.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line { ll m, b; ll at(ll x) const { return m * x + b; } };
// l2 is useless if l3 crosses l1 no later than l2 does
bool bad(Line l1, Line l2, Line l3) {
return (__int128)(l3.b - l1.b) * (l1.m - l2.m)
<= (__int128)(l2.b - l1.b) * (l1.m - l3.m);
}
ll brute(int n, ll F, vector<ll>& x, vector<ll>& r) {
vector<ll> dp(n, LLONG_MAX);
dp[0] = 0;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++) dp[i] = min(dp[i], dp[j] + F + r[j] * (x[i] - x[j]));
return dp[n - 1];
}
ll fast(int n, ll F, vector<ll>& x, vector<ll>& r) {
vector<ll> dp(n);
dp[0] = 0;
deque<Line> hull{{r[0], -r[0] * x[0]}};
for (int i = 1; i < n; i++) {
while (hull.size() >= 2 && hull[1].at(x[i]) <= hull[0].at(x[i])) hull.pop_front();
dp[i] = F + hull[0].at(x[i]);
Line nw{r[i], dp[i] - r[i] * x[i]};
while (hull.size() >= 2 && bad(hull[hull.size() - 2], hull.back(), nw)) hull.pop_back();
hull.push_back(nw);
}
return dp[n - 1];
}
int main() {
mt19937 rng(42);
for (int t = 1; t <= 1000; t++) {
int n = rng() % 10 + 1;
ll F = rng() % 30;
vector<ll> x(n), r(n);
for (int i = 1; i < n; i++) x[i] = x[i - 1] + rng() % 10 + 1;
for (ll &v : r) v = rng() % 20 + 1;
sort(r.rbegin(), r.rend()); // rates never increase
if (brute(n, F, x, r) != fast(n, F, x, r)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 1000 tests passed";
}
Output:
all 1000 tests passed
The division bug (live)
Many people write bad() with the crossing points directly, because it reads more naturally:
// where l3 crosses l1, vs where l2 crosses l1
bool bad(Line l1, Line l2, Line l3) {
return (l3.b - l1.b) / (l1.m - l3.m) <= (l2.b - l1.b) / (l1.m - l2.m);
}
Swapped into the stress test above, it crashes: Runtime Error (SIGFPE), exit code 136 (the shell's 128 + signal 8), "Floating point exception". SIGFPE here means an integer division by zero: two stops with the same rate give two lines with the same slope, and m1 − m3 is 0.
Even when all rates are different, integer division rounds towards zero, so two different crossing points can compare as equal or in the wrong order. Swapped into the full accepted program, input S779 (all nine rates different) prints 579, while the O(n²) DP and the cross-multiplied hull both print 577. Rounding kept a line that should have died and threw away a useful one. Using double instead only trades this for floating-point error at values near 10^15. Never divide in the hull test; cross-multiply.
Complexity vs the constraints
| Approach | Time | Memory | Verdict at n = 10^6 |
|---|---|---|---|
| greedy switching | O(n) | O(n) | fast, Wrong Answer (113) |
| try every j | O(n²) ≈ 5 · 10^11 | O(n) | TLE |
| Li Chao tree (any slope / query order) | O(n log n) over the n stop positions (O(n log C) over a value range of size C) | O(n) | also accepted |
| monotone hull (deque) | O(n), each line pushed and popped once | O(n) | accepted, 0.18 s |
When the order breaks: the Li Chao tree
The deque needs both promises. If the rates came in any order, a new line could belong in the middle of the envelope; if the queries came in any order, a line popped from the front might be needed again. The general tool is the Li Chao tree: a segment tree over the query positions where every node stores one line, the one that is lowest at the node's middle point.
- Add a line: at a node, compare the new line with the stored one at the middle; keep the winner there. Two lines cross at most once, so the loser can still be lowest on only one half: go into that half (the left half if the winner changes between the left end and the middle, otherwise the right half). One root-to-leaf path: O(log n).
- Query x: walk from the root to the leaf of x and take the minimum of the lines stored on the path: O(log n).
Here the query points are exactly the stop positions x[0 … n−1], already sorted, so the tree is built over the indices 0 … n−1 (no value range of 10^9 needed):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line { ll m, b; ll at(ll x) const { return m * x + b; } };
// Li Chao tree over the stop positions xs[0..n-1] (sorted): add any line, ask the lowest at xs[i]
struct LiChao {
vector<ll> xs;
vector<Line> t; // t[node] = the line that wins at the node's middle
LiChao(const vector<ll>& p) : xs(p), t(4 * p.size(), Line{0, (ll)4e18}) {}
void add(Line nw, int node, int l, int r) {
int m = (l + r) / 2;
bool winL = nw.at(xs[l]) < t[node].at(xs[l]);
bool winM = nw.at(xs[m]) < t[node].at(xs[m]);
if (winM) swap(t[node], nw); // keep the winner of the middle here
if (l == r) return;
if (winL != winM) add(nw, 2 * node, l, m); // the loser can still win on the left half...
else add(nw, 2 * node + 1, m + 1, r); // ...or on the right half, never both
}
ll query(int i, int node, int l, int r) {
ll best = t[node].at(xs[i]);
if (l == r) return best;
int m = (l + r) / 2;
if (i <= m) return min(best, query(i, 2 * node, l, m));
return min(best, query(i, 2 * node + 1, m + 1, r));
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll F;
cin >> n >> F;
vector<ll> x(n), r(n);
for (ll &v : x) cin >> v;
for (ll &v : r) cin >> v; // rates in ANY order now
LiChao lc(x);
vector<ll> dp(n, 0);
lc.add({r[0], dp[0] - r[0] * x[0]}, 1, 0, n - 1);
for (int i = 1; i < n; i++) {
dp[i] = F + lc.query(i, 1, 0, n - 1);
lc.add({r[i], dp[i] - r[i] * x[i]}, 1, 0, n - 1);
}
cout << dp[n - 1] << "\n";
return 0;
}
It prints 104, 0 and 577 on S1, EDGE and S779. With the rates shuffled, 5 10 / 0 3 4 10 20 / 5 8 9 3 7, the O(n²) DP and the Li Chao tree both print 100, while the monotone deque prints 110 (its promise is broken). A stress test against the brute force, with rates in any order:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line { ll m, b; ll at(ll x) const { return m * x + b; } };
// Li Chao tree over the stop positions xs[0..n-1] (sorted): add any line, ask the lowest at xs[i]
struct LiChao {
vector<ll> xs;
vector<Line> t; // t[node] = the line that wins at the node's middle
LiChao(const vector<ll>& p) : xs(p), t(4 * p.size(), Line{0, (ll)4e18}) {}
void add(Line nw, int node, int l, int r) {
int m = (l + r) / 2;
bool winL = nw.at(xs[l]) < t[node].at(xs[l]);
bool winM = nw.at(xs[m]) < t[node].at(xs[m]);
if (winM) swap(t[node], nw); // keep the winner of the middle here
if (l == r) return;
if (winL != winM) add(nw, 2 * node, l, m); // the loser can still win on the left half...
else add(nw, 2 * node + 1, m + 1, r); // ...or on the right half, never both
}
ll query(int i, int node, int l, int r) {
ll best = t[node].at(xs[i]);
if (l == r) return best;
int m = (l + r) / 2;
if (i <= m) return min(best, query(i, 2 * node, l, m));
return min(best, query(i, 2 * node + 1, m + 1, r));
}
};
ll brute(int n, ll F, vector<ll>& x, vector<ll>& r) {
vector<ll> dp(n, LLONG_MAX);
dp[0] = 0;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++) dp[i] = min(dp[i], dp[j] + F + r[j] * (x[i] - x[j]));
return dp[n - 1];
}
ll lichao(int n, ll F, vector<ll>& x, vector<ll>& r) {
LiChao lc(x);
vector<ll> dp(n, 0);
lc.add({r[0], -r[0] * x[0]}, 1, 0, n - 1);
for (int i = 1; i < n; i++) {
dp[i] = F + lc.query(i, 1, 0, n - 1);
lc.add({r[i], dp[i] - r[i] * x[i]}, 1, 0, n - 1);
}
return dp[n - 1];
}
int main() {
mt19937 rng(42);
for (int t = 1; t <= 1000; t++) {
int n = rng() % 10 + 1;
ll F = rng() % 30;
vector<ll> x(n), r(n);
for (int i = 1; i < n; i++) x[i] = x[i - 1] + rng() % 10 + 1;
for (ll &v : r) v = rng() % 20 + 1; // NOT sorted: any order
if (brute(n, F, x, r) != lichao(n, F, x, r)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 1000 tests passed";
}
Output:
all 1000 tests passed
(The same check with up to 200 stops and 100000 tests also printed all 100000 tests passed.) The starting line {0, 4·10^18} is "infinity": every real line is below it, and 0 · x + 4 · 10^18 cannot overflow.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| switch whenever the rate drops | 113 (expected 104) |
ignores the fee | DP over the last booking stop |
| greedy books an auto even when n = 1 | 5 (expected 0) |
pays F with nowhere to go | dp[0] = 0, answer dp[n−1] |
| try every j | Time Limit Exceeded (killed after 10 s) |
O(n²) = 5 · 10^11 | lines + hull |
crossing points with / |
Runtime Error (SIGFPE), exit code 136 |
equal slopes: ÷ 0 | cross-multiply |
integer division in bad() |
579 (expected 577) |
rounding towards zero | cross-multiply |
cross-multiply in long long |
sanitizer: signed integer overflow: 93571279089789 * 252948 |
products ~10^21 > 9.22 · 10^18 | __int128 |
| monotone deque with rates in any order | 110 (expected 100) |
new line belongs in the middle | Li Chao tree |
Mini project
Build a phone-plan advisor. Read n plans (fee, rate per GB) and q users (GB used). For each user print the cheapest plan and its bill. Version 1: sort the plans by rate, build the envelope once with the cross-multiplied bad(), and answer each user by binary search on the hull (practice 3 below). Version 2: plans and users arrive mixed in one stream ("add plan" / "ask") in any order: use a Li Chao tree over the sorted list of all usages. Add a stress test against the "try every plan" loop, and print the envelope as a list of usage ranges ("0 to 10 GB: plan C, 10 to … GB: plan B").
Practice
These are the homework questions from the video. Every answer below was compiled and run, and each solution was also checked against a brute force on 1000 random cases.
1. Maximum instead of minimum. The auto union wants the largest total a passenger could be charged, now with rates that never decrease (r[0] ≤ r[1] ≤ …).
Solution
max(m·x + b) = −min(−m·x − b). Store neg[i] = −dp[i]; then neg[i] = −F + min over j of ( −r[j]·x[i] + (neg[j] + r[j]·x[j]) ). The slopes −r[j] are non-increasing, so the same deque code works unchanged.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line { ll m, b; ll at(ll x) const { return m * x + b; } };
bool bad(Line l1, Line l2, Line l3) {
return (__int128)(l3.b - l1.b) * (l1.m - l2.m)
<= (__int128)(l2.b - l1.b) * (l1.m - l3.m);
}
int main() {
int n;
ll F;
cin >> n >> F;
vector<ll> x(n), r(n);
for (ll &v : x) cin >> v;
for (ll &v : r) cin >> v; // rates never DEcrease now
// max of (m·x + b) = −min of (−m·x − b): store neg[i] = −dp[i]
vector<ll> neg(n, 0);
deque<Line> hull; // lines −r[j]·x + (neg[j] + r[j]·x[j]), slopes decreasing
hull.push_back({-r[0], neg[0] + r[0] * x[0]});
for (int i = 1; i < n; i++) {
while (hull.size() >= 2 && hull[1].at(x[i]) <= hull[0].at(x[i]))
hull.pop_front();
neg[i] = -F + hull[0].at(x[i]);
Line nw{-r[i], neg[i] + r[i] * x[i]};
while (hull.size() >= 2 && bad(hull[hull.size() - 2], hull.back(), nw))
hull.pop_back();
hull.push_back(nw);
}
cout << -neg[n - 1] << "\n";
return 0;
}
5 10 / 0 3 4 10 20 / 1 2 3 8 9 prints 143, the same as the O(n²) max DP; 1000 random tests against that DP all agreed. (Alternatively, keep the slopes as they are and flip every comparison to build an upper envelope.)
2. Rates in any order: Li Chao tree.
Solution
Use the Li Chao program from the complexity section: add each stop's line after computing dp[i], and ask the tree at index i. O(n log n). 5 10 / 0 3 4 10 20 / 5 8 9 3 7 prints 100 (the O(n²) DP agrees; the monotone deque prints 110), and the any-order stress test prints all 1000 tests passed.
3. Queries in any order: binary search the hull. Plans are given with non-increasing rates, users' usages in any order.
Solution
Build the whole envelope first (no pop_front). On the envelope, line k is lowest between its crossing with line k−1 and its crossing with line k+1, and those crossings increase with k. So "line k+1 is not lower than line k at x" is false, false, …, true, true: binary search for the first true. O(log n) per query. Equal rates must be merged before bad() here (keep the smaller fee), because no front pops will clean them up.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line { ll m, b; ll at(ll x) const { return m * x + b; } };
bool bad(Line l1, Line l2, Line l3) {
return (__int128)(l3.b - l1.b) * (l1.m - l2.m)
<= (__int128)(l2.b - l1.b) * (l1.m - l3.m);
}
int main() {
int n, q;
cin >> n >> q;
vector<Line> hull; // plans given with rates non-increasing
for (int i = 0; i < n; i++) {
Line nw;
cin >> nw.m >> nw.b; // rate per GB, fixed fee
if (!hull.empty() && hull.back().m == nw.m) { // same rate: keep the smaller fee
if (hull.back().b <= nw.b) continue;
hull.pop_back();
}
while (hull.size() >= 2 && bad(hull[hull.size() - 2], hull.back(), nw))
hull.pop_back();
hull.push_back(nw);
}
while (q--) {
ll x;
cin >> x; // usage, in ANY order
int lo = 0, hi = (int)hull.size() - 1; // first k whose next line is not lower at x
while (lo < hi) {
int mid = (lo + hi) / 2;
if (hull[mid + 1].at(x) >= hull[mid].at(x)) hi = mid;
else lo = mid + 1;
}
cout << hull[lo].at(x) << "\n";
}
return 0;
}
The quiz plans 3 4 / 3 0 / 2 10 / 1 20 / 15 0 7 10 (C = 3x, A = 2x + 10, B = x + 20; usages 15, 0, 7, 10) print 35, 0, 21, 30. 1000 random tests against "try every plan" all agreed.
4. Print the stops where Arjun books an auto.
Solution
Give every line the id of the stop that made it. When dp[i] reads the front line, store from[i] = hull[0].id. Walk back from n−1.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line { ll m, b; int id; ll at(ll x) const { return m * x + b; } }; // id = the stop that made it
bool bad(Line l1, Line l2, Line l3) {
return (__int128)(l3.b - l1.b) * (l1.m - l2.m)
<= (__int128)(l2.b - l1.b) * (l1.m - l3.m);
}
int main() {
int n;
ll F;
cin >> n >> F;
vector<ll> x(n), r(n);
for (ll &v : x) cin >> v;
for (ll &v : r) cin >> v;
vector<ll> dp(n, 0);
vector<int> from(n, -1); // from[i] = where the last auto into stop i was booked
deque<Line> hull;
hull.push_back({r[0], dp[0] - r[0] * x[0], 0});
for (int i = 1; i < n; i++) {
while (hull.size() >= 2 && hull[1].at(x[i]) <= hull[0].at(x[i]))
hull.pop_front();
dp[i] = F + hull[0].at(x[i]);
from[i] = hull[0].id;
Line nw{r[i], dp[i] - r[i] * x[i], i};
while (hull.size() >= 2 && bad(hull[hull.size() - 2], hull.back(), nw))
hull.pop_back();
hull.push_back(nw);
}
vector<int> stops; // walk back from the last stop
for (int v = from[n - 1]; v != -1; v = from[v]) stops.push_back(v);
reverse(stops.begin(), stops.end());
cout << dp[n - 1] << "\n";
for (int s : stops) cout << s << " "; // every stop where an auto is booked
cout << "\n";
return 0;
}
| Input | Output |
|---|---|
| S1 | 104 / 0 2 3 |
| EDGE | 0 / (empty line) |
| S779 | 577 / 0 1 4 6 |
On S1 the plan 0 → 2 → 3 → 4 costs 46 + 28 + 30 = 104, a tie with 0 → 2 → 4 (46 + 58): the front pop uses <=, so on a tie it moves to the newer line. S779: 199 + 259 + 64 + 55 = 577. A checker recomputed the cost of the printed stops on 1000 random tests and it always matched the O(n²) DP.
Quick quiz
Three phone plans as lines: A: y = 2x + 10, B: y = x + 20, C: y = 3x. A heavy user needs x = 15 GB. Which plan is cheapest?
A) A · B) B · C) C · D) A and C tie
Answer
B. A = 40, B = 35, C = 45. The smallest slope wins for large x, just like the cheap autos near the city. (The binary-search program in practice 3 prints 35 for usage 15.)
Interview questions
- When does the convex hull trick apply? When the transition can be written as dp[i] = (terms of i) + min over j of ( m_j · x_i + b_j ): each j becomes a line, each i a query point.
- What makes the deque version O(n)? Slopes added in sorted order (new lines go to one end) and queries in sorted order (beaten lines leave from the other end). Each line is pushed once and popped at most once: amortised O(1).
- Derive the "useless middle line" test. l2 is useless if l3 crosses l1 no later than l2 does: (b3 − b1)/(m1 − m3) ≤ (b2 − b1)/(m1 − m2); both denominators are positive, so cross-multiply: (b3 − b1)(m1 − m2) ≤ (b2 − b1)(m1 − m3).
- Why not compute the crossing points with division? Equal slopes divide by zero (SIGFPE) and integer division rounds (here
579instead of577); doubles lose precision near 10^15. - What if the slopes or queries are not sorted? Unsorted queries with sorted slopes: binary search on the hull, O(log n) per query. Unsorted slopes: a Li Chao tree (O(log C) per add and query), or a dynamic hull kept in a balanced set.
- How big can the numbers in bad() get, and what do you do in Java? About 10^15 · 10^6 = 10^21, beyond 64 bits. C++:
__int128. Java: compare the exact 128-bit products usingMath.multiplyHighfor the high half plus the wrapped low half, orBigInteger(slower).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Transition | The formula that computes one DP state from earlier ones | dp[j] + F + rj |
| Greedy | Take the best-looking local choice and never reconsider | switch whenever the rate drops: 113 |
| Line | y = m·x + b, a straight line | stop 2 → 3x + 34 |
| Slope (m) | How fast a line rises per unit of x | r[j], the rate per km |
| Intercept (b) | The value of a line at x = 0 | dp[j] − r[j]·x[j] = 34 |
| Query | Asking for the lowest line at one x | x[i] = 10 → 64 |
| Crossing point (intersection) | The x where two lines have equal value: (b2 − b1)/(m1 − m2) | 9x and 3x + 34 cross at 34/6 ≈ 5.67 |
| Lower envelope | The minimum of all lines at every x, a broken line made of pieces | 9x, then 3x + 34, then 2x + 54 … |
| Convex hull | The smallest convex shape around a set; the lower envelope is its lower boundary | gives the trick its name |
| Convex hull trick (CHT) | Turning each earlier state into a line and answering "lowest line at x" fast | dp[i] = F + lowest line at x[i] |
| Monotone CHT | The deque version, valid when slopes and queries both arrive sorted | Auto Hops, O(n) |
| Deque | A double-ended queue: push/pop at both ends in O(1) | deque<Line> hull |
bad() |
The test "the last line on the hull can never be lowest any more" | pops stop 1's line 8x + 13 |
| Cross-multiplication | Comparing a/b ≤ c/d as a·d ≤ c·b when b, d > 0, to avoid division | (b3 − b1)(m1 − m2) ≤ (b2 − b1)(m1 − m3) |
__int128 |
g++'s 128-bit signed integer, up to about 1.7 · 10^38 | (__int128)(l3.b - l1.b) * (l1.m - l2.m) |
| Overflow / undefined behaviour | A signed result too big for its type; C++ gives no guarantee what happens | 93571279089789 * 252948 |
| UBSan | g++'s undefined-behaviour sanitizer, -fsanitize=..., reports overflow at run time |
runtime error: signed integer overflow |
| SIGFPE | The signal for an arithmetic fault; for integers, division by zero | exit code 136 |
| Amortised | Cost averaged over all operations: one step may be slow, the total is bounded | n pushes + ≤ n pops = O(n) |
| Li Chao tree | A segment tree over query positions, one line per node; add and query in O(log n) | rates in any order: 100 |
| Binary search on the hull | Finding the lowest line at any x by bisecting the envelope | practice 3: 35 0 21 30 |
| Stress test | Comparing a fast solution with a simple correct one on many random inputs | all 1000 tests passed |
| Brute force | The simple, slow, obviously correct solution | the O(n²) DP |
| Parent pointer | Storing which choice gave each state, to rebuild the plan | from[i] = hull[0].id |
Math.multiplyHigh |
Java (9+): the high 64 bits of the 128-bit product of two longs | used in the Java bad() |
| TLE | Time Limit Exceeded | the O(n²) DP at n = 10^6 |
Summary
- Greedy switching ignores the fee (
113instead of104); the O(n²) DP is right but TLE at n = 10^6. - dp[j] + F + rj = F + r[j]·x[i] + (dp[j] − r[j]·x[j]): each earlier stop is a line, dp[i] = F + the lowest line at x[i].
- Keep the lower envelope in a deque: slopes decrease → push at the back, popping useless lines with
bad(); queries increase → pop beaten lines from the front. O(n) amortised. bad(): (b3 − b1)(m1 − m2) ≤ (b2 − b1)(m1 − m3), cross-multiplied in__int128(products ~10^21).- Never divide in
bad(): SIGFPE on equal slopes,579instead of577from rounding. - Slopes or queries in any order: Li Chao tree (or binary search on the hull for unsorted queries).
Solutions in C++, Java and Python
Problem S · Auto Hops
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line { ll m, b; ll at(ll x) const { return m * x + b; } };
// l2 is useless if l3 crosses l1 no later than l2 does
bool bad(Line l1, Line l2, Line l3) {
return (__int128)(l3.b - l1.b) * (l1.m - l2.m)
<= (__int128)(l2.b - l1.b) * (l1.m - l3.m);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll F;
cin >> n >> F;
vector<ll> x(n), r(n);
for (ll &v : x) cin >> v;
for (ll &v : r) cin >> v;
vector<ll> dp(n, 0); // dp[0] = 0
deque<Line> hull; // the lower envelope, slopes decreasing
hull.push_back({r[0], dp[0] - r[0] * x[0]});
for (int i = 1; i < n; i++) {
while (hull.size() >= 2 && hull[1].at(x[i]) <= hull[0].at(x[i]))
hull.pop_front(); // x only grows: beaten for good
dp[i] = F + hull[0].at(x[i]);
Line nw{r[i], dp[i] - r[i] * x[i]};
while (hull.size() >= 2 && bad(hull[hull.size() - 2], hull.back(), nw))
hull.pop_back();
hull.push_back(nw);
}
cout << dp[n - 1] << "\n";
return 0;
}
Java (Java has no __int128. A long product of ~10^21 silently wraps, so the hull test compares the exact 128-bit products: Math.multiplyHigh(p, q) gives the high 64 bits and the ordinary p * q the low 64 bits; compare the high halves as signed numbers, then the low halves as unsigned. BigInteger would also be exact but allocates objects on every comparison, and double or long double-style tricks lose the low digits. The deque is two arrays with head and tail indices, since every line enters once.)
import java.io.*;
import java.util.*;
public class Main {
static long[] m, b; // the hull: lines m[k]·x + b[k], slopes decreasing
// sign of p·q − r·s, exact: Java has no __int128, so build each 128-bit product
// from its high half (Math.multiplyHigh) and its low half (the ordinary wrapped product)
static int cmpProducts(long p, long q, long r, long s) {
long hi1 = Math.multiplyHigh(p, q), lo1 = p * q;
long hi2 = Math.multiplyHigh(r, s), lo2 = r * s;
if (hi1 != hi2) return Long.compare(hi1, hi2); // high halves are signed
return Long.compareUnsigned(lo1, lo2); // low halves are unsigned
}
// l2 is useless if l3 crosses l1 no later than l2 does
static boolean bad(int l1, int l2, long m3, long b3) {
return cmpProducts(b3 - b[l1], m[l1] - m[l2], b[l2] - b[l1], m[l1] - m3) <= 0;
}
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
int n = (int) next(in);
long F = next(in);
long[] x = new long[n], r = new long[n];
for (int i = 0; i < n; i++) x[i] = next(in);
for (int i = 0; i < n; i++) r[i] = next(in);
long[] dp = new long[n]; // dp[0] = 0
m = new long[n];
b = new long[n];
int head = 0, tail = 0; // the deque is m[head..tail-1]: each line enters once
m[tail] = r[0]; b[tail] = dp[0] - r[0] * x[0]; tail++;
for (int i = 1; i < n; i++) {
while (tail - head >= 2 && m[head + 1] * x[i] + b[head + 1] <= m[head] * x[i] + b[head])
head++; // x only grows: beaten for good
dp[i] = F + m[head] * x[i] + b[head];
long nm = r[i], nb = dp[i] - r[i] * x[i];
while (tail - head >= 2 && bad(tail - 2, tail - 1, nm, nb))
tail--;
m[tail] = nm; b[tail] = nb; tail++;
}
System.out.println(dp[n - 1]);
}
static long next(DataInputStream in) throws IOException {
int c = in.read();
while (c != '-' && (c < '0' || c > '9')) c = in.read();
boolean neg = c == '-';
if (neg) c = in.read();
long v = 0;
while (c >= '0' && c <= '9') { v = v * 10 + (c - '0'); c = in.read(); }
return neg ? -v : v;
}
}
Python (Python integers are unbounded, so the cross-multiplication is exact with no special type. The worst case n = 10^6 takes about 2 seconds here; fine for the samples.)
import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, F = int(data[0]), int(data[1])
x = list(map(int, data[2:2 + n]))
r = list(map(int, data[2 + n:2 + 2 * n]))
def bad(l1, l2, l3): # Python ints never overflow: no __int128 needed
return (l3[1] - l1[1]) * (l1[0] - l2[0]) <= (l2[1] - l1[1]) * (l1[0] - l3[0])
dp = [0] * n
hull = deque([(r[0], dp[0] - r[0] * x[0])]) # lines (m, b), slopes decreasing
for i in range(1, n):
xi = x[i]
while len(hull) >= 2 and hull[1][0] * xi + hull[1][1] <= hull[0][0] * xi + hull[0][1]:
hull.popleft() # x only grows: beaten for good
m0, b0 = hull[0]
dp[i] = F + m0 * xi + b0
nw = (r[i], dp[i] - r[i] * xi)
while len(hull) >= 2 and bad(hull[-2], hull[-1], nw):
hull.pop()
hull.append(nw)
print(dp[n - 1])
main()
All three print 104, 0 and 577 on S1, EDGE and S779, and 501414212250000 on the n = 10^6 worst case. On 150 random tests with values at the full limits (x up to 10^9, r up to 10^6, F up to 10^9), the C++, Java and Python solutions all matched the O(n²) DP.
Next episode: DP optimisation 3: divide and conquer DP (when the best split point only moves right).