The Smallest String Concatenation

Editorial oficial (C++ y Python) 

Explicación

Solución

La demostración rigurosa del método usado para resolver este problema está en Codeforces y queda fuera del alcance de USACO Plata. Sin embargo, presentamos aquí cómo se puede llegar a esta solución y convencerse de que funciona.

Si todos los strings de la entrada tuvieran la misma longitud, se puede demostrar que esta solución de hecho funcionaría.

Sin embargo, este método no funciona en este problema porque los strings no tienen por qué tener la misma longitud. Por ejemplo, con el caso de prueba:

4
z
za
b
by

La mejor concatenación sería “bbyzaz”.

Sin embargo, según cómo se defina personalmente “lexicográficamente más chico”, se puede obtener “bbyzza” o “bybzaz”. Ninguna de las dos es la respuesta correcta.

La razón por la que la solución falla aquí es que no tiene sentido comparar dos strings de distintas longitudes, porque no se sabe qué puede aparecer en el hueco que deja el string más corto.

b?
by
(Si no sabemos '?' no podemos estar seguros de cuál es más chico)

Por lo tanto, en este problema, solo tiene sentido comparar strings de la misma longitud. Para ello, al decidir cuál de los strings $a$ o $b$ va primero, podemos comparar $a + b$ y $b + a$, que tienen la misma longitud.

bby
byb
(Sin ninguna incertidumbre, "bby" es más chico)

Aunque esto no es una demostración rigurosa, es cómo se puede llegar a la solución y convencerse de que funciona. Para la demostración rigurosa de Lewis Gan, ver el editorial oficial enlazado arriba.

Complejidad temporal: $\mathcal{O}(n \log(N) \cdot |a_i|)$

Implementación

#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);
	for (string &s : inps) { cin >> s; }
 
	// Ordenamos con un comparador personalizado
	sort(inps.begin(), inps.end(), comp);
 
	// Imprimimos todo en el orden lexicográficamente más chico
	for (const string &s : inps) { cout << s; }
}

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();
 
		// Ordenamos con un comparador personalizado
		Arrays.sort(inps, (a, b) -> (a + b).compareTo(b + a));
 
		// Imprimimos todo en el orden lexicográficamente más chico
		System.out.println(String.join("", inps));
	}
}

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 debería ir antes que x
		return 1
	elif x + y < y + x:  # x debería ir antes que y
		return -1
	return 0  # x e y son iguales
 
 
print("".join(sorted(inps, key=cmp_to_key(compare))))