Yo he participado ¿Alguno participo? ¿Participan en algunos similares como el google code jam?

Saludos!!

Yo hice el primer ejercicio, el de la suma de los cuadrados y paré, no confiaba en pasar la primera ronda xD

Yo no he pasado, no he hecho los problemas

Gracias, a ver hasta donde se puede llegar

Para los que han participado, me gustaría saber si alguien ha hecho alguna solución cuadrática para el segundo problema. Estuve pensando un rato pero no se me ocurrió ninguna y programé la dinámica cúbica estándar, que era igualmente instantánea con la entrada que se daba.

Por si a alguien le sirve, comento un poco mis soluciones.

Problema 1: Simplemente precalculo los cuadrados de todos los números hasta 50000 (cuyo cuadrado es sobradamente mayor que el máximo que te dan ellos) y los guardo en un AVL. Una vez hecho esto, con cada número de la entrada itero hasta su raíz y miro si la diferencia entre el número y el iterador al cuadrado está en mi AVL, incrementando en uno el contador en dicho caso. Por lo tanto, la complejidad para cada caso es de O(sqrt(x)*log(50000)), es decir, iterar*(coste de buscar en el AVL).

Problema 2: La idea es dada una posición de inicio, saber con qué probabilidad llega al objetivo. Para esto hago una dinámica cuadrática sobre la matriz del juego y en cada posición guardo la probablidad de llegar a dicha casilla. Por lo tanto, inicializo la primera fila todo a 0 excepto la de inicio, que le pongo 1. El resto de la matriz se inicializa también toda a cero. Una vez hecho esto, voy iterando fila a fila. Si en una posición tengo probabilidad mayor que cero, la propago a la fila inferior siguiendo las normas del enunciado. Tras hacer esto, en la casilla destino tengo la probabilidad buscada. Teniendo hecha esta dinámica en función de la casilla inicial, basta iterar sobre todas las posibles (tantas como columnas haya - 1). Así, acaba quedado una complejidad de O(filas*columnas^2), es decir, cúbica.

Problema 3: Aunque después vi que un backtracking a saco entraba, por si acaso programé una solución algo más rápida. Suponiendo que comparar las strings es constante (algo no muy descabellado puesto que tenían como mucho 10 carácteres), si había n strings el backtracking tiene coste O(n!), es decir, todas las posibles permutaciones. Mi solución, usando programación dinámica tiene complejidad O(n*2^n). La idea es hacer que el estado sea una máscara que indica qué strings he utilizado hasta el momento y que devuelva la menor string lexicográficamente que se puede obtener con las strings restantes. Así, tan sólo hace falta iterar sobre la máscara y probar a poner las strings que no están usadas.

Yo también estoy interesado. Participé en su día en la OIE y ahora con la universidad participo en el SWERC.

Para el segundo ayer descubrí que la solución cuadrática que había implementado sí era correcta, tan sólo tenía un pequeño bug que ya he corregido en el código. La idea era empezar por abajo y propagar hacia arriba.

Respecto al tercero, también me comentó un amigo ayer que aunque ordenar las palabras a saco y concatenar no era correcto (puede fallar cuando una palabra es prefijo de otra), sí que se puede hacer usando como función de comparación la siguiente:

bool cmp(const string &a, const string &b){
    return (a+b) < (b+a);
}

Sobre la competición, es cierto que han tenido bastantes fallos. Yo para estar al día iba mirando en los foros de Topcoder, donde un par de empleados de Facebook iban contestando a las dudas de la gente, puesto que en la página del concurso no decían nada.