1109. The Largest Number You Can Spell Out
You are given n non-negative whole numbers. Write them one after another, in any
order you like, to form one long number. Print the largest number you can make.
10 2 9 -> 9210
3 30 34 5 9 -> 9534330
30 3 -> 330
0 0 1 0 -> 1000
0 0 0 -> 0
The second line is the one everybody gets wrong first. Ordinary descending order by
VALUE gives 34 30 9 5 3, which spells 349053 and is smaller than 9534330. Ordinary
descending order as TEXT gives 9 5 34 3 30, spelling 9534330 here but failing on
30 3, where text order puts 30 before 3 and spells 303 instead of 330.
## What most people try first
Sorting by value, sorting as text, sorting by first digit, sorting by length. Every one
of them is right on some inputs. Trying every order is exact and costs n!.
The rule that works compares two numbers by which of their TWO orderings spells more:
> a comes before b when the text a followed by b is larger than the text b
> followed by a, compared as text of equal length.
On 30 and 3: "303" against "330". The second is larger, so 3 comes first. On 9
and 34: "934" against "349", so 9 comes first.
## The method
read every value as TEXT, not as a number
sort with the comparator: a before b when a + b > b + a as strings
join them
if the result starts with '0', print a single 0
One sort with an O(len) comparison, so O(n log n * 10) for values up to ten digits.
## Why the comparator is a genuine total order
This is the part that matters, and it is not optional. A C++ sort given a comparator
that is not a strict weak ordering is undefined behaviour: it can read past the end of
the array and crash, not merely return a wrong order. So the comparator has to be shown
to be transitive before it is used.
Write a <= b to mean the text a + b is at most the text b + a when compared as
equal-length strings.
Suppose a <= b and b <= c. Concatenation of digit strings is the same thing as
a * 10^len(b) + b in arithmetic. Writing A, B, C for the values and p, q,
r for 10^len(a), 10^len(b), 10^len(c):
a <= b means A*q + B <= B*p + A
b <= c means B*r + C <= C*q + B
Rearranged, the first says A*(q - 1) <= B*(p - 1) and the second says
B*(r - 1) <= C*(q - 1). Every one of p - 1, q - 1, r - 1 is at least 0, and it
is 0 only for the empty string, which does not occur. Multiplying the first by
(r - 1) and the second by (p - 1) and chaining gives
A*(q - 1)*(r - 1) <= C*(q - 1)*(p - 1), and dividing by the positive (q - 1) gives
A*(r - 1) <= C*(p - 1), which is exactly a <= c.
So the relation is transitive, it is total because any two strings compare one way or the other, and antisymmetry holds up to equal spellings. It is therefore a valid sort key.
## Why the sorted order is the best order
With a total order in hand, the exchange argument is short. Take any arrangement that
is not sorted. Two ADJACENT entries are then out of order, say b immediately before
a with a before b under the comparator. Swapping them changes nothing outside the
pair, because the two occupy the same span of digit positions, and by the definition of
the comparator the swapped pair spells a larger number in that span. So the whole number
grows, and no unsorted arrangement can be the largest.
## The boundary that breaks a careless implementation
All zeros. The input 0 0 0 spells "000", and the required answer is 0, not 000.
Stripping leading zeros and printing a single 0 when nothing is left is the fix.
Comparing as NUMBERS rather than text fails as soon as the joined value exceeds what an
integer type holds: n reaches 10^5 and each value has up to ten digits, so the
answer has up to a million digits. It must be built and printed as text.
## Sizes
Each value is at most 10^9, which fits in a signed 32-bit integer. The ANSWER does
not fit in any integer type at all, which is why the whole problem is done on strings.
Inside the comparator, comparing a + b against b + a as text avoids arithmetic
entirely.
## A related problem
Problem #1117 is the other comparator problem in this block. There the pairwise rule is arithmetic rather than textual, and the transitivity argument comes out of an ordinary inequality instead of a digit-length one. Both exist so that "prove your comparator is an order" becomes a habit.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ value ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated non-negative whole numbers.
Output
Print the largest number that can be spelled by writing every given value one after another, as a single line of digits with no spaces and no leading zeros. When every value is zero print a single 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.