These are the notes for Competitive Programming episode 13. An original problem, Price Tag, asks for the largest number you can make by gluing digit stickers in some order. Sorting the stickers as numbers gives the wrong answer, sorting them as text gives a different wrong answer, and trying every order is right but gets Time Limit Exceeded at just 12 stickers. Looking at only two stickers gives the rule: put x before y when x + y > y + x. You hand that rule to sort as a custom comparator (a lambda), prove it with a stress test, learn why >= in a comparator crashes std::sort, and sort a contest scoreboard by three keys with make_tuple. 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: the shopkeeper's price stickers
A shopkeeper has a blank price tag and a box of stickers with digits on them: 3, 30, 34, 5, 9. He must glue all of them side by side, in any order, and wants the biggest price. "Biggest sticker first" gives 3430953 (about 34 lakh). The best order, 9 5 34 3 30, gives 9534330 (about 95 lakh). What rule gives that order?
The problem: Price Tag
Problem M · Price Tag (written for this course). There are
nstickers; stickeriis a string of digitsa[i]with no leading zeros. Glue all of them in some order and print the largest number you can make.
1 ≤ n ≤ 2·10^5, eacha[i]has 1 to 9 digits.
| Sample input | Sample output |
|---|---|
53 30 34 5 9 |
9534330 |
30 0 0 |
0 |
The answer can have almost 2·10^6 digits, so it is built as a string, never as an integer.
Attempt 1: biggest number first (Wrong Answer)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> a(n);
for (auto &s : a) cin >> s;
sort(a.begin(), a.end(), [](const string &x, const string &y) {
return stoll(x) > stoll(y);
});
string ans;
for (auto &s : a) ans += s;
cout << ans << "\n";
return 0;
}
Output on the sample: 3430953. 34 is the biggest number, but a 9 in front beats any 3 in front.
Attempt 2: reverse dictionary order (Wrong Answer)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> a(n);
for (auto &s : a) cin >> s;
sort(a.rbegin(), a.rend());
string ans;
for (auto &s : a) ans += s;
cout << ans << "\n";
return 0;
}
Output on the sample: 9534303 (expected 9534330). In dictionary (lexicographic) order "30" > "3", because it is longer with the same start, but 3 glued before 30 gives 330, which beats 303.
Brute force: every order (correct, but TLE)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> a(n);
for (auto &s : a) cin >> s;
sort(a.begin(), a.end());
string best;
do {
string cur;
for (auto &s : a) cur += s;
best = max(best, cur);
} while (next_permutation(a.begin(), a.end()));
cout << best << "\n";
return 0;
}
next_permutation steps through every arrangement of a sorted array. On the sample it prints 9534330 (correct). On 12 stickers (1 8 15 22 29 36 43 50 57 64 71 78) it got Time Limit Exceeded: 12! = 479,001,600 orders. Keep it anyway: it is the judge for the stress test.
The key observation: two stickers, two orders
Look at just two stickers x and y. There are only two ways to glue them: x + y or y + x (string concatenation). Both have the same length, so comparing the strings compares the numbers. Put x first if x + y > y + x.
| Pair | x + y |
y + x |
Who goes first |
|---|---|---|---|
| 3, 30 | 330 | 303 | 3 |
| 34, 3 | 343 | 334 | 34 |
| 5, 34 | 534 | 345 | 5 |
If every neighbouring pair is in this order, no single swap of neighbours can make the number bigger. (Next episode turns this "swap two neighbours" idea into a proof technique: the exchange argument.)
Custom comparators in C++
sort(first, last, cmp) takes an optional third argument, the comparator. cmp(x, y) answers one yes/no question: must x come before y?
- A lambda is a small nameless function written in place:
[](const string &x, const string &y) { return x + y > y + x; }. const string &is a const reference: the comparator looks at the strings without copying them.[&]instead of[]lets the lambda use variables from the surrounding code (for example sorting indices bya[i]).
The accepted solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> a(n);
for (auto &s : a) cin >> s;
sort(a.begin(), a.end(), [](const string &x, const string &y) {
return x + y > y + x;
});
string ans;
for (auto &s : a) ans += s;
if (ans[0] == '0') ans = "0";
cout << ans << "\n";
return 0;
}
| Input | Output |
|---|---|
5 / 3 30 34 5 9 |
9534330 |
3 / 0 0 0 |
0 (without the if (ans[0] == '0') line it printed 000) |
3 / 9 91 919 |
991991 |
Stress test: is the rule really right?
Samples passing is not a proof. The stress test (episode 5) compares the slow brute force with the fast rule on 1000 random small inputs and prints the first input where they differ. Here it is pointed at the wrong rule (return x > y;):
#include <bits/stdc++.h>
using namespace std;
string brute(vector<string> a) {
sort(a.begin(), a.end());
string best;
do {
string cur;
for (auto &s : a) cur += s;
best = max(best, cur);
} while (next_permutation(a.begin(), a.end()));
return best;
}
string fast(vector<string> a) {
sort(a.begin(), a.end(), [](const string &x, const string &y) {
return x > y;
});
string ans;
for (auto &s : a) ans += s;
return ans;
}
int main() {
mt19937 rng(42);
for (int t = 1; t <= 1000; t++) {
int n = rng() % 6 + 1;
vector<string> a(n);
for (auto &s : a) s = to_string(rng() % 100 + 1);
if (brute(a) != fast(a)) {
cout << "MISMATCH:";
for (auto &s : a) cout << " " << s;
cout << "\nbrute " << brute(a);
cout << "\nfast " << fast(a) << "\n";
return 0;
}
}
cout << "All 1000 tests passed\n";
return 0;
}
Real output:
MISMATCH: 40 100 96 10
brute 964010100
fast 964010010
With the real rule (return x + y > y + x;) the same program prints All 1000 tests passed.
The comparator rules: strict weak ordering
std::sort trusts the comparator to behave like a real ordering:
- Irreflexive:
cmp(x, x)is false. Nothing comes before itself. - Asymmetric: if
cmp(x, y)is true,cmp(y, x)is false. - Transitive:
cmp(x, y)andcmp(y, z)meancmp(x, z). - (Equal items must stay "equal" consistently.)
A comparator with these properties is a strict weak ordering. Use < or >, never <= or >=.
What >= does (real crash)
sort(a.begin(), a.end(), [](const string &x, const string &y) {
return x + y >= y + x; // WRONG: equal items answer true
});
| Input | Result |
|---|---|
16 stickers, all 7 |
7777777777777777 (looks fine) |
20 stickers, all 7 |
Segmentation fault (Runtime Error, SIGSEGV) |
Why: for 16 elements or fewer, libstdc++'s std::sort uses a guarded insertion sort. For larger arrays it uses an unguarded inner loop that walks left while cmp(item, previous) is true and trusts that something will stop it. With equal items and >=, the answer is always true, so it walks off the start of the array. Tests with tiny arrays never show this bug.
Multi-key sorting with tuples: a scoreboard
Sort teams by more problems solved, then less penalty, then name A→Z:
#include <bits/stdc++.h>
using namespace std;
struct Team {
string name;
int solved, pen;
};
int main() {
int n;
cin >> n;
vector<Team> t(n);
for (auto &x : t) cin >> x.name >> x.solved >> x.pen;
sort(t.begin(), t.end(), [](const Team &a, const Team &b) {
return make_tuple(-a.solved, a.pen, a.name)
< make_tuple(-b.solved, b.pen, b.name);
});
for (auto &x : t)
cout << x.name << " " << x.solved << " " << x.pen << "\n";
return 0;
}
Input:
4
asha 3 120
ravi 4 300
meena 3 95
dev 3 95
Real output:
ravi 4 300
dev 3 95
meena 3 95
asha 3 120
- Tuples (and pairs) compare key by key, left to right, like words in a dictionary.
- A minus sign on a number key (
-a.solved) makes that key descending. <on tuples is already a strict weak ordering, so the comparator is safe.- Other tricks:
sort(a.rbegin(), a.rend())sorts in decreasing order;stable_sortkeeps equal items in their input order; to sort indices by value,iotaan index array and sort it with[&](int i, int j) { return a[i] < a[j]; }.
Solutions in C++, Java and Python
C++: the accepted solution above.
Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String[] a = br.readLine().trim().split("\\s+");
Arrays.sort(a, (x, y) -> (y + x).compareTo(x + y));
StringBuilder sb = new StringBuilder();
for (String s : a) sb.append(s);
String ans = sb.toString();
if (ans.charAt(0) == '0') ans = "0";
System.out.println(ans);
}
}
Python
import sys
from functools import cmp_to_key
def cmp(x, y):
if x + y > y + x:
return -1 # x first
if x + y < y + x:
return 1
return 0
def main():
data = sys.stdin.read().split()
n = int(data[0])
a = data[1:n + 1]
a.sort(key=cmp_to_key(cmp))
ans = "".join(a)
if ans[0] == "0":
ans = "0"
print(ans)
main()
All three print 9534330, 0 and 991991 on the three inputs above. On 2·10^5 random stickers (up to 9 digits each) the C++ version took about 0.33 s.
Brute force vs optimal
| Every order | Comparator sort | |
|---|---|---|
| Work | n! arrangements × n | about n log n ≈ 3.5·10^6 comparisons × ≤ 18 characters |
| n = 12 | TLE (479,001,600 orders) | instant |
| n = 2·10^5 | hopeless | ≈ 0.33 s |
| Correct? | yes | yes (stress-tested) |
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
return x + y >= y + x; |
Segmentation fault (20 equal stickers) |
equal items answer true: not a strict weak ordering | > or <, never >= / <= |
sort(a.rbegin(), a.rend()) on strings |
9534303 instead of 9534330 |
"30" > "3" in dictionary order |
compare x + y with y + x |
Sorting by stoll value |
3430953 |
bigger number ≠ better first | the pair rule |
| Printing the glued string as is | 000 instead of 0 |
all stickers are zero | if (ans[0] == '0') ans = "0"; |
| Converting the answer to a number | overflow / std::out_of_range |
up to 2·10^6 digits | keep it a string |
Mini project: a contest scoreboard
Read n teams (name, solved, penalty) and print the ranking with rank numbers, giving equal ranks to teams tied on solved and penalty (1 ravi, 2 dev, 2 meena, 4 asha). Sort with the tuple comparator, then walk the sorted list and keep the previous team's (solved, penalty).
Practice
-
Make the smallest price from the stickers (now leading zeros are not allowed in the answer unless it is
0).Answer
Sort with <code>x + y < y + x</code>. Only the sticker <code>0</code> can start with a zero; if all are <code>0</code>, print <code>0</code>. Otherwise the first sticker must be non-zero: try each non-zero sticker <code>f</code> as the first one, followed by the rest in sorted order, and keep the smallest string. The tempting shortcut "move the first non-zero sticker to the front" is <b>wrong</b>: a stress test finds <code>53 0 0 5</code>, where it gives <code>53005</code> but the answer is <code>50053</code>. -
Sort points by distance from (0, 0), ties by
x, theny.Answer
<code>make_tuple(1LL*x*x + 1LL*y*y, x, y)</code> compared with <code><</code>. Use <code>long long</code> for the squared distance and avoid <code>sqrt</code>. -
What is the smallest number of equal stickers that crashes the
>=version?Answer
16 equal stickers worked and 17 crashed in our test (g++ 13, libstdc++): the switch from guarded insertion sort happens above 16 elements. -
Sort indices
0..n−1bya[i]without movinga.Answer
<code>vector<int> id(n); iota(id.begin(), id.end(), 0); sort(id.begin(), id.end(), [&](int i, int j) { return a[i] < a[j]; });</code>
Quick quiz
Stickers 9, 91, 919. What is the largest price?
A) 991919 · B) 919991 · C) 991991 · D) 999191
Answer
C. 9 goes first (991 > 919 and 9919 > 9199). Then 919 + 91 = 91991 beats 91 + 919 = 91919, so 919 goes before 91: 9 · 919 · 91 = 991991.
Interview questions
- What does a comparator return?
trueif the first argument must come strictly before the second. - What is a strict weak ordering? Irreflexive, asymmetric, transitive, with consistent "equal" classes;
<on numbers, strings and tuples is one. - Why can
<=crashstd::sort? Its unguarded insertion loop relies oncmp(x, x)being false; with<=it can run past the array start (undefined behaviour). - How do you sort by several keys? Compare tuples (
make_tuple/tie) key by key; negate numeric keys for descending. sortvsstable_sort?stable_sortkeeps equal elements in input order (O(n log n), extra memory);sortdoes not promise that.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Comparator | A function answering "must x come before y?" | x + y > y + x |
| Lambda | A small nameless function written in place | [](int a, int b) { return a > b; } |
Capture [&] |
Lets a lambda use outside variables by reference | sort indices by a[i] |
const & (const reference) |
Look at a value without copying or changing it | const string &x |
| Lexicographic (dictionary) order | Compare strings character by character | "30" > "3" |
| Concatenation | Gluing strings end to end | "3" + "30" = "330" |
| Strict weak ordering | The rules a comparator must follow (never <=) |
< on tuples |
| Undefined behaviour | The C++ standard promises nothing; may crash | >= comparator |
next_permutation |
Rearranges into the next order; false after the last | brute force over orders |
| Stress test | Compare brute force and fast solution on random inputs | 1000 tests |
| Tuple | A fixed group of values compared key by key | make_tuple(-solved, pen, name) |
stable_sort |
Sort that keeps equal items in input order | ties by arrival |
stoll |
Converts a string to long long |
stoll("34") = 34 |
| Segmentation fault | The program touched memory it doesn't own (SIGSEGV) | >= on 20 equal items |
Summary
- Biggest-number-first gave
3430953, reverse dictionary order gave9534303: both Wrong Answer. - Every order was correct but TLE at n = 12 (12! orders); it became the stress-test judge.
- The pair rule
x + y > y + x, given tosortas a lambda comparator, solves Price Tag in O(n log n · L). - The stress test caught the wrong rule on
40 100 96 10; the right rule passed 1000 tests. - Comparators must be strict:
>=crashedstd::sorton 20 equal stickers (fine on 16). - Several keys: compare
make_tuple(-solved, pen, name). - Edge case: all zeros → print
0.
Next episode: greedy algorithms with exchange-argument proofs.