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!
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.
1 comentario:
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
Publicar un comentario