UVa 10905

From Algorithmist
Jump to: navigation, search

10905 - Children's game[edit]

Summary[edit]

Given are several numbers. Find the way how to concatenate them so that the result is as large as possible.

Explanation[edit]

There are many different ways how to write a wrong solution to this problem. There are lots and lots of possible heuristic algorithms, but most of them are doomed to fail.

A more systematic approach is required. First of all, forget that the input is given as numbers. We have several strings and we want their lexicographically largest concatenation.

Consider an arbitrary concatenation of the given strings. One simple way how we can try to improve the solution: find two subsequent strings such that by swapping them we obtain a better solution.

For example, let the given strings be "99", "90", "70", "7", and "123". By concatenating them in this order, we get the result "9990707123". However, we may note that by swapping "70" and "7" we get a better result, "9990770123".

Now, note that the fact whether we should swap two subsequent strings depends only on these two strings. If the strings are x and y, their possible concatenations are xy and yx. If and only if yx>xy, you should swap them.

Given any starting sequence, make such swaps until no more swaps are possible. It can be proved that the result is optimal. (See Notes.)

Gotchas[edit]

  • The input description only states that the given numbers are positive integers, it doesn't give an upper bound on their size. To be on the safe side, input them and process them as strings.

Notes[edit]

If we define x\triangleleft y~\Leftrightarrow ~xy<yx\,\lor \,(xy=yx\,\land \,|x|<|y|), it is easy to show that \triangleleft is a complete order on the set of all strings. (I.e., the relation is irreflexive and transitive.) Thus, the whole problem boils down to sorting the strings using \triangleleft as the comparison function.

Implementations[edit]

The input used at UVa is quite small, a quadratic sorting algorithm will be accepted.

Solutions[edit]

Input[edit]

4
123 124 56 90
5
123 124 56 90 9
5
9 9 9 9 9
1
1
5
991 9909 99 990 989
2
191 1919
2
345 3453453453453453
2
345 3453453453453454
2
90 9
30
53 206 12 9 3271 17 1 18 2319 9 17445 1813 7486 530 2 6 3 207 484 5 15 2211 214 91 22 33 10163 27690
26267 831
26
17 20 20345 1715 141 2 241 6 10901 9 1382 13813 681 181 1784 31727 4405 1445 84 520 114 2285 22
30330 10 235
12
10 5934 2289 30363 45 232 10 1734 160 1206 1029 1244
8
210 42 18 134 1373 2253 429 1102
5
163 21817 528 1905 185
3
2299 1 896
46
19 2249 1363 13 12 7 17167 5 57 1229 11 191 31067 25217 17549 2078 2031 2366 67 883 11802 16 19 362
48 10395 416 1997 12 141 5 6 19746 6 7 19 25100 1425 13968 24779 21778 611 1 3 722 154
2
5 8
3
10 102 1024
2
90 9
2
56 5
5
1 12 123 1234 12345
7
9 98 987 9876 98765 987654 9876543
6
9 900 9 90 9 9
1
24187
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5
1 11 111 1111 11111
2
666666666666666666666666666666666666 123421412341234
2
123421412341234 635235523523523566666666666666666666666666666666666
0

Output[edit]

9056124123
99056124123
99999
1
999919909990989
1919191
3453453453453453453
3453453453453454345
990
999183174866553530484333327127690262672319222221121420720618181317445171512110163
98468165204405317273033024123522852222034520181178417171514451411382138131141090110
59344530363232228917341601244120610291010
4294222532101813731341102
528218171905185163
89622991
883777226766611575548416362331067252172510024779236622492177820782031199719746191919191175491716716154142514113968136313122912121180211110395
85
102410210
990
565
123451234123121
9989879876987659876549876543
999990900
24187
9876543220191817161514131211110
111111111111111
666666666666666666666666666666666666123421412341234
635235523523523566666666666666666666666666666666666123421412341234