Facebook "Hacker cup"

[]_HQH_[]

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

Saludos!!

[]_HQH_[]

He pasado la ronda. ¿Alguien mas de por aqui ha participado y pasado la primera ronda?

Un saludo.

[Oblivi0n]

He pasado la ronda. ¿Alguien mas de por aqui ha participado y pasado la primera ronda?

Un saludo.

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

[ghastlyX]

Yo también he pasado de ronda. He hecho los tres problemas correctamente.

[qw3rty404]

Yo no he pasado, no he hecho los problemas

[leogtz]

Yo también he pasado de ronda. He hecho los tres problemas correctamente.

ánimo, ghastlyX, he visto que eres excelente en algoritmia Suerte

[ghastlyX]

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.

[]_HQH_[]

Hola ghastlyX, es un placer ver a gente interesada en algorítmica ya que hay pocos, a mi siempre me ha encantado e intento comentar cosas en foros y en mi propio website hispabyte.

El 2 ni lo intente no por nada, sino por perreria (saber que haciendo uno te clasificas da perreria), por lo cual no puedo ayudarte a pensar una solucion alternativa, ya que ni recuerdo el enunciado.

Hice el primero y el tercero también al ver que era muy fácil y rápido de codificar también por si acaso.

En el primero, lo que hacía era para obtener el resultado de N, iteraba i desde 0 hasta N hasta que i*i fuera mayor que N y LA diferencia entre N y i*i fuera menor que i*i. Cuando era menor, simplemente usaba la diferencia entre N y I*I y si esta diferencia era un cuadrado perfecto, sumaba 1.

El único problema era evitar repeticiones, eso lo hacía parando también cuando la diferencia de N-i*I fuera menor que el propio i*i (porque suponemos que dicha combinación ha sido probada ya anteriormente).

El tercero, el mas fácil de todos, eran pocas combinaciones y se hacia fácil con cualquier método de ordenación, yo use la funcion qsort de C y me daba tiempo de sobra.

Sobre la competición en si, no se si es por ser la primera vez, pero estan teniendo problemas organizativos, de corrección de problemas, etc...

Un saludo y suerte para entrar en el top 3000

[ghastlyX]

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:

Código (cpp) [Seleccionar] Expandir

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.

[]_HQH_[]

Yo estoy ya retirado, aunque en su dia tambien participe en la OIE y en la SWERC, es siempre bonito encontrarse con gente del mundillo

A ver que tal son los problemas de luego, un saludo.