Translate

viernes, 21 de octubre de 2011

Regional ACM Mexico Centro America 2011 Regional ACM Caribe 2011 Regional ACM Brasil 2011 Regional ACM Sudamerica sin Brasil 2011



  Ya están las fechas en sima, del 4 al 5 de noviembre se llevaran a cabo el concurso reginal en varias zonas de america latina, muchos estudiantes ya están preparándose para este gran evento, ya fueron eliminatorias, en México , Centro America y el Caribe, se llevaron acabo varios concursos de preparación, donde se ve que el Caribe esta mejorando bastante, y un incremento de participación de Centro America, también me lleve una grata sorpresa el mes pasado al ver que ya existe una pagina que hicieron los cubanos, muy buena pagina http://coj.uci.cu/


  Lo que queda es recomendarles que preparen bien sus notas de los concursos, Geometría, Grafos, Teoría de números.

  Y bueno no esta de mas darle un vistazo a los problemas regionales del año pasado.


Ants Colony

Este problema fue uno de los problemas complicado de este regional , para resolver este problema les sugiero leer este post en topcoder  http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor  (Lowest Common Ancestor)

Este problema podemos verlo como un árbol, este árbol calculamos un arreglo SUM[ nodo ], donde SUM[ nodo ] contiene la suma o la distancia de la raíz del árbol al nodo seleccionado. Con el algoritmo del post podemos obtener el ancestro de cada uno de ellos de manera logarítmica, (aun que antes tenemos que hacer un pre proceso que corre en n log n) si sabemos el ancestro común del nodo A y nodo B entonces la distancia entre A y B es igual a SUM[A] + SUM[B] – 2*SUM[ancestroAB].

Bingo!


Este problema se puede resolver con el uso de un hash, con el me ayudo a validar que esten todos los numeros del 0 a n





Digits Count

   Digit Count es un problema que se puede atacar de manera matematica, en lo personal se me hizo mas facil hacerlo con Programacion Dinamica, pero eso ya es cuestion de cada quien 


Electric Needs

    (No le he podido resolver, alguien tiene alguna idea??)

Flowers Flourish from France

    Es uno de los problemas mas faciles, solo hay que saber partir una caden, despues de partir la cadena, o separarlas por sus espacios, hay que ver si todos empiezan con las mismas letras.

 Para la separacion de la cadena yo utilize strtok (pueden googlearlo para ver como funciona)

Growing Strings

  (otro problema que no eh podido resolver)

Hyperactive Girl

 

  Es un problema que se requiere un poco de conocimiento de programacion dinamica , se ve sencillo al inicio por que N es 100, pero M es muy grande , para superar este pequeño obstaculo del tamaño de M tenemos que darle otros valores a S y F , como solo nos interesa el orden de los elementos, por ejemplo si tenemos valores de 100, 200, 500, 100000, podemos darles los valores de 1, 2, 3, 4 respectivamente, y asi quedaria una dinamica de 200 x 200 que seria lo maximo de valores distintos que se pueden obtener.


Ingenious Metro

No  he podido resolver el problema pero aqui les pongo un link de alguien que si
http://apps.topcoder.com/forums/;jsessionid=D1941A7AEF3A12C45930433FA57C103D?module=Thread&threadID=717448&start=0&mc=5#1413943


Jollo

   Este es de los moderadamente secillos, se intenta con todas las cartas posible que no se allan utilizado aun, y luego se validan todas las combinaciones de juego para garantizar que el principe gane.

Kids' Wishes

Este problema solo requiere una busqueda en profundidad , pero lo que lo hace complicado es que es sobre un grafo muy grande, para eso necesitan utilizar listas ligadas o minimo simularlas.

 

Solo me queda desearles suerte en el regional.


Saludos. (cualquier comentario es bienvenido)

 

 

 

 

 



1 comentario:

David Jacobo dijo...

Hola, el problema de Growing Strings no es tan dificil si haces un ordenamiento de las palabras en base a su longitud y orden lexicografico para posteriormente por DP computar la maxima longitud de palabras ¨en cadena¨, cuando recupere mi codigo te lo puedo mostrar, saludos