Links de Algoritmos y Estructura de Datos

Thomas Jefferson's Senior Computing Team
Skiena's Algorithms Lectures
Algorithm Design

Problema - Square Math

Este problema aparecio en la ronda 1 del Codejam 2009. El link del problema: http://code.google.com/codejam/contest/dashboard?c=186264#s=p2. En el problema se define lo que es el Square Math (SM) y se te pide encontrar la secuencia menor que genere este cuya suma sea igual a un valor determinado. Un SM tiene esta forma:

2+3
+4-
1+0

Una secuencia del Square Math que sume 20 es "5+5+5+5" y 2 es "2". Tambien te dicen que una secuencia es menor si es mas corta o si, siendo de igual longitud, es menor lexicograficamente. A simple vista, un enfoque de brute-force puede servir pero siendo los limites de las entradas son demasiado grandes incluso para la entrada pequeña.

El truco es el darse cuenta de que el problema se puede representar por medio de un grafo, donde cada nodo es una posible solucion para el query de q = suma. Y donde cada arista marca la posibilidad de ir de una solucion a otra en el SM. Luego se puede usar BFS (Breadth First Search) y una cola de prioridad para encontrar la solucion mas corta.

class Nodo{  

  int i; //la coordenada i de la posicion actual (vertical).

  int j; //la coordenada j de la posicion actual (horizontal). 

  int suma; //la suma acumulada hasta la posicion actual

  String exp; //auxiliar: la expresion hasta la pos. actual "2+2+3"  

}

Por ejemplo, el (0,0,2,"2") se conecta a (0,2,5,"2+3"), es decir sumamos 3 al nodo inicial yendo de (0,0) a (0,2) y pasando por (0,1) que es '+'. El nodo (0,0,2,"2") tambien se conecta al nodo (1,1,6,"2+4"). De igual manera todos los nodos que tengan que tengan la forma (0,0,X,"...") se conectan al nodo (1,1,X+4,"...+4"). Se comienza con un grafo como la imagen donde los nodos en amarillo son los nodos iniciales a considerar.

Este enfoque es correcto pero en realidad no es necesario generar un grafo real para calcular el bfs. En la funcion de BFS se puede ir generando cada nodo dinamicamente, encontrar sus nodos "hijos" y añadirlos en caso no existan.

Los nodos conforme se vayan generando se almacenaran en un arreglo de Nodos. Se usara una cola de prioridad (una cola normal pero que siempre se mantiene ordenada de acuerdo a una funcion de comparacion) para obtener el nodo siguiente a procesar en el BFS.

Nodo[][][] nodos = new Nodo[w][w][3000];
//almacenamos los nodos conforme los generamos
Queue<Nodo> cola = new PriorityQueue<Nodo>(500,
 new ComparadorNodo()); ;
// la cola de prioridad. Procesaremos primero los nodos
// con una expresion menor 

El tamaño "3000" del campo suma de nodos se da suponiendo que la suma maxima de un nodo esta dentro de -1500 y +1500. Esto si se cumple considerando que los querys se encuentran entre -250 y +250. El codigo del bfs seria algo asi:

private static Nodo bfs(String[] SM, int query) {
    int i,j;
    Nodo v;

    //si es el primer caso, generar los nodos iniciales
    if (cola.isEmpty()) {
        for(i=0;i<SM.length;i++){
            for(j=0;j<SM.length;j++){
                if(Character.isDigit(SM[i].charAt(j)))
                    cola.add(new Nodo(i,j,SM[i].charAt(j)-'0',""+
                            SM[i].charAt(j)));
            }
        }
    }

    //en caso ya se tenga la solucion, se busca la que tenga
    //menor expresion
    Nodo sol = null;
    ComparadorNodo cmp = new ComparadorNodo();
    for(i=0;i<SM.length;i++){
        for(j=0;j<SM.length;j++){
            Nodo n =nodos[i][j][query+1500];
            if(n!=null && (sol == null || cmp.compare(sol, n)>0))
                sol=n;
        }
    }
    if(sol!=null)
        return sol;

    while (!cola.isEmpty()) {
        v = cola.peek();
        if (v.suma == query) 
            return v;              
        v = cola.poll();

        List<Nodo> hijos = BuscarHijos(v,SM); //serian 16 hijos
        Collections.sort(hijos,cmp); //ordenarlos de acuerdo a exp.
        for (i = 0; i < hijos.size(); i++) {
            Nodo hijo = hijos.get(i);
            if (nodos[hijo.i][hijo.j][hijo.suma+1500]==null) {
                nodos[hijo.i][hijo.j][hijo.suma+1500] = hijo;
                cola.add(hijo);
            }
        }
    }
    return null;
}

Problema - Decision Tree

Este problema apareció en el Round 1B del CodeJam 2009. El link del problema:
http://code.google.com/codejam/contest/dashboard?c=186264#.

El problema es relativamente sencillo. En resumen lo que se tiene que hacer es hacer una función que transforme el árbol del formato texto (String) a una estructura de datos determinada y luego otra que permita el procesamiento.

Solo hay que hacer lo que dice el enunciado, pero la programación se puede complicar si no se tienen las estructuras de datos adecuadas. Además utilizando la recursividad simplifica las funciones.

Mi estructura de datos:

    static class Nodo{
        String feature;
        double p;
        Nodo left;
        Nodo right;
    }

Mi enfoque fue usar dos funciones, una de interpretación y otra de ejecución:

  double ejecutar(HashSet<String> features, Nodo raiz)
  Nodo interpret(String x)

La función interpret lo que hace es, a partir del String tree generar un nodo. El String 'tree' tiene la forma"0.54 fast (...) (...)" ó "0.36".

• Si se corresponde al 1er caso lo que hice fue identificar los strings que se encuentran dentro de cada uno de estos paréntesis teniendo como nodo resultante algo asi: Nodo("fast",0.54,interpret("..."),interpret("..."))
• El 2do caso es mas simple. El nodo resultante seria asi: Nodo(null,0.36,null,null)

Ahora la función ejecutar: (en java)

 private static double ejecutar(HashSet<String> features, Nodo raiz){
      if(raiz.left == null)
          return raiz.p;
      if(features.contains(raiz.feature))
          return raiz.p * ejecutar(features,raiz.left);        
      return raiz.p * ejecutar(features,raiz.right);
  }

Esta función tiene 3 casos. Si el nodo es un nodo final, sin hijos, devuelve la probabilidad p del nodo. En caso no sea final y la 'feature' del nodo este contenida dentro de las 'features' del animal entonces devuelve la probabilidad p multiplicada por la probablidad del hijo izquierdo. Caso contrario va por el lado derecho.

El código del programa lo pueden ver en el mismo codejam. Mi código (en java) lo pueden ver con el usuario 'zaratov'.

Bienvenidos

Hola a todo el mundo.

Como dice el titulo, este el blog oficial de la FIIS y de la UNI respecto a los concursos de problemas de programacion de naturaleza algoritmica como el de Topcoder, el Google Code Jam, el ACM-ICPC, IEEE Extreme y cualquier otro que aparezca.

Para los que no conocen que es un algoritmo-> http://online-judge.uva.es/p/v1/100.html para un ejemplo de que tipo de problemas se espera tratar aqui.

La idea de este blog es que sirva como medio para compartir teoria, tecnicas y experiencias entre los participantes de estos concursos asi como informar de cualquier suceso de importancia relacionado al tema que se de en la FIIS, la UNI o el Peru.

Todo el mundo esta invitado a colaborar con el blog, en especial gente de Lima y Peru.