Official Editorial (C++ and Python)

Explanation

Solution

The rigorous proof of the method used to solve this problem is available on Codeforces and beyond the scope of USACO Silver. However, we present here how one might arrive at this solution and be convinced that it works.

If all the strings in the input had the same length, we can prove that this solution would in fact work.

However, this method does not work in this problem as strings do not have to be the same length. For example, with the testcase:

4
z
za
b
by

The best concatenation would be "bbyzaz".

However, depending on how you personally define "lexicographically smaller", you may either get "bbyzza" or "bybzaz". Neither of these are the correct answer.

The reason why the solution fails here is because it doesn't make sense to compare two strings of different lengths since you don't know what can appear in the gap left by the shorter string.

b?
by
(If we don't know '?' we can't be sure which is smaller)

Therefore, for this problem, it only ever makes sense to compare strings of same length. To do this, when deciding which of strings $a$ or $b$ goes first, we can instead compare $a + b$ and $b + a$, which have the same length.

bby
byb
(No uncertainty at all, "bby" is smaller)

Though this is not a rigorous proof, this is how one may arrive at the solution and convince themselves that it works. For the rigorous proof by Lewis Gan, check the official editorial linked above.

Time Complexity: $\mathcal{O}(n \log(N) \cdot |a_i|)$

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

bool comp(const string &a, const string &b) { return (a + b) < (b + a); }

int main() {
	int n;
	cin >> n;

	vector<string> inps(n);

Copy
import java.util.Arrays;
import java.util.Scanner;

public class Smallest {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[] inps = new String[n];
		for (int i = 0; i < n; i++) inps[i] = sc.next();
		sc.close();

Copy
from functools import cmp_to_key

n = int(input())
inps = []
for _ in range(n):
	inps.append(input())


def compare(x: str, y: str) -> int:
	if x + y > y + x:  # y should come before x