cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2021 · MediumSorting by concatenation

Largest Concatenated Number

National Olympiad — National round (2021 season)

Submission name: maxc.cpp

Solve in Editor →

Problem summary

Reorder all given numbers so that concatenating their decimal representations produces the largest possible number.

Input

N followed by N nonnegative integers.

Output

The chosen concatenation, without spaces.

Constraints

1 ≤ N ≤ 100000; 0 ≤ a[i] ≤ 10^9.

Worked example

Input and output for the worked example discussed below.

Input

4
20 17 18 2

Output

2201817

Solution analysis

  1. Sorting numerically is insufficient: 20 is larger than 2, but putting 2 before 20 gives 220 rather than 202. For two strings a and b, compare a+b with b+a.
  2. Sort so that a precedes b whenever a+b>b+a. Every pair of adjacent strings then has the better relative order. This comparator is a valid strict weak ordering; ties can be kept in either order.
  3. The example becomes 2,20,18,17, giving 2201817. Keep values as strings throughout; the final result can contain a million digits and must never be converted into a numeric type.

Why it works

If adjacent strings a,b appear in the less favourable order, exchanging them increases the full concatenation because all earlier and later digits remain identical. Repeated exchanges lead to the comparator-sorted arrangement without decreasing the result. Thus no arrangement is larger.

Complexity: O(N log N × D) time, where D≤10 is the maximum input digit count; O(ND) storage for the strings. Each comparison concatenates at most 20 characters.

Watch out. Use a+b>b+a, not plain string order or descending numeric order. Preserve all input entries, including repeated values. Equal concatenations must not compare true in both directions.

Commented C++17 solution

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<string>values(n);
    for(string&value:values){
        cin>>value;
    }
    // Decide which relative order produces the larger digit sequence.
    sort(values.begin(),values.end(),[](const string&a,const string&b){
        return a+b>b+a;
    });
    for(const string&value:values){
        cout<<value;
    }
    cout<<'\n';
}

Source: Arena Olimpiici ↗