AQP TRAINING #5 – 2011 finalizado!

Posted: December 12, 2010 in AQP Contest!

Hola a todos, AQP Training 5 ha finalizado! felicitamos a los ganadores y a todos los que participaron de este contest,

1. a20025122 ( Shinta )

2. Hamlet ( Hamlet_fiis )

3. Trulo ( Trulo )

A. Prairie Dogs IV

Categoria: Ad hoc

Los que participamos en el entrenamiento onsite del dia viernes nos enfrentamos con un problema muy parecido a este y para  resolverlo se tenia que tener en cuenta los siguientes puntos:

  • Los números en todas la iteraciones empiezan en el cuadrado de algún el numero impar ( N^2 ) y terminan en el cuadrado del numero impar siguiente (  (N+2)^2 )
  • Sea P  la diferencia entre los cuadrados ( P = (N+2)^2-N^2 ), este se divide en cuatro intervalos que tiene recorridos diferentes: de arriba hacia abajo, de derecha a izquierda, de abajo hacia arriba y de izquierda a derecha.

Una de la formas de resolver este problema era encontrar la iteración a la que pertenece la consulta y simular la cuenta hasta encontrar la coordenada que nos pide, entonces imprimir el contador.

B. Grouping Problem

Categoria: Dynamic Programming, Depth First Search, ya que el N es muy pequeño se puede resolver con fuerza bruta.

El problema nos pide dividir un grupo de personas en dos equipos tal que la diferencia de pesos entre los equipos sea mínima. Una de las formas de resolver este problema usando programación dinámica es encontrar la máxima suma menor o igual a un numero, que en este caso seria la mitad del peso total. El resultado del DP seria el peso de uno de los equipos y la respuesta seria la diferencia entre el peso de este equipo y el peso del resto de personas.

Este problema es muy parecido al problema de la mochila: http://en.wikipedia.org/wiki/Knapsack_problem

C. Homework

Categoria: Greedy

Para minimizar la sumatoria debemos tener claro que mientras mas peso/unidad de tiempo tenga un problema su costo sera mas elevado, asi que greedy is good! ordenamos los problemas de acuerdo al criterio explicado y hallamos es costo total para terminar los problemas.

D. Ancestor

Categoria: Depth First Search

Ya que el numero de queries puede ser muy grande ( N<100000 ) el método trivial ( visitar todos los ancestros del nodo b ) es demasiado ineficiente. Una de las forma de resolver este problema requiere tener en consideracion la siguiente propiedad:

a es ancestro de b si y solo si a es visitado antes que b en preorden y es visitado después de b en postorden

Haciendo DFS calculamos la posición de los nodos en preorden y postorden ( O(V+E) ) y las consultas son atendidas en O(1) chekando la propiedad anteriormente descrita.

Un tutorial de grafos ( incluye DFS ) http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2

E. Card Game

Categoria: Maximum Bipartite Matching

Este problema consiste en hallar el ciclo de cadenas con el mayor peso, donde el peso entre dos cadenas es determinado por el sufijo en orden inverso mas grande de la primera cadena que es igual a algún prefijo de la segunda cadena.

El maximo ciclo puede hallarse a partir máximo matching en un grafo bipartito donde el lado izquierdo y derecho del grafo tienen todas las cadenas, y el peso de las aristas es hallado como explique anteriormente.

El problema de máximo matching en grafos bipartitos puede resolverse con KM, la explicación del algoritmo la pueden ver aqui:

http://algorithack.blogspot.com/2008/08/km-algorithm-solving-maximum-weighted.html

F. Im telling the truth

Categoria: Min Cost Max Flow

En este problema puede ser modelado como un problema de flujos, asi que el reto esta en construir el grafo correctamente:

  1. Por un lado tenemos la fuente conectada a los intervalos ( cada intervalos representa la respuesta de 1 estudiante por lo cual la arista tendra capacidad 1  y costo 0 ).
  2. Ya que los intervalos presentan solapamiento debemos procesarlos. Para ello ordenamos los puntos ( inferior y superior de cada intervalo ) y creamos nuevos intervalos los cuales no tienen solapamiento.
  3. Conectamos los intervalos originales a los creados con capacidad 1 y costo igual a la diferencia entre el numero de intervalos creados y la posición del intervalos actual ( esto para dar prioridad a los intervalos que son mayores lexicograficamente )
  4. Finalmente creamos aristas entre los nuevos intervalos y el sumidero con capacidad igual al tamaño del intervalo y costo 0.

El libro de Jungnickel es muy bueno para aprender flujos y todo lo relacionado a grafos.

Las soluciones de (ACed) del los problemas las pueden ver aqui:

http://code.google.com/p/codebreakerscorp/source/browse/#svn/trunk/5

Comments
  1. Hamlet says:

    Buena shinta .. feliz cumple

  2. Shinta says:

    gracias hamlet =P, mmm, tengo una duda, hice la E con max cost max flow, al estilo hungarian, y me da WA. ¿Hay una caso especial para considerar?

    • Hola Shinta,
      Me parece que no hay casos especiales en este problema, no tengo idea de pq no te haya salido con el algoritmo húngaro ( he hecho pocos problemas de este tipo ) , lo hice con KM y no tuve problemas🙂,

  3. Shinta says:

    Me parece que la explicación de la C no es satisfactoria. Lo digo porque se usa una técnica que es usada en otros problemas más complejos para que sean simples. Aquí la expongo:
    Queremos hallar una permutación de las tareas de manera que el valor de la función sea mínima. Entonces, tengamos dicha permutación de elementos
    1, 2, 3, 4, 5, 6, ….., i, i+1, …., n-1, n

    Al ser esta permutación óptima, al intercambiar los elementos i y i+1, el valor de la función es peor o igual al actual. Entonces tenemos:
    —————– i, i+1 —————
    Sea T el tiempo que se demoró en llegar a la tarea i, entonces la contribución de (i, i+1) para la fórmula es
    A = (T + t[i]) * w[i] + (T + t[i] + t[i + 1]) * w[i + 1]

    Si intercambiamos tenemos
    —————– i+1, i —————-
    El T es el mismo en este caso y tenemos esta contribución
    B = (T + t[i + 1]) * w[i + 1] + (T + t[i] + t[i + 1]) * w[i]

    Cabe notar que la contribución de todos los otros elementos no ha cambiado, sólo los de (i, i+1).
    Sabemos que B >= A, porque A es óptimo, entonces, despejamos la inecuación y tenemos
    C : t[i + 1] * w[i] >= t[i] * w[i + 1]

    Notamos ahora que dicha expresión es similar a lo que se dijo en el análisis del problema C arriba, y además que T desapareció. De esta manera ya sabemos que si C es verdadero, no debemos cambiar dos elementos consecutivos; por lo tanto, si C es falso, sí debemos cambiar. Así, tenemos la función de comparación

    comp: t[i + 1] * w[i] < t[i] * w[i + 1]

    Ahora, acá estamos intercambiando dos elementos consecutivos; entonces, para ordenar la permutación inicial, podríamos usar bubble sort, pero todos sabemos que quick sort es equivalente a bubble sort. Así que lo podemos usar.

    Espero que este análisis les haya servido.🙂

    • Chévere el análisis, he aprendido algo nuevo, cuando lo hice pense que era un greedy simple ( de hecho en el INTERCON 2010 vino un problema igualito ), se agradece el tutorial :D….

    • interesante análisis, a veces aplico algoritmos sin saber porque funcionan, pero ahora veo un poco mas claro cual es su base matemática🙂 , al menos sobre este tipo, gracias.

  4. Trulo says:

    Hola a todos. Los felicito por esta interesante iniciativa, los problemas de este último contest(no he participado en versiones anterirores) estuvieron muy entretenidos.

    Saludos.

  5. Trulo says:

    Respecto al problema A, considerando las constraints, se podía también precalcular(considerando un offset de +1000 en cada dirección de un array 2D para evitar indexación con negativos) todo el tablero, para después responder las querys en O( 1 ).

    Se puede ir recorriendo la espiral con las siguientes observaciones:

    -Las direcciones se alternan así: derecha,abajo,izquierda,arriba.
    -Cada 2 cambios de direcciones, se incrementa el “paso”(cantidad de elementos que recorreremos en la dirección actual) en 1.

  6. Shinta says:

    El problema A lo hice como Trulo lo dije, corrió bien rápido. Sobre el problema F, yo lo hice con maximum bipartite matching, y luego un greedy para generar la solución. El greedy usa también un bipartite matching. Por cierto, ¿alguien tiene AC en la E? xd

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s