El algoritmo de búsqueda que se explicará a continuación es Depth First Search ( DFS ) se explicará el algoritmo de manera similar a como se hizo BFS, proponiendo problemas y otorgando códigos del algoritmo en si.

Descripción

El algoritmo DFS posee varias aplicaciones la mas importante es para problemas de conectividad,  si un grafo es conexo, detectar ciclos en un grafo,  numero de componentes conexas,  etc y es bastante útil en otro algoritmos como para hallar las componentes fuertemente conexas en un grafo ( Algoritmo de Kosaraju, Algoritmo de Tarjan), para hallar puntos de articulación o componentes biconexas ( puentes ),  para recorrido en un circuito o camino euleriano, topological sort, flood fill y otras aplicaciones.

Como trabaja

DFS va formando un árbol al igual que BFS pero lo hace a profundidad. Existen dos formas de hacer el recorrido una es usando una Pila y otra de manera recursiva:

Usando Stack

El concepto es el mismo que BFS solo que se cambia la Cola por una Pila, el proceso es como sigue: visitar el nodo inicial y ponerlo en la pila, ahora para ver los siguientes nodos a visitar sacamos el nodo tope de la pila y vemos sus adyacentes, los que no han sido visitados los insertamos en la pila. El proceso se repite hasta que la pila se encuentre vacía ( se han visitado todos los nodos ).

Algoritmo en pseudocodigo:

1  método DFS( origen):
2      creamos una pila S
3      agregamos origen a la pila S
4      marcamos origen como visitado
5      mientras S no este vacío:
6          sacamos un elemento de la pila S llamado v
7          para cada vertice w adyacente a v en el Grafo: 
8              si w no ah sido visitado:
9                 marcamos como visitado w
10                 insertamos w dentro de la pila S

Código en C++:  Algoritmo DFS usando Stack

Usando Recursión

Usar la recursión es mucho mas fácil y ademas muy útil, es la forma mas usada en la solución de problemas con este algoritmo.

Algoritmo en pseudocódigo:

1  método DFS( origen):
2      marcamos origen como visitado 
3          para cada vertice v adyacente a origen en el Grafo: 
4              si v no ah sido visitado:
5                 marcamos como visitado v
6                 llamamos recursivamente DFS( v )  

Tomemos como ejemplo el siguiente grafo no dirigido:


Al igual que con la pila requerimos un nodo inicial, de manera recursiva llamamos a los adyacentes del nodo inicial, de esta forma se puede ver si llamamos inicialmente a “1”:

Inicial “1”: marcamos “1” como visitado, sus adyacentes son “2”,  “3” y “5”.

  • Visitados : 1.
  • Adyacentes de 1: 2 , 3 , 5

En la llamada recursiva ira el primero insertado en la lista de adyacencia, en este caso “2”, marcamos como visitado. Ahora el inicial es “2”, sus adyacentes son “1” , “4” y “5”.

  • Visitados: 1 , 2
  • Adyacentes de 2: 1, 4 , 5

Evaluamos el 1ero de la lista que es “1” pero ya fue visitado por lo tanto sigo con el siguiente, en este caso “4” , marcamos como visitado. Ahora inicial es “4”, sus adyacentes son “2”.

  • Visitados: 1 , 2 , 4
  • Adyacentes de 4: 2

Tocaria el nodo 2 pero ya fue visitado termina la recursion por ese lado. El siguiente adyacente de “2” es “5”. Ahora inicial es “5”, marcamos como visitado, sus adyacentes son “1” y “2”.

  • Visitados: 1 , 2 , 4 , 5
  • Adyacentes de 5: 1 , 2

Igual que con nodo “4” sus adyacentes han sido visitados por lo tanto terminamos la recursion por el nodo “2”.

El nodo actual es “1”, sus adyacentes eran “2”, “5” y “3”, estabamos evaluando por “2” pero ya terminamos el siguiente es “5” el cual ya fue visitado, continuamos con “3” este no fue visitado, marcamos como visitado, vemos sus adyacentes “1”.

  • Visitados: 1 , 2 , 4 , 5 , 3
  • Adyacentes de 3: 1

Como nodo “1” ya fue visitado entonces termina la recursión y termina el recorrido DFS. Como se puede observar el orden en que fueron visitados los nodos es el recorrido DFS del grafo.

Posibles Paths en un grafo

Otra ayuda importantisima del algoritmo recursivo es que nos permite hallar todos los posibles paths( rutas) de un nodo inicial a otro final, ello lo conseguiremos usando backtracking dentro del algoritmo:

Algoritmo en pseudocódigo:

1  método DFS( origen,final):
2      marcamos origen como visitado 
3      recuperar el path si se llego a final
4          para cada vertice v adyacente a origen en el Grafo: 
5              si v no ah sido visitado:
6                 marcamos como visitado v
7                 llamamos recursivamente DFS( v )
8      marcamos origen como no visitado

Codigo C++:  Algoritmo DFS usando Recursion

Ejemplo Aplicativo:

Tengamos un juego de dominos donde si hago caer uno domino, todos los demas dominos que siguen a este caerán. Dado el numero de dominos “n”, el estado del juego en la forma “x y” ( si domino “x” cae entonces domino “y” tambien caerá) , la cantidad de consultas a realizar, cada consulta sera el numero del domino el cual yo impulsaré. El problema me pide hallar cuantos dominos caeran a partir del domino que yo impulsé.

Supongamos la entrada:

8 6 3  ( 8 dominos, 6 enlaces de dominos y 3 consultas  )

1 2

2 5

5 3

4 3

6 7

7 8

1

4

6

Solución

Declaremos nuestras variables globales:

vector<int> ady[ MAX ];                     //lista de adyacencia
int total;                                  //la cantidad total de dominos que caerán
bool visitado[ MAX ];                       //arreglo de dominos caidos

Modelemos el problema como un grado dirigido:

Ahora vemos cada consulta, la primera nos indica que impulsaré el domino numero 1, entonces al hacer ello los dominos que caerán serán 1 -> 2 -> 5 ->3, debo retornar 4 la cantidad de dominos caidos. Para la segunda consulta caéran solamente 4->3, y finalmente para 6 caerán 6->7->8

La solución lo relizaremos con un DFS como sigue:

void dfs( int u ){                          //domino origen
    total++;                                //aumento en mi respuesta la caida de un domino
    visitado[ u ] = true;                   //domino "u" cayo
    for( int v = 0 ; v < ady[ u ].size(); ++v ){ //verifico los demas posibles domino que caeran si impulso "u"
      if( !visitado[ ady[ u ][ v ] ] ){         //si el domino adyacente no cayó entonces es el siguiente a evaluar
         dfs( ady[ u ][ v ] );               //recursivamente veo que dominos caeran a partir del adyacente de "u"
      }
    }
}

Codigo C++: DFS Ejemplo – Domino

Componentes Conexas

Algun problema puede ser que nos pida hallar la cantidad de componentes conexas, supongamos el siguiente grafo no dirigido:

La cantidad de componentes conexas es 2. El problema puede ser resuelto de la siguiente manera:

Evaluamos todos los vertices posibles y los tomamos como origen aquellos no visitados:

for( int i = 1 ; i <= V ; ++i ){    //recorremos todos los posibles vertices
    if( !visitado[ i ] ){          //si alguno no fue visitado tenemos una componente a partir de ese nodo
       dfs( i );                  //recorremos a partir de nodo i todo el grafo que se forma
       total++;                   //incrementamos cantidad de componentes
    }
}

Usamos el algoritmo estandar DFS para cada recorrido:

void dfs( int u ){
    visitado[ u ] = true;
    for( int v = 0 ; v < ady[ u ].size(); ++v ){
       if( !visitado[ ady[ u ][ v ] ] ){
           dfs( ady[ u ][ v ] );
       }
    }
}

Codigo C++: DFS Ejemplo – Conectividad

A continuación algunos problemas que pueden ser resueltos con este algoritmo:

JUEZ UVA:

459 – Graph Connectivity

Varios Problemas se encuentran en el UvaToolkit colocando en el buscador DFS

JUEZ PKU:

2245 – Lotto

TOPCODER:

SRM 371: DIV 2 – 1000  FloodRelief

SRM 407: DIV 2 – 500 CorporationSalary

SRM 435 : DIV 1 – 250 CellRemoval

Se irán agregando mas adelante mas problemas de otros jueces asi como más aplicaciones de DFS.

Resumen de códigos:

Código en C++:  Algoritmo DFS usando Stack

Código en C++:  Algoritmo DFS usando Recursion

Código en C++: DFS Ejemplo – Domino

Código en C++: DFS Ejemplo – Conectividad

Por: Jhosimar George Arias Figueroa

[Saludos, les escribe Jhosimar Arias autor de los tutoriales aqui mostrados y parte de algunos posts. Escribo este post para hacerles llegar mi blog propio:

http://jariasf.wordpress.com/

Traslade mis 2 tutoriales de DFS y BFS, asi mismo agregue algunas cosas a ambos como mas imagenes en el caso de DFS y un punto mas en el BFS. Posteare mas tutoriales en mi propio blog asi como soluciones de problemas de jueces que parezcan interesantes.]

AQP Training Contest #7 finalizado!

Posted: February 27, 2011 in AQP Contest!

AQPTraining Contest #7 ah finalizado y agradecemos a los participaron del contest, a continuación presentamos el analisis de los problemas propuestos en el contest:

PROBLEMA A: Cola

El problema puede ser resuelto simplemente simulando el 1er método dado en el enunciado del problema. Ello es iterando sobre el numero de botellas e ir restando 3 mientras se tenga mas de 3 botellas, a la vez que incrementamos en 1 la respuesta. Si el número final de botellas restantes es 2 entonces podemos tomar prestado una botella para maximizar el número de botellas, por lo tanto incrementamos en uno nuestra respuesta.

PROBLEMA B: Count DePrimes

Dado dos numero a y b, hallar la cantidad de numeros entre a y b ( inclusive ) cuyos factores primos suman un numero primo,Si un numero primo es factor de algun numero n, entonces p*k = n, para algun numero primo p, y algun k. Si el valor de k varia obtendremos otros numero de los cuales p es factor es decir los multiplos de p.Para obtener la suma de factores primos de un numero n, debemos sumar todos los numeros primos tal que p * k = n, Una forma de hacer es iterar sobre todos los numeros primos y sumar este numero primo a sus multiplos en un array.

PROBLEMA C: Sumsets

Una forma de resolver el problema es usando fuerza bruta con 4 for anidados ( O( n ^4 ) ). Primeramente almacenamos los números de ingreso en un arreglo y lo ordenamos. Luego hacemos los 4 for de la siguiente manera, el 1ero tendrá el ultimo elemento del arreglo e ira decreciendo en tamaño, este será el valor de “d” por ser el mayor. Los otros 3 for representaran el valor de “a”, “b” y “c”. Por lo tanto dentro del ultimo for quedaría la comparación de si “a + b + c = d” retornar el valor de “d”, de otro modo seguir iterando. Si al final no se hallo resultado imprimimos “no solution”.

PROBLEMA D: LCM

Dado un n, encontrar el LCM de todos los enteros positivos menores o iguales que n, ya que el numero puede ser muy grande, imprimir el ultimo digito diferente de cero.Si representamos dos numero como el producto de la potencias de sus factores primos, su lcm sera:

lcm ( a, b ) = p1 ^ max ( e1_1, e1_2 ) * p2 ^ max ( e2_1, e2_2 ) * p3 ^ max ( e3_1, e3_2 ) * ..

Esta definicion se puede extender para todos los valores menores o iguales que n:

lcm ( 1..n ) = p1 ^ max ( e1_1, .., e1_n ) * p2 ^ max ( e2_1, .., e2_n ) * ..

Para hallar el maximo exponente que puede tener cada primo en el rango 1..n es equivalente a encontrar el maximo k tal que p ^ k <= n, ya que p ^ k * m = n, para algun m.
Ya que solo queremos el ultimo digito diferente de cero, debemos evitar multiplicar por 10, esto los conseguiremos modificando los exponentes del 2 y 5,

lcm ( 1..n ) = 2 ^ ( max_e2 – k ) * .. * 5 ^ ( max_e5 – k ) , donde k = min ( max_e2, max_e5 ).

El resultado sigue siendo grande asi que debemos usar modulo

PROBLEMA E: Light and Transparencies

Para este problema el eje “y” no será de ayuda, solo usaremos el eje “x”. En cada ingreso podemos almacenarlo en una estructura Segmento que contenga el “x” menor, “x” mayor y el valor “r”. También en otro vector podemos almacenar todos los puntos del eje “x” y luego ordenar dicho vector para iniciar el recorrido. Casos –inf +inf siempre se imprimirá 1, para los demás recorremos el vector de valores “x” y vemos a que segmentos pertenece dicho valor, puede ser una función como sigue:

double segment( vector<Segment> s , double x ){
     double value = 1.0;
     for(int i = 0 ; i < s.size() ; ++i )
         if( s[ i ].xmin <= x && x < s[ i ].xmax ) value *= s[ i ].r;
     return value;
}
PROBLEMA F Dropping balls

Dadas las indicaciones para recorrer una arbol binario completo, el problema nos pide hallar el numero del nodo hoja donde caera la i-esima bola, de las indicaciones del recorrido nos damos cuenta que la i-esima posicion en el arbol padre es la (i/2) posicion de algunos de sus hijos, la eleccion del hijo depende de las pardidad del indice, ya que solo escogemos 1, la complejidad se reduce a log(n) ( solo buscamos en una del las mitades ).

int solve ( int cur_deep, int max_deep, int i, int cur ) {
	if ( cur_deep >= max_deep ) return cur;
	return i%2? 
	solve ( cur_deep + 1, max_deep, i/2, 2*cur + 2 )
	: solve ( cur_deep + 1, max_deep, i/2, 2*cur + 1 );
 Read the rest of this entry »

TOPCODER SRM 497

Posted: February 11, 2011 in TopCoder

El SRM 497 se llevo a cabo este 10 de febrero. En cuanto a la división 1 el primer lugar lo obtuvo Petr y por pocos puntos menos ACRush en segundo lugar y en la división 2 el ganador fue el nuevo participante HDU_Lost. En cuanto a participaciones del Perú la mayoría pudo realizar el problema de 250 (Div 2), el problema de 500 (Div 2) fue el mismo que el 250 (Div 1) y hubo participantes tanto en Div 1 como en Div 2 que pudieron resolverlo.

A continuación procederemos a mostrarles un detalle de las soluciones de la división 2. Se recomienda leer antes los enunciados para mejor entendimiento, las soluciones serán dadas en Java:

Problema de 250 Puntos

Input:

  • Arreglo o vector de enteros, que viene a ser el tamaño de los objetos, ( Java – int [ ] sizes, C++ – vector<int> sizes).
  • Una cadena con caracteres ‘A’ y ‘R’, si se tiene ‘A’ los objetos de ese tamaño son aceptados sino son rechazados. ( Java – String outcome, C++ – string outcome)

Output

Si se lee el enunciado quizás no este bastante claro pero lo que se pide es encontrar el valor de A y B que son el mínimo y máximo valor de la cadena que contiene ‘A’ consecutivos, si existe un ‘R’ en medio de esa cadena de ‘A’ entonces retornar un arreglo vació. De otro modo retornar el valor de A y B en un arreglo.

Ejemplos:

0)

sizes = {3, 4, 5, 6, 7}

outcome = “AAAAA”

En este caso se tiene puras ‘A’ por ello el mínimo y máximo será 3 y 7 entonces

Retorna: {3, 7 }

1)

sizes = {3, 4, 5, 6, 7}

outcome = “AARAA”

En este caso vemos que hay una ‘R’ en medio de lo que vendría hacer la cadena de ‘A’ consecutivas por ello

Retorna: { }

2)

sizes = {3, 4, 5, 6, 7}

outcome = “RAAAA”

En este caso la única ‘R’ se encuentra al inicio y no interviene en la cadena de ‘A’ consecutivas por lo que el mínimo y máximo es 4 y 7

Retorna: {4, 7}

Solución

Una forma es poner ambos sizes[ i ] con su respectivo outcome[ i ] en una vector y ordenarlo por sizes. De esta manera simplemente bastaria verificar si antes de una ‘R’ y después de una ‘R’ existen ‘A’ entonces se retornaría vació, de otro modo el mínimo y máximo.

Otra forma es sin necesidad de ordenar y esa el la que les mostraré, lo que se hace es hallar el valor mínimo y máximo para ‘A’ eso en una iteración. Luego en otra iteración si tengo un ‘R’ veo si esa en el rango de ese mínimo y máximo ( if( sizes[ i ] >= min && sizes[ i ]<= max) ) si se cumple retorno vacío, de otro modo retorno el arreglo con máximo y mínimo.

Adjunto mi código: Problema 250 – Filtering

Problema de 500 Puntos – 250 Puntos (DIV I)

Input:

  • Una cadena con caracteres ‘I’ y ‘D’ referenciando al incremento y decremento respectivamente. ( String signature- string signature )

Output:

  • La permutación menor lexicograficamente que cumpla con la cadena de ingreso dada.

Ejemplos:

0)

signature = “IIIII”

En este caso todos son incremento por lo que la permutación debe retornar

Retorna : { 1, 2 , 3 , 4 , 5 , 6 }

1)

signature = “DI”

En este caso tenemos un decremento y un incremento por lo que retorna.

Retorna: { 2 , 1 , 3 }

2)

signature = “DIDDID”

En este caso lo primero que tenemos es decremento por lo que tenemos { 2, 1 } luego un incremento por lo que tenemos { 1, 5 } luego 2 decrementos ello seria { 5 , 4 , 3}

Luego un incremento {3 , 7 } finalmente un decremento { 7, 6 }

Retorna: {2, 1, 5, 4, 3, 7, 6}

Solución

Para obtener la permutación lexicograficamente menor simplemente es ubicar la permutación usando los enteros desde 1 hasta n.

La forma en como realice el problema es primeramente asumir que mi respuesta estará compuesta de puro incremento ( ‘I’ ), ello me ayuda a solo verificar los decrementos ya que para incrementos cumple. Por lo que mi arreglo de respuestas tendrá valores por ejemplo para el último caso ejemplo:

signature = “DIDDID”

resp = { 1 , 2, 3 , 4 , 5, 6 , 7}

Ahora itero sobre signature si encuentro un decremento ‘D’, cuento cuantos decrementos consecutivos se tiene a partir del indice actual de signature:

while( j < signature.length() && signature.charAt( j ) == 'D' ) j++;

Una vez obtenido la cantidad de decrementos tengo que invertir esa subarreglo para que todos cumplan. Para ello si tengo por ejemplo un arreglo { 3 , 4 , 5 , 6} para invertirlo simplemente itero hasta la mitad y cambio el primero con el ultimo, el segundo con el penúltimo y así sucesivamente. Hay que tener en cuenta que ese subarreglo se encuentra en cualquier posición inicial en “i” ( i = indice actual de signature ) y terminando en “j” por lo que para ver el tamaño de ese subarreglo será: ( j – i + 1 ).

Finalmente como ya use los decrementos consecutivos actualizo i = j.

Para el ejemplo, en la primera iteración tengo un decremento ‘D’, j = 1, i = 0

  • Tamaño = j – i + 1 = 1- 0 +1 = 2
  • Subarreglo = { 1 , 2 }
  • Mitad y cambio = { 2 , 1}
  • resp = { 2 , 1 , 3 , 4 , 5 , 6 , 7} actualizo i = j = 1

Iteración 2: Incremento, no ocurre nada.

Iteración 3: Decremento, i = 2, se tiene 2 decrementos consecutivos, j = 4

  • Tamaño = j – i + 1 = 4 – 2  + 1 = 3
  • Subarreglo = { 3 , 4 , 5 }
  • Mitad y Cambio = { 5 , 4 , 3}
  • resp = { 2 , 1 , 5 , 4 , 3 , 6 , 7 } actualizo i = j = 4

Iteración 4: Incremento, no ocurre nada.

Iteración 5: Decremento, i = 5, j = 6

  • Tamaño = j – i + 1 = 6 – 5  + 1 = 2
  • Subarreglo = { 6 , 7 }
  • Mitad y Cambio = { 7, 6 }
  • resp = { 2 , 1 , 5 , 4 , 3 , 7 , 6 } actualizo i = j = 6

Entonces retorno la respuesta final = { 2 , 1 , 5 , 4 , 3 , 7 , 6 }

Adjunto mi código: Problema 500 – PermutationSignature

Problema de 1000 puntos

Input

  • Una cadena conteniendo caracteres ‘a’ – ‘z’ ( Java – String S, C++ – string s).

Output

  • El menor numero de cambios ( agregar, borrar o cambiar un carácter) para que la cadena S sea cuadrada ( Es cuadrada si es la concatenación de dos copias del mismo string ).

Ejemplos

0)

S = “abcdabgcd”

En este caso para que sea cuadrada basta con borrar la “g”, tendríamos “abcdabcd”

Retorna: 1

1)

S = “abcdeabce”

En este caso para tener el menor numero de pasos basta con insertar la “d” entre la “c” y “e”, teniendo “abcdeabcde”

Retorna: 1

2)

S = “abcdeabxde”

En este caso es necesario un cambio de la letra “x” por la letra “c”, teniendo “abcdeabcde”

Retorna: 1

Solución:

Este problema es bastante sencillo si se conoce el algoritmo de programación dinámica “Edit Distance”, más específicamente la distancia de Levenshtein. Ya que es simple aplicación sin modificación del algoritmo. El algoritmo recibe dos cadenas para realizar los pasos de agregar o borrar o cambiar caracteres. En este caso tendremos que iterar sobra la cadena S desde i hasta N ( longitud de S) e ir verificando el EditDistance de substrings de S(0,i) y S(i). Obteniendo el mínimo que es lo que nos pide.

Una explicación breve del algoritmo:

Dado el string inicial compuesto por los caracteres S1,S2,S3,….,Si y un string final compuesto por los caracteres  T1,T2,T3,….,Tj , defimos a D(i,j) al minimo número de operaciones necesarias para transformar S en T, tomando en cuenta hasta el caracter i de S y hasta el caracter j de T.

Dicho esto la formula recursiva seria:

Donde:

  • DC: Costo de la operación de eliminación de un caracter.
  • IC: Costo de la operación de inserción de un caracter.
  • SC: Costo de la operación de sustitución de un caracter.

Generalmente DC, IC, y SC toman el valor de 1.

EJEMPLO

Hallar el mínimo número de operaciones para convertir el string “kitten” en “sitting”. Utilizando la formula recursiva a modo de programación Dinámica llegariamos a construir  la siguiente tabla:

Para lo cual el minimo de operaciones seria 3, siendo estas:

  1. kitten → sitten (sustitución de ‘s’ por ‘k’)
  2. sitten → sittin (sustitución de ‘i’ por ‘e’)
  3. sittin → sitting (inserción de ‘g’ al final).

Adjunto mi código: Problema 1000 – MakeSquare

Jhosimar George Arias Figueroa

FELIZ NAVIDAD!

Posted: December 24, 2010 in Otros

Holas a todos, bueno por motivos de la navidad y año nuevo y luego por lo de final de semestre en la UNSA, es que comunicamos a todos que los AQPTrainingContest serán suspendidos hasta mediados de Enero, para cuando la mayoria tenga tiempo de entrar, no obstante los animamos a que no dejen de prácticar y meterse a cuanto contest de programación vean. Mientras mas practiquen, mayor cantidad de problemas podrán resolver y en menor cantidad de tiempo, pero si lo dejan, el reponerse no es muy fácil, lo decimos por experiencia propia.

Por otro lado apenas tengamos tiempo, publicaremos mas tutoriales, de tal forma que todos mejoremos, y logremos clasificar a un mundial, y ya saben cualquier duda pueden hacerla llegar al foro, nosotros les ayudaremos con gusto.

Finalmente les deseamos una feliz navidad, que la pasen bien en familia comiendo su panetón xD y programando😀

keep solving.

Holas a todos AQP Training #6 ah finalizado!! queremos agradecer de antemano a nuestro problemsetter Walter Erquínigo por haber preparado este contest y a todos los que participaron. Tenemos unas palabras de Walter:

Los resultados fueron mejor de lo que esperaba, felicito a TheGoldenEagle que ganó brutalmente en ambas divisiones. A Digberth y a Ziklon por haber hecho también 5 problemas quedando en segundo y tercer puesto de Div2. En Div1 felicito también a jpenam por haber hecho 4 problemas quedando segundo y a Jhosimar por quedar tercero con 3 problemas. Espero que les haya gustado el problem set y me esmeré buscando problemas que enseñen cosas importantes.🙂

A continuación presentaremos el analisis otorgado por Walter para ambas divisiones:

DIVISION 2

Stamps:

Problema bien simple: un greedy en el que primero ordenamos de mayor a menor y vemos el menor índice tal que la suma acumulada hasta dicho índice es mayor o igual a lo que queremos. En caso contrario, retornamos imposible.

Box of Bricks:

Otro problema simple pero que requiere pensar algo. Una vez que sabemos el número total de fichas F y el número de pilas P, ya sabemos cuántas fichas habrá finalmente en cada fila  T = F / P. Luego, revisamos cada pila p, que tiene X[p] fichas. Si X[p] < T fichas, entonces entrarán a él T – X[p] fichas; en caso contrario, saldrán de él X[p] – T fichas. Como cada ficha que sale de una pila tiene que entrar a otra pila, sabemos que la sumatoria  de T – X[p], para toda pila p que recibe fichas, es igual a la sumatoria de X[p] – T, para toda pila p que entrega fichas. Por lo tanto, la respuesta es la sumatoria de los X[p] – T, o la sumatoria de los  T – X[p].

Friends:

Problema básico e importante, es simplemente un DFS para contar en número de componentes conexos en un grafo, donde los vértices son las personas y las aristas son las relaciones de amistad. Incluyo un código:

#include<cstring>
#include<vector>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

vector<int> E[101];
bool seen[101];

void dfs(int u){
   if(seen[u]) return;
   seen[u] = true;
   for(int i = 0; i < E[u].size(); i++)
       dfs(E[u][i]);
}

int main(){
   int t; cin >> t;
   while(t--){
       int n, m;
       cin >> n >> m;
       for(int i = 0; i < n; i++) E[i].resize(0);
       while(m--){
           int a, b; scanf("%d %d", &a, &b);
           a--; b--;
           E[a].push_back(b); E[b].push_back(a);
       }
       int res = 0;
       memset(seen, 0, sizeof seen);
       for(int i = 0; i < n; i++) if(!seen[i]) dfs(i), res++;
       cout << res << endl;
   }
}

 
Bitwise reverse:

Primero se debe hallar el bit con mayor peso, y a partir de él, hacer un reverse de todos los otros bits de menor peso. Incluyo código.

#include<cstring>
#include<vector>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){

    int n;
    while(scanf("%d", &n) == 1 && n){
           int last;
           for(int i = 0; i < 30; i++)
           if(n & (1 << i)) last = i; //hallamos el bit más pesado que esté prendido
           int res = 0;

           for(int i = last, j = 0; i >= j; i--, j++){
                  int bi = (n & (1 << i)) != 0; //booleano [0, 1] que representa el valor del bit
                  int bj = (n & (1 << j)) != 0;
                  res |= bj << i;
                  res |= bi << j;
           }
           cout << res << endl;
    }
}
Marbles in Three Baskets:

Este tal vez es el problema más difícil de este Div2. Es un bfs con vértices de 3 dimensiones.
Normalmente en un bfs un vértice es representado por un número, teniendo así 1 dimensión; sin embargo, en este caso, un vértice es representado por 3 números (los contenidos en los 3 recipientes), teniendo así 3 dimensiones. Por lo tanto, para trabajar con un “arreglo” de distancias para el bfs, tendremos un arreglo de 3 dimensiones:

int distancias[N][N][N];
Y nuestra cola será un
queue<node> q;
donde node puede ser
struct node{
   int x, y, z;
   node(){}
};

Y dentro del bfs, como no podemos tener una lista o matriz de adyacencia, simulamos los envíos de contenido de un recipiente a otro, creando así otros estados válidos de recipientes. Esto es lo mismo que movernos por las aristas del grafo asociado, sólo que de manera implícita.

Y para hacer más fastidioso el proceso, tenemos que guardar una matriz de padres para reconstruir el camino. Añado el código por su importancia en el aprendizaje, dado que este tipo de problemas de caminos es frecuente

#include<set>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
struct node{
    int a[3];
    node(int x, int y, int z){
         a[0] = x;
         a[1] = y;
         a[2] = z;
    }
    node(){}
};

int main(){
    int a, b, c;
    int dist[60][60][60];
    node parent[60][60][60];
    while(scanf("%d %d %d", &a, &b, &c) == 3){
          memset(dist, -1, sizeof dist);
          dist[a][b][c] = 0;
          queue<node> cola;
          node begin(a, b, c);
          cola.push(begin);
          bool listo = false;
          int fin = (a + b + c) / 3;

          if((a + b + c) % 3 == 0) //si existe solución
          while(!cola.empty()){
               node cur = cola.front();
               cola.pop();
               bool sirve = true;
               for(int i = 0; i < 3; i++) if(cur.a[i] != fin) sirve = false;
                   if(sirve){
                       listo = true; break;
                   }

               for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) if(i != j && cur.a[i] >= cur.a[j]){
                   node next = cur;
                   next.a[i] -= cur.a[j];
                   next.a[j] += cur.a[j];
                   if(dist[next.a[0]][next.a[1]][next.a[2]] == -1){
                        dist[next.a[0]][next.a[1]][next.a[2]] = dist[cur.a[0]][cur.a[1]][cur.a[2]] + 1;
                        parent[next.a[0]][next.a[1]][next.a[2]] = cur;
                        cola.push(next);
                   }
               }
          }

          if(!listo){
              printf("%4d%4d%4d\n", a, b, c);
              printf("============\n");
          }else{
              node cur(fin, fin, fin);
              vector<node> pasos(1, cur);
              while(true){
                   if(cur.a[0] == a && cur.a[1] == b && cur.a[2] == c) break;
                   pasos.push_back(parent[cur.a[0]][cur.a[1]][cur.a[2]]);
                   cur = parent[cur.a[0]][cur.a[1]][cur.a[2]];
              }
              for(int i = pasos.size() - 1; i >= 0; i--)
              printf("%4d%4d%4d\n", pasos[i].a[0], pasos[i].a[1], pasos[i].a[2]);
              printf("============\n");
         }
    }
}
Super Square:

Junto con los problemas del DFS y del BFS son los problemas más importantes de este Div2.
El problema pide calcular n ^ n (mod 2006), o en otras palabras n^n % 2006.

Primero vale la pena mencionar dos importantes propiedas de teoría de números

(a + b) % mod = (a % mod  +  b % mod) % mod
(a * b) % mod  = (a % mod  *  b % mod) % mod

Osea, cuando tenemos que hacer operaciones de suma o producto, y al resultado tenemos que sacarle módulo, podemos primero sacarle módulo a los operandos y luego al resultado, de esta manera, siempre podemos trabajar con número pequeños, puesto que n ^ n es grande, pero n ^ n % 2006 es máximo 2005.

n puede ser hasta 10^8, por lo que hacer esto

long long res = 1; //uso long long porque soy paranoico cada vez que veo números grandes
 for(int i = 0; i < n; i++)
      res = res * n % 2006;

a pesar de ser correcto esto puede ser muy lento, dándonos así un TLE.

Un mejor análisis nos permite descubrir esto

a^(2n) = (a^n) ^ 2, dado que 2n es par
a^(2n+1) = a * a^(2n)  = a * (a^n)^2,  dado que 2n+1 es impar

Entonces, podemos hacer esto

typedef long long ll;
ll expmod(ll a, ll e){
   if(e == 0) return 1;
   ll x = expmod(a, e / 2);
   x = x * x % 2006;
   if(e % 2 == 1) x = x * a % 2006;
   return x;
}

Llamado fast modular exponentiation. Es un algoritmo logarítmico (porque el exponente decrece sucesivamente por un factor de 2), que halla lo que queremos. No es muy difícil verificar la correctitud del algoritmo. Este es un algoritmo IMPORTANTE para problemas de matemática.

DIVISION 1

Finding Nemo:

Problema sencillo, sólo se necesitan huevos porque a primera vista da miedo. Lo primero es describir el grafo asociado, para esto tendremos:

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool E[202][202][4];

Las dos primeras ĺíneas nos indican los diferencias de movimiento que haremos dentro de nuestro algoritmo de búsqueda. La tercera línea nos dice, si para la posición (x, y) la dirección (d), asociada a (dx[d], dy[d]), está libre o tiene un muro. De esta manera, cada que vez recibamos del input una pared, simplemente marcamos con false los E[x][y][d] respectivos.

Luego tenemos que asignar a la posición final objetivo (a, b), que tiene coordenadas decimales, una posición en el grid con coordenadas enteras. Con un poco de análisis y haciendo ejemplos en papel, se verifica que dicha posición final es (floor(a), floor(b)).

Finalmente, una vez descrito el grafo y hallado la casilla objetivo del grid, se procede a hacer un dijkstra o un bfs modificado para pesos 0-1. 

How many 0’s?:

Este problema tiene dos soluciones, la primera es un dp un poco largo y la segunda es un greedy. Explicaré el greedy.
Primero es importante notar la periodicidad de los números. Si sólo nos fijamos en el último dígito de todo número notamos:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 …
Y si ahora nos fijamos en los segundos dígitos tenemos:
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 …

Así, podemos hacer unos calculos con división y resto, para determinar el número de veces que aparece cada dígito en cada posición (primera posición, segunda, tercera …).
Nada muy complicado, sólo pensar un poco.

Mondriaan’s Dream:

Un DP clásico de nivel alto.
Definimos la recursión

f(mask, row, col) = suma de f(nmask, row, col + 1), para todo posible nmask
f(mask, n, 0) = mask == 0;

Tal que mask es lo siguiente:

                col
                [x] xxxxxxxx
row  xxxxx

Mask es un conjunto de bits, 1 o 0, tal que dice si un bloque está lleno o vacío. Ahora, para todas las columnas menores que col, dichas posiciones de la máscara indicarán el estado de dichas columnas en la fila row. Y para las columnas mayores a col, indicarán el estado de dichas columnas en la fila row – 1. Inicialmente considerando que la fila -1 es 0.

Pongo mi código:

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int n, m;
ll dp[12][12][1 << 12];
ll cuenta(int row, int col, int mask){
    if(col == m) return cuenta(row + 1, 0, mask);
    ll &res = dp[row][col][mask];
    if(row == n){
        if(mask == 0) return  1;
        else return  0;
    }

    if(res != -1) return res;

    if(mask & (1 << col)) return res = cuenta(row, col + 1, mask - (1 << col));

    res = 0;
    if(col + 1 != m) if((mask & (1 << (col + 1))) == 0) res = cuenta(row, col + 2, mask);
    res += cuenta(row, col + 1, mask | (1 << col));
    return res;
}

int main(){
    while(scanf("%d %d", &m, &n) == 2 && n + m){   
         memset(dp, -1, sizeof dp);   
         printf("%lld\n", cuenta(0, 0, 0));
    }
}

Este problema es de importancia vital.

Box of Bricks:

Explicado de Div2🙂

Seminar Room:

Un problema sencillo de 2-SAT. Haré primero un outline de lo que es 2-SAT.

Un problema de 2-SAT consiste en hallar una solución afirmativa para una ecuación de la siguiente forma:


(extraído de Wikipedia).

Así, 2-SAT se reduce a asignar valores true o false a cada X[i], de manera que la expresión total, la conjunción de disyunciones, nos de valor verdadero.
El algoritmo para esto son 2 pasos.

Paso 1: crear el grafo asociado

Notemos que (a or b) = (~a -> b) and (~b ->a)
Entonces, creamos dos vértices para cada variable, con lo que tendremos en el grafo un vértice para X[i] y un vértice para ~X[i], y según las disyunciones colocamos las aristas.

Ahora el problema se reduce a escoger una de dos opciones para cada variable. (X[i] = true, ~X[i] = false) o (X[i] = false, ~X[i] = true), de manera que en grafo nunca ocurra que true -> false. Si logramos asignar valores a todas las variables sin romper esa restricción, el problema ya está listo, porque cada arista será de la forma
true -> true
false -> true
false -> false
Y todas esas expresiones son válidas en la expresión matemática arriba.

Paso 2: verificar si existe solución

Ahora corremos un algoritmo de Strongly Connected Components y si para algún i, X[i] y ~X[i] están en el mismo componente, no existe solución; en caso contrario, sí existe solución.
Si X[i] y ~X[i] están en el mismo componente, entonces existe un camino de X[i] a ~X[i] y un camino de ~X[i] a X[i]. Por lo tanto, como uno de ellos debe ser true y el otro false, existe un camino true -> false, lo cual es inválido y no existe solución. Si no hay tal contradicción, siempre es posible hallar una solución, dado que, al comprimir cada SCC en un supervértice, en el DAG asociado, X[i] y ~X[i] están en componentes diferentes, y si existe un camino de ~X[i] a X[i], entonces ~X[i] = false y X[i] = true, o si existe un camino de X[i] a ~X[i], lo contrario. Y si no existe relación entre X[i] y ~X[i], se asocia arbitariamente, manteniendo siempre la restricción de que no puede haber un true -> false. Para un mejor algoritmo para hallar la solución, recomiendo esta lectura: http://www.oi.edu.pl/download/boi-2001.pdf (leer el primer problema y su solución).

Finalmente, resolvemos el problema:
Cada grupo tiene dos opciones de horario, llamemos a la primera X[i] y a la segunda ~X[i]. Luego hacemos una verificación todos contra todos entre grupos diferentes. Si un horario A de un grupo se interseca con un horario B de otro grupo sabemos que A y B no pueden estar juntos, entonces:

~(A and B)

Y por la ley de Morgan

~(A and B) = (~A or ~B)

Finalmente, cada restricción es una disyunción, y como todas las disyunciones tienen que satisfechas, tenemos una conjunción de disyunciones, lo que es 2-sat.
Finalmente, creamos el grafo asociado y verificamos los SCC dando la respuesta. Acá pongo mi código:

#include<map>
#include<string>
#include<set>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;

vector<int> adj[2000];
int timer, times[2000], comps, comp[2000], instack[2000], n;
stack<int> s;

void addclause(int a, int b){
   adj[a^1].push_back(b);
   adj[b^1].push_back(a);
}

int dia[7];
int from[2000], to[2000];

int diff(char a, char b, char c){
   if(a == 'M') return dia[0];
   else if(b == 'U') return dia[1];
   else if(a == 'W') return dia[2];
   else if(b == 'H') return dia[3];
   else if(a == 'F') return dia[4];
   else if(b == 'A') return dia[5];
   else return dia[6];
}

void clear(){
   for(int i = 0; i < 2 * n; i++){
       instack[i] = false; times[i] = -1;
       adj[i].resize(0);
   }
   comps = timer = 0;
}

int scc(int u){
   int low = times[u] = timer++;
   instack[u] = true; s.push(u);
   for(int i = 0; i < adj[u].size(); i++){
       int v = adj[u][i];
       if(times[v] == -1) low = min(low, scc(v));
       else if(instack[v]) low = min(low, times[v]);
   }
   if(low == times[u]){
       int x;
       do{
          x = s.top(); s.pop(); instack[x] = false;
          comp[x] = comps;
       }while(x != u);
       comps++;
   }
   return low;
}

int main(){
    int t; cin >> t;
    dia[0] = 0;
    for(int i = 1; i < 7; i++) dia[i] = dia[i - 1] + 24 * 60;

    while(t--){
        cin >> n;
        for(int i = 0; i < n; i++){
            char c1, c2, c3; int m, h, tiempo;
            scanf(" %c%c%c:%d:%d", &c1, &c2, &c3, &h, &m);
            tiempo = diff(c1, c2, c3) + h * 60 + m;
            from[2 * i] = tiempo;
            scanf(" %c%c%c:%d:%d", &c1, &c2, &c3, &h, &m);
            tiempo = diff(c1, c2, c3) + h * 60 + m;
            to[2 * i] = tiempo;

            scanf(" %c%c%c:%d:%d", &c1, &c2, &c3, &h, &m);
            tiempo = diff(c1, c2, c3) + h * 60 + m;
            from[2 * i + 1] = tiempo;
            scanf(" %c%c%c:%d:%d", &c1, &c2, &c3, &h, &m);
            tiempo = diff(c1, c2, c3) + h * 60 + m;
            to[2 * i + 1] = tiempo;
        }
        clear();
        for(int i = 0; i < 2 * n; i++) for(int j = i % 2 == 0 ? i + 2 : i + 1; j < 2 * n; j++)
        if(from[i] >= from[j] && from[i] < to[j] || from[j] >= from[i] && from[j] < to[i])
        addclause(i ^ 1, j ^ 1);    

        for(int i = 0; i < 2 * n; i++) if(times[i] == -1) scc(i);
        bool sirve = true;
        for(int i = 0; i < 2 * n; i += 2) if(comp[i] == comp[i + 1]) sirve = false;
        printf("%s\n", sirve ? "YES" : "NO");
    }
}

Este tipo de problemas no es muy común, pero viene. Ya vino en un mundial y en un sudamericano.

Destroying the Graph

Yo pensé que nadie resolvería este problema, felicitaciones a TheGoldenEagle por haber resuelto el problema.
Este es un problema de Min-Cut, así que creemos el grafo

s —- (W+)  —-  E —- (W-) —– t

s    : source
t    : target
W+    : V vértices, uno por cada vértice del grafo original
W-    : V vértices, uno por cada vértice del grafo original
E    : E vértices, uno por cada arista del grafo original

Para cada vértice del grafo original, hacemos una arista del W+ respectivo a los E respectivos, según las aristas que entran a dicho vértice en el grafo original. Para las aristas que salen, algo similar con W- y E. Los pesos de dichas aristas son infinitas.
Ahora, para cada vértice, hacemos una arista de s al W+ respectivo con peso igual al W+ del input. Lo mismo para W- y t.

Finalmente, lo que queremos es que cada arista esté cubierta, o bien por un W+, o bien por un W-, incluso por ambos. Esto equivale a romper aristas (s, W+) o (W-, t). Cada vez que rompemos una de esas aristas, estamos “eliminando” los W- o W+. Si existe un camino de s a t, entonces existe al menos una arista que tiene su W+ y su W- activos (recuerden que una arista tiene sólo un W- y sólo un W+).

Entonces, si desconectamos totalmente s de t, todos los E están cubiertos, y como queremos el menor costo para desconectar s de t, estamos hallando el min cut. Además, como las aristas incidentes a E son de peso infinito, nunca tocaremos esas aristas, sólo las de (s, W+) y las de (W-, t). Así, podemos resolver este problema con un algoritmo para max flow – min cut que pueda trabajar con al menos 5000 vértices.

Acá pongo mi code. Por cierto, hay implementaciones mucho más cortas.

#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;

const int maxnode=20000+5;
const int maxedge=1000000+5;
const int oo=1000000000;

int node,src,dest,nedge;
int head[maxnode],point[maxedge],next[maxedge],flow[maxedge],capa[maxedge];
int dist[maxnode],Q[maxnode],work[maxnode];

//inicializa el network, con _node igual a numero de nodos, _src como fuente y como _dest como sink
void init(int _node,int _src,int _dest)
{
     node=_node;
     src=_src;
     dest=_dest;
     for (int i=0;i<node;i++) head[i]=-1;
     nedge=0;
}

//añade la arista de u a v con capacidad c1 y la arista de v a u con capacidad c2
void addedge(int u,int v,int c1,int c2)
{
     point[nedge]=v,capa[nedge]=c1,flow[nedge]=0,next[nedge]=head[u],head[u]=(nedge++);
     point[nedge]=u,capa[nedge]=c2,flow[nedge]=0,next[nedge]=head[v],head[v]=(nedge++);
}

//bfs de dinic
bool dinic_bfs()
{
     memset(dist,-1,sizeof(dist));
     dist[src]=0;
     int sizeQ=0;
     Q[sizeQ++]=src;
     for (int cl=0;cl<sizeQ;cl++)
     for (int k=Q[cl],i=head[k];i>=0;i=next[i])
     if (flow[i]<capa[i] && dist[point[i]]<0)
     {
        dist[point[i]]=dist[k]+1;
        Q[sizeQ++]=point[i];
     }
     return dist[dest]>=0;
}

//dfs de dinic
int dinic_dfs(int x,int exp)
{
    if (x==dest) return exp;
    for (int &i=work[x];i>=0;i=next[i])
    {
        int v=point[i],tmp;
        if (flow[i]<capa[i] && dist[v]==dist[x]+1 && (tmp=dinic_dfs(v,min(exp,capa[i]-flow[i])))>0)
        {
           flow[i]+=tmp;
           flow[i^1]-=tmp;
           return tmp;
        }
    }
    return 0;
}
//flujo
int dinic_flow()
{
    int result=0;
    while (dinic_bfs())
    {
         for (int i=0;i<node;i++) work[i]=head[i];
         while (1)
         {
              int delta=dinic_dfs(src,oo);
              if (delta==0) break;
              result+=delta;
         }
    }
    return result;
}

int main(){
    int V, E; scanf("%d %d", &V, &E);
    int s = 2 * V + E;
    int t = s + 1;
    init(t + 1, s, t);

    for(int i = 0; i < V; i++){
        int mas; scanf("%d", &mas);
        addedge(s, i, mas, 0);
    }

    for(int i = 0; i < V; i++){
        int menos; scanf("%d", &menos);
        addedge(i + V, t, menos, 0);
    }

    for(int i = 0; i < E; i++){
        int u, v; scanf("%d %d", &u, &v); u--; v--;
        int ar = 2 * V + i;
        addedge(v, ar, oo, 0);
        addedge(ar, u + V, oo, 0);
    }

    cout << dinic_flow() << endl;
    vector<pair<int, int> > res;
    for(int i = 0; i < V; i++)
        if(dist[i] == -1)
           res.push_back(make_pair(i + 1, 1));

    for(int i = 0; i < V; i++)
        if (dist[i + V] != -1)
           res.push_back(make_pair(i + 1, 0));

    cout << res.size() << endl;
    sort(res.begin(), res.end());
    for(int i = 0; i < res.size(); i++){
        printf("%d %c\n", res[i].first, res[i].second == 1 ? '+' : '-');
    }
}

Cualquier duda o aporte respecto a los problemas pueden acceder al foro -> http://codebreakerscorp.foroperu.org/t37-aqp-training-6-2011 .

#include<cstring>
#include<vector>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

vector<int> E[101];
bool seen[101];

void dfs(int u){
   if(seen[u]) return;
   seen[u] = true;
   for(int i = 0; i < E[u].size(); i++)
       dfs(E[u][i]);
}

int main(){
   int t; cin >> t;
   while(t--){
       int n, m;
       cin >> n >> m;
       for(int i = 0; i < n; i++) E[i].resize(0);
       while(m--){
           int a, b; scanf("%d %d", &a, &b);
           a--; b--;
           E[a].push_back(b); E[b].push_back(a);
       }
       int res = 0;
       memset(seen, 0, sizeof seen);
       for(int i = 0; i < n; i++) if(!seen[i]) dfs(i), res++;
       cout << res << endl;
   }
}

AQP Training Contest #6!

Posted: December 16, 2010 in AQP Contest!

Saludos a todos,

Este fin de semana habrá AQP Training Contest !

En esta oportunidad tendremos un invitado especial como problemsetter, el mejor rankeado en topcoder de Perú, Walter Erquínigo (Shinta). Se tendrá dos divisiones, Division 1 para personas experimentadas (Conocimiento de algoritmos, técnicas de programación) y División 2 para los que estan iniciando y no conocen mucho de algoritmia.

  • Fecha del entrenamiento: Domingo 19 de diciembre
  • Hora de inicio: 10:00 am.
  • Duración del entrenamiento: 3 horas

El entrenamiento se realizará en el juez TJU:

http://acm.tju.edu.cn/toj/

Para lo cual los participantes en caso de no estar registrados deberán hacerlo en el siguiente link:
http://acm.tju.edu.cn/toj/register.html 

El problem set estará disponible a la hora de inicio en Virtual Contest:

con los nombres:
  • AQP TRAINING # 6 – 2011 DIV 1
  • AQP TRAINING # 6 – 2011 DIV 2
Las soluciones se publicarán al terminar el contest en el blog: 

https://codebreakerscorp.wordpress.com/

Aclaraciones, dudas y discusiones acerca de los problemas se podran discutir en el foro:

Esperamos tu participación.

keep solving Wink !.

[UPDATE: Para los que vieron hoy la página del TJU y notaron que los contest(div1 y div2)estaban finalizados…, ps no entrar en pánico xD, solo fue un error de cálculo al colocar los horarios(TJU toma la hora de China), por lo que mañana normal habrá contest, no falten!]

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