google code jam 2010
No hay nada como programar a la luz de la luna… O algo asi debieron pensar los organizadores del concurso de programacion Google Code Jam. La primera ronda ha tenido lugar este sabado, comenzando a la una de la madrugada y terminando a la una de la madrugada del domingo.
Y por si no tengo bastante con lo que programo en el curro, ni corto ni perezoso, me he puesto a solucionar los problemas de esta primera ronda.
De uno de ellos es del que os voy a hablar ahora…
Eliminando la narrativa del problema (joder, se tarda mas en leer alguno de los problemas de lo que tardas en resolverlo!!), basicamente el problema era encontrar un numero x que sumado a una coleccion de numeros nos permitiese maximizar su maximo comun divisor. Por ejemplo, dada la coleccion de numeros : (16, 6, 11) la solucion seria x=4, puesto que:
mcd(20,10,15) = 5
Pero, como solucionamos este problema? Me imagino que habra soluicones mejores, pero yo os voy a proponer la solucion que se me ocurrio a mi sobre la marcha, Y de paso me excusare comentando que el Code Jam es un concurso contra el crono con lo que la solucion mas optimas puede no ser la que mas nos interese.
Bueno, como lo que queremos hacer al final es maximizar un maximo comun divisor, vamos a ver la implementacion tipica del mcd, el algoritmo de euclides: Una posible implementacion es esta:
{
unsigned int result;
assert(x>y);
if(y == 0)
{
result = x;
}
else
{
result = mcd(y, x%y);
}
return result;
}
Bien, si nos fijamos en esa descripción recursiva del maximo comun divisor vemos que tenemos un problema a la hora de llevar a cabo operaciones matematicas debido a la presencia de un modulo, pero en realidad tambien podemos expresar la recursividad con ayuda de la resta:
Y este es el punto de partida para mi solucion. Nos estan pidiendo calcular el mcd(a+x,b+x), que podriamos desarrollar como:
mcd(b+x, a+x – b – x) =
mcd(b+x, a-b)
Y nuestro objetivo es maximzar el mcd. El maximo mcd(a,b) se da cuando a = b, por lo que tenemos:
x = a -2b;
Con lo que finalmente tenemos :
Ejemplo : a = 91, b = 81
a-b = 10;
Como resultado de haber cambiado el modulo por la resta, el valor de x puede salir negativo, en cuyo caso podremos calcular un x positivo alternativo:
x = 0
sino
x = ((a-b)* ((a / (a-b)) + 1)) – a;
Que no es mas que calcular la diferencia entre a y el multiplo de (a-b) mas pequeño que sea mayor que a.
Bueno, Y ahora que sabemos como calcular x para dos numeros (a,b), como hacerlo para (a,b,c,…) Pues muy sencillo : Recolectando todas las diferencias y calculando el mcd comun a todas ellas
Y esto es to to todo amigos :o)
Espero que hayais «disfrutado» con la explicacion. Por cierto, google deja de disposicion de quien le interese el codigo fuente de todas las soluciones de todos los participantes…
riau!