These are the notes for Competitive Programming episode 14. An original problem, Repair Queue, asks in which order one technician should repair phones so that the owners lose as little money as possible. Two natural greedy rules (shortest repair first, biggest loss first) both give the wrong answer. Trying every order is correct but needs n! orders (TLE). A stress test finds a two-phone counterexample, and looking at just two neighbouring jobs gives the exchange argument: swap them, only they change, compare the two costs. That inequality becomes a comparator, and one sort solves the problem in O(n log n). 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: Raju's repair shop
Raju is the only technician at a phone repair shop and repairs one phone at a time. Three phones arrive together: one needs 1 minute (its owner, a delivery rider, loses ₹6 a minute without it), one needs 7 minutes (a student, ₹1 a minute), one needs 9 minutes (a shopkeeper, ₹7 a minute). In what order should he repair them so the total money lost is smallest?
The problem: Repair Queue
Problem N · Repair Queue (written for this course). There are
nphones and one technician. Phoneineedst[i]minutes of work, and its owner losesw[i]rupees for every minute until it is ready. LetC[i]be the minute phoneiis finished. Choose the order of repairs that minimises
Σ w[i] · C[i]
1 ≤ n ≤ 2·10^5,1 ≤ t[i], w[i] ≤ 10^4. Print the minimum total loss.
| Sample input | Sample output |
|---|---|
31 67 19 7 |
93 |
Best order: the 1-minute phone (finishes at 1, costs 6), then the 9-minute phone (finishes at 10, costs 70), then the 7-minute phone (finishes at 17, costs 17): 6 + 70 + 17 = 93.
Greedy: what it is
A greedy algorithm builds the answer step by step, always taking the choice that looks best right now by one simple rule, and never goes back to change it. Greedy solutions are short and fast, but a greedy rule is only a guess until it is proved.
Guess 1: shortest repair first (Wrong Answer)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll cost(vector<int>& ord, vector<ll>& t, vector<ll>& w) {
ll T = 0, s = 0;
for (int i : ord) {
T += t[i];
s += w[i] * T;
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> t(n), w(n);
for (int i = 0; i < n; i++) cin >> t[i] >> w[i];
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) {
return t[a] < t[b];
});
cout << cost(ord, t, w) << "\n";
return 0;
}
Output on the sample:
133
Guess 2: biggest loss first (Wrong Answer)
Change the comparator to return w[a] > w[b];. Output on the sample:
140
Shortest-first ignores how much each owner loses; biggest-loss-first ignores how long each repair blocks everyone behind it.
Brute force: try every order (correct, but TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll cost(vector<int>& ord, vector<ll>& t, vector<ll>& w) {
ll T = 0, s = 0;
for (int i : ord) {
T += t[i];
s += w[i] * T;
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> t(n), w(n);
for (int i = 0; i < n; i++) cin >> t[i] >> w[i];
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
ll best = LLONG_MAX;
do {
best = min(best, cost(ord, t, w));
} while (next_permutation(ord.begin(), ord.end()));
cout << best << "\n";
return 0;
}
next_permutation steps through every ordering of the phone numbers (they start sorted, 0 1 2 …, which is what iota gives). On the sample it prints 93. On 13 phones there are 13! = 6,227,020,800 orders: Time Limit Exceeded in the SyntaxPilot compiler (run locally it needed more than 20 seconds and printed 1069).
13-phone input:
13
5 2
3 9
8 1
2 2
7 6
4 4
9 3
1 8
6 5
3 3
8 7
2 9
5 1
Stress test: find a tiny counterexample
The brute force is slow but always right, so it can act as a judge. A stress test (episode 5) generates random small inputs, runs the brute force and the candidate solution, and stops at the first difference.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll cost(vector<int>& ord, vector<ll>& t, vector<ll>& w) {
ll T = 0, s = 0;
for (int i : ord) {
T += t[i];
s += w[i] * T;
}
return s;
}
int main() {
mt19937 rng(1);
for (int it = 1; it <= 1000; it++) {
int n = rng() % 6 + 1;
vector<ll> t(n), w(n);
for (int i = 0; i < n; i++) {
t[i] = rng() % 10 + 1;
w[i] = rng() % 10 + 1;
}
vector<int> o(n);
iota(o.begin(), o.end(), 0);
ll best = LLONG_MAX;
do best = min(best, cost(o, t, w));
while (next_permutation(o.begin(), o.end()));
sort(o.begin(), o.end(), [&](int a, int b) {
return t[a] < t[b];
});
ll g = cost(o, t, w);
if (best != g) {
cout << "test " << it << " FAILS\n";
for (int i = 0; i < n; i++)
cout << t[i] << " " << w[i] << "\n";
cout << best << " vs " << g << "\n";
return 0;
}
}
cout << "all 1000 tests passed\n";
return 0;
}
Real output:
test 1 FAILS
10 5
9 4
126 vs 131
Two phones are enough to break shortest-first: the 9-minute phone (weight 4) before the 10-minute phone (weight 5) costs 36 + 95 = 131; the other order costs 50 + 76 = 126.
The key observation: swap two neighbours (the exchange argument)
Take two phones i and j that are next to each other in the order. Swapping them does not change anyone else's finish time: everything before them is the same, and the two together take t[i] + t[j] minutes either way, so everything after them is the same too. Only the two of them change:
| Order | Extra waiting | Extra cost |
|---|---|---|
i then j |
j waits t[i] extra minutes |
w[j] · t[i] |
j then i |
i waits t[j] extra minutes |
w[i] · t[j] |
So i should go first exactly when
t[i] · w[j] < t[j] · w[i] (the same as t[i] / w[i] < t[j] / w[j]: minutes of work per rupee of loss, smallest first).
Proof (exchange argument). Take any optimal order. If some pair of neighbours breaks the rule, swap them: by the table above the total does not increase. Each such swap fixes one out-of-order pair, so after finitely many swaps we reach the sorted order, still with the optimal total. Therefore the sorted order is optimal. Ties (equal t·w products) cost the same in either order, so any tie order is fine.
Check on the sample: ratios 1/6 ≈ 0.17, 9/7 ≈ 1.29, 7/1 = 7, so the order is 1-minute, 9-minute, 7-minute phone: exactly the order the brute force found.
Real-life picture: two neighbours in a ticket queue swap places; everyone in front and behind waits exactly as long as before, so only those two people's costs need to be compared.
The accepted solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll cost(vector<int>& ord, vector<ll>& t, vector<ll>& w) {
ll T = 0, s = 0;
for (int i : ord) {
T += t[i];
s += w[i] * T;
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> t(n), w(n);
for (int i = 0; i < n; i++) cin >> t[i] >> w[i];
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) {
return t[a] * w[b] < t[b] * w[a];
});
cout << cost(ord, t, w) << "\n";
return 0;
}
| Input | Output |
|---|---|
| sample | 93 |
| the 13 phones above | 1069 (instantly; the brute force agrees) |
110000 10000 (one phone, maximum values) |
100000000 |
32 41 23 6 (all ratios equal) |
50 |
29 410 5 (the stress-test counterexample) |
126 |
2·10^5 phones of 10000 10000 |
2000010000000000000 |
The stress test with this comparator prints all 1000 tests passed.
Trap: integer division in the comparator (real output)
return t[a] / w[a] < t[b] / w[b];
On the input 29 410 5 it prints 131 (expected 126): 9/4 and 10/5 are both 2 in integer division, so the sort sees a tie and keeps the wrong order. Cross-multiply instead: t[a] * w[b] < t[b] * w[a] (at most 10^8, exact in long long).
Solutions in C++, Java and Python
C++: the accepted program above.
Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
int n = nextInt(in);
long[] t = new long[n], w = new long[n];
for (int i = 0; i < n; i++) {
t[i] = nextInt(in);
w[i] = nextInt(in);
}
Integer[] ord = new Integer[n];
for (int i = 0; i < n; i++) ord[i] = i;
Arrays.sort(ord, (a, b) -> Long.compare(t[a] * w[b], t[b] * w[a]));
long T = 0, s = 0;
for (int i : ord) {
T += t[i];
s += w[i] * T;
}
System.out.println(s);
}
static int nextInt(DataInputStream in) throws IOException {
int r = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') {
r = r * 10 + (b - '0');
b = in.read();
}
return r;
}
}
Python
import sys
from functools import cmp_to_key
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
t = list(map(int, data[1:2 * n + 1:2]))
w = list(map(int, data[2:2 * n + 2:2]))
def cmp(a, b):
x, y = t[a] * w[b], t[b] * w[a]
return -1 if x < y else (1 if x > y else 0)
order = sorted(range(n), key=cmp_to_key(cmp))
T = s = 0
for i in order:
T += t[i]
s += w[i] * T
print(s)
main()
All three print 93 on the sample, 1069 on the 13 phones, 50 on the ties input and 2000010000000000000 on 2·10^5 phones of 10000 10000.
Brute force vs optimal
| Shortest / biggest first | All orders (next_permutation) |
Exchange-argument sort | |
|---|---|---|---|
| Time | O(n log n) | O(n! · n) | O(n log n) |
| n = 13 | instant | 6.2·10^9 orders: TLE | instant |
| n = 2·10^5 | instant | impossible | ≈ 3.5·10^6 comparisons |
| Correct? | no (133 / 140) | yes | yes (proved + stress-tested) |
| Memory | O(n) | O(n) | O(n) |
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Sort by t only, or by w only |
133 / 140 instead of 93 |
a rule that feels right, never checked | stress test + exchange argument |
t[a] / w[a] < t[b] / w[b] |
131 instead of 126 |
integer division: 9/4 = 10/5 = 2 | t[a] * w[b] < t[b] * w[a] |
t[a] * w[b] <= t[b] * w[a] |
Segmentation fault (2·10^5 equal phones) |
<= breaks strict weak ordering; std::sort runs past the array |
strict < |
Total in int |
-1657102336 (correct: 2000010000000000000) |
the answer reaches about 2·10^18 | long long (up to about 9.2·10^18) |
The greedy recipe for contests
- Guess a rule (usually "sort by something").
- Try to break it: brute force + stress test on tiny inputs. Most wrong greedy ideas die here.
- Prove it: swap two neighbours and compare the two costs.
- Turn the inequality into a comparator: multiply, don't divide; keep it strict.
- If swapping two neighbours changes things far away, the exchange argument doesn't apply, and greedy may be wrong: think dynamic programming.
Mini project: minimise the worst lateness
Each job has a time t[i] and a deadline d[i]; lateness is max(0, C[i] − d[i]). Minimise the largest lateness. Exchange argument: for neighbours i, j with d[i] ≤ d[j], putting i first never makes the worse of the two latenesses bigger, so sort by deadline (earliest deadline first).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<pair<ll, ll>> job(n); // (deadline, time)
for (auto& [d, t] : job) cin >> t >> d;
sort(job.begin(), job.end());
ll T = 0, worst = 0;
for (auto [d, t] : job) {
T += t;
worst = max(worst, T - d);
}
cout << worst << "\n";
return 0;
}
Input 3 / 3 5 / 2 2 / 4 6 (each line t d) prints 3: deadlines 2, 5, 6 finish at 2, 5, 9, so the worst lateness is 9 − 6 = 3.
Practice
-
All weights are 1 (minimise
Σ C[i]). Which order is best? Prove it.Answer
Shortest first. With <code>w = 1</code> the rule <code>t[i]·w[j] < t[j]·w[i]</code> becomes <code>t[i] < t[j]</code>. For times 3, 1, 2 the best total is <code>10</code> (1, 2, 3 → finish times 1, 3, 6). -
Phone A (t = 4, w = 2) and phone B (t = 3, w = 1). Which first?
Answer
A: 4·1 = 4 < 3·2 = 6. A first costs 8 + 7 = 15; B first costs 3 + 14 = 17. -
Why does the comparator use multiplication instead of
doubledivision?Answer
Products of integers are exact (at most 10^8 here). Integer division truncates (<code>9/4 = 2</code>), and doubles can round two different ratios to the same value on bigger inputs. -
Why does swapping two neighbours not change the other phones' costs?
Answer
Phones before them are untouched, and the pair together still takes <code>t[i] + t[j]</code> minutes, so every phone after them finishes at the same minute as before. -
Stress-test the integer-division comparator: what is the smallest counterexample?
Answer
Two phones whose ratios differ but truncate to the same integer, in the wrong input order, e.g. <code>2</code> / <code>9 4</code> / <code>10 5</code> → 131 instead of 126. (Even <code>2</code> / <code>3 2</code> / <code>2 2</code> fails: 3/2 = 1 = 2/2.)
Quick quiz
Phone A: t = 4, w = 2; phone B: t = 3, w = 1. Which goes first?
A) B: it is shorter · B) A: 4·1 < 3·2 · C) Either: same cost · D) B: 3·2 < 4·1
Answer
B. A goes first iff t[A]·w[B] < t[B]·w[A]: 4 < 6. Total 15 instead of 17.
Interview questions
- What is a greedy algorithm? One that builds the answer with a fixed local rule and never revisits a choice.
- How do you prove a greedy is correct? Exchange argument: take any optimal solution, swap a pair that disagrees with the greedy, show it's not worse; repeat until it matches the greedy. (The other common style is "greedy stays ahead".)
- Weighted completion time on one machine? Sort by
t/wascending (Smith's rule), compared ast[i]·w[j] < t[j]·w[i]. - Why must a comparator be strict?
std::sortrequires a strict weak ordering;<=can make it read past the array and crash. - How do you test a greedy quickly in a contest? A brute force on tiny inputs plus a random stress test.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Greedy algorithm | Builds the answer step by step with one simple rule, never undoes a choice | shortest repair first |
| Exchange argument | Proof: swap two neighbours that break the rule; the answer never gets worse | w[j]·t[i] vs w[i]·t[j] |
Weight w[i] |
How much one minute of waiting costs for job i |
₹6 per minute |
Finish time C[i] |
The minute job i is done |
10 for the 9-minute phone |
| Weighted completion time | Σ w[i] · C[i] |
93 on the sample |
| Counterexample | An input where a solution gives the wrong answer | 9 4 / 10 5 |
| Stress test | Random small inputs, brute force vs fast solution, stop at the first difference | mt19937 rng(1) |
next_permutation |
Rearranges a range into the next order; returns false after the last | all 3! orders |
iota |
Fills a range with 0, 1, 2, … | phone numbers |
| Comparator | A function telling sort whether a goes before b |
t[a] * w[b] < t[b] * w[a] |
| Strict weak ordering | The rules a comparator must follow; in particular comp(a, a) is false |
<, never <= |
| Cross-multiplication | Comparing a/b < c/d as a·d < c·b (for positive b, d) |
t[i]·w[j] < t[j]·w[i] |
long long |
64-bit integer, up to about 9.2·10^18 | the total loss |
| Segmentation fault | The program touched memory it doesn't own and was killed | <= comparator |
Summary
- Greedy = one rule, never undo. Shortest-first gave
133, biggest-loss-first140; the answer is93. - Trying all orders is right but n!: 13 phones already TLE.
- A stress test found a 2-phone counterexample:
126 vs 131. - Exchange argument: swapping neighbours only affects them;
ifirst ifft[i]·w[j] < t[j]·w[i]. - Sort with that comparator: O(n log n), passes the stress test. Multiply, don't divide; strict
<;long longtotal.
Next episode: constructive problems: build any valid answer.