TrixX's Journal: CyM

Después de volverme de ACM, y pasar un par de días en Cuesta Blanca con la Ra (vacaciones! :) ), me volví a ir para Bs. As. el 16 a la noche.

Esta vez, para ir como jurado al 7mo torneo de Computación y matemática. En esa página pueden encontrar la prueba. Estuvo bastante bueno, estuvimos corrigiendo con Jorge Sacchini y Dante Zanarini (exolímpicos rosarinos). Mas tarde nos dio una mano Pablo Haramburu

Después de un par de noches de dormir poco, salieron los campeones de la que, como dijo Pablo, es la segunda generación de CyM; ya no queda ninguno de los que participabamos originalmente.

Hubo un pedacito de codigo, bastante interesante que quería mostrar:

/*entrada: int l, int a[l] */
int i,j;
for (i=0;i<l;i++)
...for (j=0;j<l;j++)
......if (a[i] > a[j]) swap(a[i],a[j]);
/* swap hace lo obvio */
/* y slashdot no muestra la indentaci&#243;n, as&#237; que use puntitos */

Ejercicio: 1) que hace esto? 2) Darse cuenta que en realidad no es tan obvio como parece a primera vista (revisar los rangos) 3) Ver que en realidad si funciona.

Estuvimos un rato para entender porque eso funcionaba. Diviertanse.

+1 Interesting

[anicholo]

Ja! muy bueno... Pero el/la chabón/ona lo habrá entendido él/ella mismo/a?

Re:+1 Interesting

[TrixX]

Hacia lo que tenía que hacer... y resolvió el problema. Esperemos que lo haya entendido, porque ganó

Punto extra: adiviná en que problema fue :) (3er nivel)

Re:+1 Interesting

[mpupu]

Es uno de esos algoritmos que una vez que los sabes, te olvidas de como funciona pero te acordas del codigo porque es muy simple.

A mi me pasaba con el Floyd-Warshall. Si me pedis demostrarlo, me tomaba mi tiempo. Pero escribirlo era automatico.

Deberia haber una categoria para esos tipos de algoritmos.

Ahora si, pasando al codigo:

*SPOILER*

Yo lo llamaria AIS (Anti-Intuitive Sort). Te das cuenta que es un sort por los swap. Al principio parecia un Bubble, pero despues lo analizas un poco y ves

Re:+1 Interesting

[TrixX]

Es un poco más complicado que un insertion. Fijate que no va insertando las cosas a medida que llegan, sino que va metiendo siempre el más grande. En ese sentido, podrías decir que tiene un poco de "selection sort".

Nosotros (el jurado de CyM) le empezamos a llamar "Rassol Sort" (por el nombre del participante que lo escribió)

The final spoiler

[TrixX]

[indentado con puntos ya que /. no me deja otra]:

Fijense que lo pueden reescribir asi:

/* Primer lazo, cuando i=0 */
for (j=0;j<l;j++)
...if (a[0] > a[j]) swap(a[0],a[j]);
/* Primer lazo, cuando i>0 */
for (i=1;i<l;i++)
.../* Segundo lazo con j<i */
...for (j=0;j<i;j++)
......if (a[j] < a[i]) swap(a[i],a[j]);
.../* Cuando j=i no hace nada */
.../* Segundo lazo con i<j */
...for (j=0;j<l;j++)
......if (a[i] > a[j]) swap(a[i],a[j]);

Esto es equivalente al programa inicial

La primer vuel