SyntaxPilot
Courses/Competitive Programming/Lesson 13

Competitive Programming · Lesson 13 of 90 · 13 min

Sorting tricks and custom comparators

queued

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 n stickers; sticker i is a string of digits a[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, each a[i] has 1 to 9 digits.

Sample input Sample output
5
3 30 34 5 9
9534330
3
0 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 by a[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:

  1. Irreflexive: cmp(x, x) is false. Nothing comes before itself.
  2. Asymmetric: if cmp(x, y) is true, cmp(y, x) is false.
  3. Transitive: cmp(x, y) and cmp(y, z) mean cmp(x, z).
  4. (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_sort keeps equal items in their input order; to sort indices by value, iota an 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

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

  2. Sort points by distance from (0, 0), ties by x, then y.

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

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

  4. Sort indices 0..n−1 by a[i] without moving a.

    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

  1. What does a comparator return? true if the first argument must come strictly before the second.
  2. What is a strict weak ordering? Irreflexive, asymmetric, transitive, with consistent "equal" classes; < on numbers, strings and tuples is one.
  3. Why can <= crash std::sort? Its unguarded insertion loop relies on cmp(x, x) being false; with <= it can run past the array start (undefined behaviour).
  4. How do you sort by several keys? Compare tuples (make_tuple / tie) key by key; negate numeric keys for descending.
  5. sort vs stable_sort? stable_sort keeps equal elements in input order (O(n log n), extra memory); sort does 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 gave 9534303: 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 to sort as 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: >= crashed std::sort on 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.