AQP TRAINING #4 – 2011 finalizado!!

Holas a todos,  hace unos momentos terminó  AQP TRAINING #4, y es por eso que felicitamos a:

1. a20012251 (1er lugar)
2. TheGoldenEagle (2do lugar)
3. EragonX (3er lugar)

Asimismo agradecemos a los que participaron.

Adicionalmente queremos pedir disculpas por no aver avisado con anticipación este evento, aunque de todos modos ocurrieron cosas interesantes hoy. Una de ellas fue la participación del actual primer puesto del topcoder de Perú (que por poco resuelve todos los problemas propuestos), y otra fue la rapidez y eficiencia del participante TheGoldenEagle en resolver el problema mas difícil(problema F) de este problem set, realmente siento muchas ganas de saber que algoritmo utilizó para resolverlo.

Ahora haremos una descripción de las soluciones de estos problemas

Problema A – Genealogy: Este problema si bien en un principio pareciera difícil, la verdad es que su solución es bien sencilla, para esto debemos darnos cuenta de que si un nodo X tiene Y padres y solo se permite d padres, ocurren los siguientes casos:

• Y <= d : Si pasa esto debemos dejar al nodo tal y como esta, sin ninguna modificación.
• Y > d: entonces debemos crear Y/d padres para lo cual el nodo X tendría Y/d + Y%d padres, de aquí se vuelve a verificar que el nuevo Y no exceda a d, si sucede eso se vuelve a ejecutar este caso.

Debemos hacer esto con cada uno de los nodos que tengan padres.

Problema B – Mountain Watching: Este problema muestra las bondades de aplicar un greedy, ya que greedy is good!, la observación esta en por ejemplo si tenemos las alturas 1 2 3 2 1 1 1 2 3 4 2 , vemos que una montaña esta en 1 2 3 2 1 1 1 y otra montaña esta en 1 1 1 2 3 4 2, como vemos el patrón 1 1 1 puede ser atribuido a las dos montañas. Entonces cada ves que vemos que la altura  baja , luego se mantiene  y finalmente sube, debemos contar todas las alturas en donde se mantiene para ambas montañas, y de ahi ya sacar la montaña de mayor longitud.

Problema C – Tower Parking: Aquí se requiere básicamente simulación, la parte mas difícil quizás este en la forma de hacerlo, en mi caso, utilice un priority_queue que me guardaba el piso y la posición en la cinta transportadora del auto de índice x a sacar, luego buscaba el mínimo entre mover el carro a través de la cinta horariamente o antihorariamente. Lo demas se hace tal y como te dice el enunciado lo dice.

Problema D – Stock Exchange: Este problema requiere la aplicación directa de un LIS(Longest Increasing Subsequence), sin hacer mas ni menos, para esto existen algoritmos con diversas complejidades como el DP ( O(n^2) ) o con binary search ( O(nlogn) ), dado el tamaño de la entrada, se debe escoger este último.

Problema E – Scheduling Lectures: Este problema tiene 2 partes, en una debemos calcular el mínimo de lecturas necesarias para abarcar los n tópicos, esto se puede hacer con un greedy, solamente llenamos una lectura con topicos hasta que ya no puedan caber mas, de ahi pasamos a otra lectura y seguimos el mismo procedimiento , todo hasta que ya no haygan mas tópicos. La segunda parte consiste en minimizar la desatisfacción de los estudiantes, aqui podemos usar programación Dinámica para lograr este objetivo, donde el estado sería:

• DP[i][j]:La mínima desatisfacción con i tópicos abarcados y j lecturas usadas.

Debemos notar que el máximo número de lecturas usadas que vamos a tener en este DP, ya lo hayamos en la 1ra parte.

Problema F – Lights: La primera ves que vi este problema, no tenia idea de como hacerlo, luego de unas cuantas horas de intentos di con el algoritmo correcto, y  recién hoy me dieron a conocer que el algoritmo que use aquella ves  es comúnmente llamado “meet in the middle”, fue una buena noticia saberlo, ya que me permite compartirla de una mejor manera con ustedes.  Con el ejemplo del enunciado pasaré a explicarlo:

• Dada la entrada podemos decir que el interruptor 1 esta conectado con 2 y 3, lo que nos lleva a saber que cada ves que apretamos ese interruptor tanto ese  1 como 2 y 3 son afectados(se prenden si estaban apagados o viceversa). Lo mismo sucede con los conjuntos {2, 1, 4, 5} , {3, 1, 4, 5} , {4, 2, 3} y {5, 2, 3}, ahora bien todo el sistema podemos representarlo como un entero donde cada bit equivale a un interruptor que es 1 si esta prendido y 0 si es que no lo esta, con esto podemos decir que si tenemos el entero 31 (en binario 11111), podemos asumir que el sistema esta completamente prendido, lo cual es nuestro objetivo. (el entero 0 representa 00000, el sistema inicial)
• Ahora que comprendimos esto, podemos añadir que si tenemos el conjunto {1, 2, 3} podemos representarlo en binario como 00111(el número 1 en el conjunto corresponde al primer bit , el número 2 al bit 2 y así sucesivamente), o si tenemos  el conjunto {3, 1, 4, 5} en binario significaría 11101, por eso para el ejemplo de arriba tendríamos las siguientes mascaras: 00111, 11011, 11101, 01110, 10110. ¿Y eso de que nos sirve?, la verdad de mucho siempre y cuando utilicemos el operador ^ , cuya tabla de verdad es : si hay bits iguales -> 0, si hay bits diferentes -> 1, como ejemplo si inicialmente nuestro sistema es 00000, si aplicamos un ^ con 00111, el resultado seria que nuestro sistema ahora es 00111(significa que la 1 , 2 y 3 están prendidos)y si ahora hacemos 00111^11101 = 11010(significa que ahora las luces 5, 4 y 2 están prendidas).
• Dado todo este preámbulo es donde entra a tallar el algoritmo “meet in the middle”, y consiste en dividir el conjunto de todos los interruptores en dos subconjunto de n/2 y n/2+n%2 (n= número de interruptores que existen,  n puede ser impar), para nuestro ejemplo los subconjuntos serian: {00111, 11011}  y  {11101, 01110, 10110}(lo que es igual a los enteros {7, 27} y {29, 14, 22}) y aplicar todos los subsets en cada subconjunto que nos dara de resultado 7, 27 y 7^27 en el primer subconjunto y 29, 14 , 29^14 , 22, 29^22, 14^22 y 29^14^22 en el otro subconjunto, como podemos notar para el caso de 7 hemos solamente usado un interruptor, para el caso de 29^14 hemos utilizado 2, y ¿para el caso de 29^14^22? obviamente 3 interruptores, el resultado puede ser guardado en un map<long long, int> mapa que tenga el mimino número de interruptores usados para una configuracion determinada osea mapa[29^14^22]= min(mapa[29^14^22], 3);ahora que tenemos esto .. si por ejemplo tenemos mapa1[10101]=3 que fue resultado del primer subconjunto, podemos ver si podemos llegar a 11111 con la ayuda del resultado del otro subconjunto es por eso que se buscaria un mapa2[01010](recuerde que si hacemos 10101^01010 = 11111(el objetivo!!)), si este existe pues simplemente se hace resp = min(resp , mapa1[10101]+mapa2[01010]), finalmente hacemos esto con todos los elementos de mapa1 y damos como respuesta resp.

Espero que haya sido de su agrado este contest, y recuerden que si tienen alguna sugerencia, algo que no se entendió o una mejor idea pueden escribirnos a

http://codebreakerscorp.foroperu.org/concursos-f4/aqp-training-4-2011-t35.htm#43

De paso eh subido los códigos aceptados de cada problema.

Finalmente decirles que están invitados al próximo contest, ahora tengo entendido que toca domingo por la noche de la próxima semana, espero su participación.