Foro de elhacker.net

Hola.

Parece que ha habido algún problema con el antiguo tema, o bien técnico o bien por una dinámica que no ha gustado a algún moderador, por lo que he decidido globalizar el contexto y crear un espacio donde todo aquel que tenga pensado tomar parte del concurso debata sobre el tema y presente sus opiniones respecto a ella.

He leido hace poco por el foro que Facebook ha organizado un concurso donde presentan una serie de problemas de programación, llamado "Hacker cup". No tengo casi ningún conocimiento sobre ello. Hace algún tiempo empecé a estudiar Visual basic pero tuve una serie de cuestiones en las que fijarme en mi día a día con una mayor prioridad que la informática. En definitiva, quedó en nada.

No creo que haya que conocer perfectamente cada idioma que ellos exponen. Creo que, de alguna forma, hay que amoldar las estructuras de cada lenguaje a cada acertijo que se presente, pero no la sintaxis del lenguaje en sí, o al menos en un mínimo. Lo creo porque de alguna forma sería una estupidez el pedir programadores cuando Facebook dispone de un capital suficiente para contratar a los mejores programadores del mundo.

Me parece a mí que la dinámica de los acertijos van a ser, precísamente, la que se dispone a un acertijo. En otras palabras, una capacidad lógica antes que un conocimiento ya memorizado de una serie de procedimientos. Por tanto creo que lo más importante sería, en primer lugar, conocer la estructura de cada lenguaje expuesto en su página de Facebook, y en segundo lugar tener un conocimiento profundo sobre los inicios de cada lenguaje, ya que supongo que será cuestión de optimizar código, y por tanto se debe conocer hacia que se orientó en un primer lugar cada lenguaje de programación.

Tras esta serie de planteamientos no me hace falta ayuda realmente, ya que sólo debo buscar en cualquier Wiki la historia de cada lenguaje, y conocer levemente su estructura.

Me gustaría por tanto que si alguien de aquí tiene pensado participar comente sus motivaciones y lo que sabe de esta competición.

Un saludo.

Sí señor...Yá eres todo un Hacker... :laugh: :laugh: :laugh: :laugh: :laugh:  :laugh: :laugh: :laugh::laugh: ;-) ;-) ;-)



Salu2.

que ganas de ir a pasar verguenza

Contigo es que me parto el culo. Sólo te falta leer a qué estaba referida la cita que has incluido en tu mensaje, así entenderías por qué la he dicho. ¿Vas a participar?

¿Pero eso no lo hace cada uno desde su casita? xDD

que es "eso" ?

el passar verguenza o el concurso ? xD

El concurso

 el pasar verguenza jajajajajajaja.  ;-) :laugh: :xD

hasta donde vi se va a tener que saber mucho de matematicas mas que un lenguaje en concreto , ovbio que conocer un lenguaje casi completamente tambien , pero es lo que a mi me parece... talves me ekivoco y la primera ronda es mas accesible , aunque no creo

Si, según he leido, el concurso principalmente no se basa en las capacidades del lenguaje que se tengan, ni el lenguaje en concreto (corrijanme si me equivoco), sino en la capacidad de resolver los algoritmos planteados, pero, obviamente, a mayor destreza con los lenguajes (y mayores conocimientos de matematicas) mejor saldrán los algoritmos, tambien se iva a evaluar el tiempo que tarde en resolverlos, o eso me parecio leer, desde luego a mi me parece interesante, yo voi a participar, ya se que no voi a ganar, pero bueno a ver si por lo menos llego a la segunda ronda (la que ai despues de la de clasificacion....  :xD )

Saludos

P.D
wtf?? :huh:

Programación != memorización de procedimientos....

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

Saludos!!

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

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

Yo no he pasado, no he hecho los problemas :xD

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

Gracias, a ver hasta donde se puede llegar :P

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.

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

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.

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.

¿Alguien esta intentando el contest (primera sub ronda de este fin de semana) ?

Yo participé ayer y si no me he equivocado en mis soluciones estoy clasificado, puesto que aún no han salido los resultados oficiales.

Me dio bastante rabia participar puesto que ya lo hice en la que les petó el sistema y me había clasificado, pero qué se le va hacer...

¿Tú o alguien más ha participado?

Yo participe a ultima hora en la primera sub ronda , me dio tiempo a intentar 1, que era uno de esos "triangulos" matemáticos, pero la lie en los módulos y falle.

Ayer hice la segunda sub ronda, y ahi hice el segundo de simulación y el tercero que era un josephus (el tipico de un circulo y matas a alguien cada k movimientos).

También como tu, me clasifique en la ronda que anularon.

La desorganización se esta notando en que en todas las subrondas, con un problema pasabas, no hay un indice de participación muy alto, almenos comparado con el Google Code Jam.