Editorial for Permutación de Palabras


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ale

Inicialmente las cadenas estaban ordenadas y luego se les aplica una permutación sigma, por lo que la cadena i-ésima acaba en la posición sigma(i)-ésima.

Por ejemplo si tenemos la lista de cadenas:

abc
foo
xyz

y aplicamos la permutación: [2, 3, 1], la 1ra cadena acaba en la posición 2da, la 2da en la posición 3ra y la 3ra en la 1ra:

xyz
abc
foo

Fácil cierto, pero ahora es todo alrevés; nos dan la lista permutada y nos piden qué permutación se usó. Ahora, conocemos las cadenas que hay en la lista y podemos ordenarlas, ahora si además de ordenarlas mantenemos el índice donde se encuentra en la lista final podemos ir una a una en la lista ordenada y saber para la i-ésima en qué posición quedó.

Complejidad O(NlogN).


Comments

There are no comments at the moment.