Editorial for Ordenamiento de la comida

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: dcordb

Se arma un grafo de la siguiente forma: se conecta la posición $i$ ~i~ con la posición que le corresponde al $i$ ~i~-ésimo elemento en el arreglo final. Estos grafos son ciclos dirigidos simples de $k$ ~k~ nodos y $k$ ~k~ aristas (cada nodo tiene exactamente un padre directo y un hijo directo), estos ciclos también se conocen como ciclos de permutación. Para arreglar un ciclo se puede hacer una de dos cosas:

Ir intercambiando el menor elemento con su padre directo hasta que caiga en su posición (esto hace que todo el ciclo se arregle). Si denotamos al menor como $l$ ~l~ y a la suma de los elementos en el ciclo como $t$ ~t~ entonces el costo sería $t + (k - 1) \cdot l - l$ ~t + (k - 1) \cdot l - l~ ya que el menor participa en exactamente $k - 1$ ~k - 1~ intercambios y adicionalmente cada elemento participa en un intercambio.
Cambiar el menor elemento del arreglo (llamemosle $mn$ ~mn~) con el menor del ciclo y resolver el ciclo usando el método de arriba. El costo sería $t + (k - 1) \cdot mn + 2 \cdot (mn + l) - l$ .

En ambos casos se resta $l$ ~l~ al final porque ya se cuenta al sumar $t$ ~t~. El costo total es la suma, para cada ciclo, del mínimo de ambos casos.

Complejidad: $O(n)$ ~O(n)~

Comments

1

jcg commented on Feb. 2, 2018, 1:22 p.m. ← edited →

Bueno, dcordb discrepo contigo, si hay elementos iguales esta claro que se pueden producir permutaciones diferentes (y los ciclos no son los mismos), y no todas daran el mismo resultado al aplicar el algoritmo, y de hecho, la permutacion "natural" no tiene por que dar el resultado optimo con el algoritmo propuesto, ejemplo: si la entrada es 4 4 1 3 3, podemos formar dos permutaciones validas: 4 1 2 3 y 4 1 3 2, el costo de la primera es 13 con el algoritmo de la editorial y el costo de la segunda es 9. Ese problema cuando la permutacion esta dada es uno "clasico", creo que incluso salio en una final mundial del acm-icpc a principio de los 2000, pero el problema aca es que la permutacion no esta dada, y al existir pesos iguales entonces se pueden formar varias, y como te acabo de ejemplificar, la permutacion "obvia" que formamos no tiene que producir el resultado optimo. La fuente en español en la que se basaron para hacer el problema tiene un error de traduccion de la fuente original, aca esta el texto original Cow Sorting, y fijate que contiene palabra muy importante y es unique en la oracion

Each cow has a unique "grumpiness" level in the range 1...100,000.

Y cambia el problema completamente, porque sino la solucion propuesta no es correcta, les sugiero que arreglen el enunciado del problema, y en el futuro remitanse a los textos originales para evitar errores de este tipo. La version "con pesos iguales" parece un problema interesante, pero parece que no es tan simple de resolver (no me consta que exista una solucion polinomial, aunque no descarto como posible que sea asi). Saludos, y muchas felicidades por la iniciativa que traen con este nuevo sitio..

0

dcordb commented on Feb. 2, 2018, 4:02 p.m.

Ok tienes razón en lo que dices, los ciclos si son distintos, al parecer el problemsetter no se fijó bien al traducir el texto .. ya está arreglado. Gracias, saludos.

0

dcordb commented on Feb. 1, 2018, 8:48 p.m.

A ver se tiene que llevar el arreglo inicial a un arreglo ordenado .. lo que yo pienso que pasa es que para todas las permutaciones del arreglo inicial que esten en orden ascendente el costo de llevar desde el arreglo inicial a una de estas va a ser el mismo .. nota que va a cambiar el "orden" de los elementos iguales (en el arreglo final) .. pero los ciclos van a seguir siendo los mismos.

1

jcg commented on Feb. 1, 2018, 2:52 p.m.

Bueno, la solucion funciona si los $X$ ~X~ son diferentes, pero si no lo son no me queda nada claro que funcione, porque se pueden formar varias permutaciones validas como la descrita en la solucion, y no es obvio (al menos no para mi) que todas estas den la misma solucion. Podria el problemsetter o alguien que se haya "molestado" en demostrar la correctitud de la solucion escribir la demostracion aca? El detalle de que las $X$ ~X~ pueden ser diferentes es muy importante.