Latin American Regionals 2009
16 views
Skip to first unread message
MarioYC
Nov 1, 2009, 5:17:14 PM11/1/09
to ACM ICPC Perú
Ya se puede enviar soluciones en el Live Archive.
Francisco Fernandez
Nov 1, 2009, 7:23:02 PM11/1/09
to acm-ic...@googlegroups.com
Francisco Fernandez
Nov 2, 2009, 1:46:32 AM11/2/09
to acm-ic...@googlegroups.com
Logré codificar en un intervalo de 5 horas los mismos 7 problemas que realizo el team sinosomosperuanosesto es falso, con una penalidad de 1012.
Las pgtas me gustaron bastante, aunque admito que el problemset se ve algo distinto a lo usual.
Sin embargo me tope con una de grafos( la A, en la que hago una especie de "BFS" al reves, para evitar un posible stack overflow) y un par de busquedas binarias(discreta, en el problema E, y sobre un arreglo, en el problema K. Este ultimo problema es sin embargo bastante directo haciendo uso de la STL(lower_bound).)
Uno que me gusto bastante fue el problema D, que aunque greedy, resulto ser uno de esos en los que puedo dar con la solución.
El problema J no merece mayores comentarios.
El problema I tiene en común con el D el hecho de que se piensa un poco y el código es bastante simple, ayuda bastante el hecho de que nos digan que no hay equilateros con 3 vértices de coordenadas enteras. Mi solución es O(n^2logn).
Finalmente, el problema B es bastante standard, sin embargo, fue en el que me toco tener uno de esos errores que me tuvieron mas tiempo del debido en este problema.
Sería bueno que abran un hilo para comentar cada problema. Trataré de resolver los otros 4 en la medida de lo posible.
Saludos.
Las pgtas me gustaron bastante, aunque admito que el problemset se ve algo distinto a lo usual.
Sin embargo me tope con una de grafos( la A, en la que hago una especie de "BFS" al reves, para evitar un posible stack overflow) y un par de busquedas binarias(discreta, en el problema E, y sobre un arreglo, en el problema K. Este ultimo problema es sin embargo bastante directo haciendo uso de la STL(lower_bound).)
Uno que me gusto bastante fue el problema D, que aunque greedy, resulto ser uno de esos en los que puedo dar con la solución.
El problema J no merece mayores comentarios.
El problema I tiene en común con el D el hecho de que se piensa un poco y el código es bastante simple, ayuda bastante el hecho de que nos digan que no hay equilateros con 3 vértices de coordenadas enteras. Mi solución es O(n^2logn).
Finalmente, el problema B es bastante standard, sin embargo, fue en el que me toco tener uno de esos errores que me tuvieron mas tiempo del debido en este problema.
Sería bueno que abran un hilo para comentar cada problema. Trataré de resolver los otros 4 en la medida de lo posible.
Saludos.
2009/11/1 Francisco Fernandez <tru...@gmail.com>
Ricardo Zarate
Nov 2, 2009, 10:10:14 AM11/2/09
to acm-ic...@googlegroups.com
Alguien tiene la solucion de la C, F o H???
Date: Mon, 2 Nov 2009 01:46:32 -0500
Subject: Re: Latin American Regionals 2009
From: tru...@gmail.com
To: acm-ic...@googlegroups.com
Date: Mon, 2 Nov 2009 01:46:32 -0500
Subject: Re: Latin American Regionals 2009
From: tru...@gmail.com
To: acm-ic...@googlegroups.com
Francisco Fernandez
Nov 2, 2009, 10:11:21 AM11/2/09
to acm-ic...@googlegroups.com
Mario ha hecho la H.
Para la F, en el foro de los hackermate mencionan que es muy directo usando suffix-trees.
Saludos.
Para la F, en el foro de los hackermate mencionan que es muy directo usando suffix-trees.
Saludos.
2009/11/2 Ricardo Zarate <rr...@hotmail.com>
Francisco Fernandez
Nov 2, 2009, 12:46:38 PM11/2/09
to acm-ic...@googlegroups.com
Gente, les pase la vez pasada a sus correos info del grupo de hackermate.
Sería bueno que posteen también por ahi, el grupo tiene una actividad considerable, y hay participacion de gente de otros paises de la región.
Creo es una buena opción de desarrollar, ya no digamos como universidad, sino como país.
Por supuesto que de todos modos, debemos seguir posteando por aquí( yo lo haré en ambos grupos, me parecen iniciativas muy buenas)
les copio el mensaje que reenvíe aquella vez:
Grupo: http://groups.google.com/group/teamhackermate
Página del team: www.teamhackermate.tk
Sientanse libres de pasar a mas gente interesada en entrenar en los concursos de programación.
Saludos
Víctor Laguna Gutiérrez
Coach team HaCkErMaTe
Sería bueno que posteen también por ahi, el grupo tiene una actividad considerable, y hay participacion de gente de otros paises de la región.
Creo es una buena opción de desarrollar, ya no digamos como universidad, sino como país.
Por supuesto que de todos modos, debemos seguir posteando por aquí( yo lo haré en ambos grupos, me parecen iniciativas muy buenas)
les copio el mensaje que reenvíe aquella vez:
Grupo: http://groups.google.com/group/teamhackermate
Página del team: www.teamhackermate.tk
Sientanse libres de pasar a mas gente interesada en entrenar en los concursos de programación.
Saludos
Víctor Laguna Gutiérrez
Coach team HaCkErMaTe
2009/11/2 Francisco Fernandez <tru...@gmail.com>
MarioYC
Nov 2, 2009, 11:57:58 PM11/2/09
to ACM ICPC Perú
La H sale con max-flow como mencionaron en los foros de Topcoder,
estaba interesante porque tuve que mejorar el algoritmo que tenía
preescrito el cual usaba un bfs y O(V^2) de memoria, pero para este
problema tuve que cambiar a un DFS y O(E) de memoria, esto para evitar
el Memory Limit Exceeded que tuve dos veces.
On 2 nov, 10:10, Ricardo Zarate <rr...@hotmail.com> wrote:
> Alguien tiene la solucion de la C, F o H???
>
estaba interesante porque tuve que mejorar el algoritmo que tenía
preescrito el cual usaba un bfs y O(V^2) de memoria, pero para este
problema tuve que cambiar a un DFS y O(E) de memoria, esto para evitar
el Memory Limit Exceeded que tuve dos veces.
On 2 nov, 10:10, Ricardo Zarate <rr...@hotmail.com> wrote:
> Alguien tiene la solucion de la C, F o H???
>
> Date: Mon, 2 Nov 2009 01:46:32 -0500
> Subject: Re: Latin American Regionals 2009
> From: trul...@gmail.com
> Subject: Re: Latin American Regionals 2009
> To: acm-ic...@googlegroups.com
>
> Logré codificar en un intervalo de 5 horas los mismos 7 problemas que realizo el team sinosomosperuanosesto es falso, con una penalidad de 1012.
> Las pgtas me gustaron bastante, aunque admito que el problemset se ve algo distinto a lo usual.
>
> Sin embargo me tope con una de grafos( la A, en la que hago una especie de "BFS" al reves, para evitar un posible stack overflow) y un par de busquedas binarias(discreta, en el problema E, y sobre un arreglo, en el problema K. Este ultimo problema es sin embargo bastante directo haciendo uso de la STL(lower_bound).)
>
> Uno que me gusto bastante fue el problema D, que aunque greedy, resulto ser uno de esos en los que puedo dar con la solución.
> El problema J no merece mayores comentarios.
> El problema I tiene en común con el D el hecho de que se piensa un poco y el código es bastante simple, ayuda bastante el hecho de que nos digan que no hay equilateros con 3 vértices de coordenadas enteras. Mi solución es O(n^2logn).
>
> Finalmente, el problema B es bastante standard, sin embargo, fue en el que me toco tener uno de esos errores que me tuvieron mas tiempo del debido en este problema.
>
> Sería bueno que abran un hilo para comentar cada problema. Trataré de resolver los otros 4 en la medida de lo posible.
>
> Saludos.
>
> 2009/11/1 Francisco Fernandez <trul...@gmail.com>
>
> Logré codificar en un intervalo de 5 horas los mismos 7 problemas que realizo el team sinosomosperuanosesto es falso, con una penalidad de 1012.
> Las pgtas me gustaron bastante, aunque admito que el problemset se ve algo distinto a lo usual.
>
> Sin embargo me tope con una de grafos( la A, en la que hago una especie de "BFS" al reves, para evitar un posible stack overflow) y un par de busquedas binarias(discreta, en el problema E, y sobre un arreglo, en el problema K. Este ultimo problema es sin embargo bastante directo haciendo uso de la STL(lower_bound).)
>
> Uno que me gusto bastante fue el problema D, que aunque greedy, resulto ser uno de esos en los que puedo dar con la solución.
> El problema J no merece mayores comentarios.
> El problema I tiene en común con el D el hecho de que se piensa un poco y el código es bastante simple, ayuda bastante el hecho de que nos digan que no hay equilateros con 3 vértices de coordenadas enteras. Mi solución es O(n^2logn).
>
> Finalmente, el problema B es bastante standard, sin embargo, fue en el que me toco tener uno de esos errores que me tuvieron mas tiempo del debido en este problema.
>
> Sería bueno que abran un hilo para comentar cada problema. Trataré de resolver los otros 4 en la medida de lo posible.
>
> Saludos.
>
>
> Genial, ahora mismo empiezo a mandar :D
>
> 2009/11/1 MarioYC <ycma...@gmail.com>
> Genial, ahora mismo empiezo a mandar :D
>
>
> Ya se puede enviar soluciones en el Live Archive.
>
> _________________________________________________________________> Ya se puede enviar soluciones en el Live Archive.
>
Victor Laguna
Nov 3, 2009, 12:03:52 AM11/3/09
to acm-ic...@googlegroups.com
Y yo pensando que era greedy haha.
Tienes el link de la discusion en topcoder?
Saludos
Víctor
Tienes el link de la discusion en topcoder?
Saludos
Víctor
MarioYC
Nov 3, 2009, 12:22:39 AM11/3/09
to ACM ICPC Perú
Bueno acá Itaravilse da una pequeña explicación de como plantear la
red : http://forums.topcoder.com/?module=Thread&threadID=651259&start=0&mc=48
Y la representación para la red que use para tener memoria O(E) la
aprendí de decowboy acá : http://forums.topcoder.com/?module=Thread&threadID=652718&start=0&mc=5#1150517
On 3 nov, 00:03, Victor Laguna <elvitu...@gmail.com> wrote:
> Y yo pensando que era greedy haha.
>
> Tienes el link de la discusion en topcoder?
>
> Saludos
> Víctor
>
red : http://forums.topcoder.com/?module=Thread&threadID=651259&start=0&mc=48
Y la representación para la red que use para tener memoria O(E) la
aprendí de decowboy acá : http://forums.topcoder.com/?module=Thread&threadID=652718&start=0&mc=5#1150517
On 3 nov, 00:03, Victor Laguna <elvitu...@gmail.com> wrote:
> Y yo pensando que era greedy haha.
>
> Tienes el link de la discusion en topcoder?
>
> Saludos
> Víctor
>
MarioYC
Nov 3, 2009, 12:24:35 AM11/3/09
to ACM ICPC Perú
Subí en Archivos mis códigos para la H y la K.
On 3 nov, 00:22, MarioYC <ycma...@gmail.com> wrote:
> Bueno acá Itaravilse da una pequeña explicación de como plantear la
> red :http://forums.topcoder.com/?module=Thread&threadID=651259&start=0&mc=48
>
> Y la representación para la red que use para tener memoria O(E) la
> aprendí de decowboy acá :http://forums.topcoder.com/?module=Thread&threadID=652718&start=0&mc=...
On 3 nov, 00:22, MarioYC <ycma...@gmail.com> wrote:
> Bueno acá Itaravilse da una pequeña explicación de como plantear la
> red :http://forums.topcoder.com/?module=Thread&threadID=651259&start=0&mc=48
>
> Y la representación para la red que use para tener memoria O(E) la
Roy Palacios Rezza
Nov 3, 2009, 12:52:44 AM11/3/09
to acm-ic...@googlegroups.com
Para la C hay una solucion greedy y una con dp, hay un thread en topcoder dedicado unicamente a este problema:
http://forums.topcoder.com/?module=Thread&threadID=653731&start=0&mc=17
From: rr...@hotmail.com
To: acm-ic...@googlegroups.com
Subject: RE: Latin American Regionals 2009
Date: Mon, 2 Nov 2009 07:10:14 -0800
http://forums.topcoder.com/?module=Thread&threadID=653731&start=0&mc=17
From: rr...@hotmail.com
To: acm-ic...@googlegroups.com
Subject: RE: Latin American Regionals 2009
Date: Mon, 2 Nov 2009 07:10:14 -0800
Connect to the next generation of MSN Messenger Get it now!
MarioYC
Nov 3, 2009, 12:59:35 AM11/3/09
to ACM ICPC Perú
Para la F me parece que solo se necesita crear el suffix treee y sumar
las longitudes de las cadenas que se encuentran sobre las aristas que
no llegan a una hoja del árbol, pero recién estoy leyendo sobre como
crear un suffix tree en tiempo lineal así que todavía no he podido
probarlo.
On 2 nov, 10:11, Francisco Fernandez <trul...@gmail.com> wrote:
> Mario ha hecho la H.
> Para la F, en el foro de los hackermate mencionan que es muy directo usando
> suffix-trees.
> Saludos.
>
> 2009/11/2 Ricardo Zarate <rr...@hotmail.com>
>
> > Alguien tiene la solucion de la C, F o H???
>
> > ------------------------------
las longitudes de las cadenas que se encuentran sobre las aristas que
no llegan a una hoja del árbol, pero recién estoy leyendo sobre como
crear un suffix tree en tiempo lineal así que todavía no he podido
probarlo.
On 2 nov, 10:11, Francisco Fernandez <trul...@gmail.com> wrote:
> Mario ha hecho la H.
> Para la F, en el foro de los hackermate mencionan que es muy directo usando
> suffix-trees.
> Saludos.
>
> 2009/11/2 Ricardo Zarate <rr...@hotmail.com>
>
> > Alguien tiene la solucion de la C, F o H???
>
> > Date: Mon, 2 Nov 2009 01:46:32 -0500
> > Subject: Re: Latin American Regionals 2009
> > From: trul...@gmail.com
> > Subject: Re: Latin American Regionals 2009
> > To: acm-ic...@googlegroups.com
>
> > Logré codificar en un intervalo de 5 horas los mismos 7 problemas que
> > realizo el team sinosomosperuanosesto es falso, con una penalidad de 1012.
> > Las pgtas me gustaron bastante, aunque admito que el problemset se ve algo
> > distinto a lo usual.
> > Sin embargo me tope con una de grafos( la A, en la que hago una especie de
> > "BFS" al reves, para evitar un posible stack overflow) y un par de busquedas
> > binarias(discreta, en el problema E, y sobre un arreglo, en el problema K.
> > Este ultimo problema es sin embargo bastante directo haciendo uso de la
> > STL(lower_bound).)
> > Uno que me gusto bastante fue el problema D, que aunque greedy, resulto ser
> > uno de esos en los que puedo dar con la solución.
> > El problema J no merece mayores comentarios.
> > El problema I tiene en común con el D el hecho de que se piensa un poco y
> > el código es bastante simple, ayuda bastante el hecho de que nos digan que
> > no hay equilateros con 3 vértices de coordenadas enteras. Mi solución es
> > O(n^2logn).
> > Finalmente, el problema B es bastante standard, sin embargo, fue en el que
> > me toco tener uno de esos errores que me tuvieron mas tiempo del debido en
> > este problema.
>
> > Sería bueno que abran un hilo para comentar cada problema. Trataré de
> > resolver los otros 4 en la medida de lo posible.
> > Saludos.
>
> > 2009/11/1 Francisco Fernandez <trul...@gmail.com>
>
> > Logré codificar en un intervalo de 5 horas los mismos 7 problemas que
> > realizo el team sinosomosperuanosesto es falso, con una penalidad de 1012.
> > Las pgtas me gustaron bastante, aunque admito que el problemset se ve algo
> > distinto a lo usual.
> > Sin embargo me tope con una de grafos( la A, en la que hago una especie de
> > "BFS" al reves, para evitar un posible stack overflow) y un par de busquedas
> > binarias(discreta, en el problema E, y sobre un arreglo, en el problema K.
> > Este ultimo problema es sin embargo bastante directo haciendo uso de la
> > STL(lower_bound).)
> > Uno que me gusto bastante fue el problema D, que aunque greedy, resulto ser
> > uno de esos en los que puedo dar con la solución.
> > El problema J no merece mayores comentarios.
> > El problema I tiene en común con el D el hecho de que se piensa un poco y
> > el código es bastante simple, ayuda bastante el hecho de que nos digan que
> > no hay equilateros con 3 vértices de coordenadas enteras. Mi solución es
> > O(n^2logn).
> > Finalmente, el problema B es bastante standard, sin embargo, fue en el que
> > me toco tener uno de esos errores que me tuvieron mas tiempo del debido en
> > este problema.
>
> > Sería bueno que abran un hilo para comentar cada problema. Trataré de
> > resolver los otros 4 en la medida de lo posible.
> > Saludos.
>
>
> > Genial, ahora mismo empiezo a mandar :D
>
> > 2009/11/1 MarioYC <ycma...@gmail.com>
> > Genial, ahora mismo empiezo a mandar :D
>
>
> > Ya se puede enviar soluciones en el Live Archive.
>
> > ------------------------------> > Ya se puede enviar soluciones en el Live Archive.
>
Roy Palacios Rezza
Nov 3, 2009, 1:09:07 AM11/3/09
to acm-ic...@googlegroups.com
Leete las joyas de la stringologia :P
http://www.amazon.com/Jewels-Stringology-Maxime-Crochemore/dp/9810247826
> Date: Mon, 2 Nov 2009 21:59:35 -0800
> Subject: Re: Latin American Regionals 2009
> From: ycm...@gmail.com
> To: acm-ic...@googlegroups.com
Discover the new Windows Vista Learn more!
MarioYC
Nov 3, 2009, 1:15:28 AM11/3/09
to ACM ICPC Perú
Bueno ahorita estoy leyendo el Algorithms on strings, trees and
sequences, pero para el que quiera ir leyendo el otro, aca hay un
link: http://avaxhome.ws/ebooks/science_books/math/733509.html
On 3 nov, 01:09, Roy Palacios Rezza <roypalac...@hotmail.com> wrote:
> Leete las joyas de la stringologia :P
>
> http://www.amazon.com/Jewels-Stringology-Maxime-Crochemore/dp/9810247826
>
>
>
> > Date: Mon, 2 Nov 2009 21:59:35 -0800
> > Subject: Re: Latin American Regionals 2009
> > From: ycma...@gmail.com
> _________________________________________________________________
> Discover the new Windows Vistahttp://search.msn.com/results.aspx?q=windows+vista&mkt=en-US&form=QBRE
sequences, pero para el que quiera ir leyendo el otro, aca hay un
link: http://avaxhome.ws/ebooks/science_books/math/733509.html
On 3 nov, 01:09, Roy Palacios Rezza <roypalac...@hotmail.com> wrote:
> Leete las joyas de la stringologia :P
>
> http://www.amazon.com/Jewels-Stringology-Maxime-Crochemore/dp/9810247826
>
>
>
> > Date: Mon, 2 Nov 2009 21:59:35 -0800
> > Subject: Re: Latin American Regionals 2009
> Discover the new Windows Vistahttp://search.msn.com/results.aspx?q=windows+vista&mkt=en-US&form=QBRE
Roy Palacios Rezza
Nov 3, 2009, 1:18:34 AM11/3/09
to acm-ic...@googlegroups.com
A mi me gusta matar arboles, taba viendo que ya salio la 3ra edicion del Cormen, Septiembre 2009
http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=11866
A romper el chanchito
> Date: Mon, 2 Nov 2009 22:15:28 -0800
> Subject: Re: Latin American Regionals 2009
Get news, entertainment and everything you care about at Live.com. Check it out!
Shinta
Nov 3, 2009, 1:22:11 AM11/3/09
to ACM ICPC Perú
Recién pude codear mi suffix tree O(n), lo cuelgo más tarde. Muy paja
el libro que posteaste, roy.
el libro que posteaste, roy.
MarioYC
Nov 3, 2009, 1:23:17 AM11/3/09
to ACM ICPC Perú
Se ve interesante su capítulo de Advanced Data Structures, lo malo es
que todavía ni aprendo Red Black Trees :p
On 3 nov, 01:18, Roy Palacios Rezza <roypalac...@hotmail.com> wrote:
> A mi me gusta matar arboles, taba viendo que ya salio la 3ra edicion del Cormen, Septiembre 2009
>
> http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=11866
>
> A romper el chanchito
>
>
>
> > Date: Mon, 2 Nov 2009 22:15:28 -0800
> > Subject: Re: Latin American Regionals 2009
> > From: ycma...@gmail.com
> _________________________________________________________________
> News, entertainment and everything you care about at Live.com. Get it now!http://www.live.com/getstarted.aspx
que todavía ni aprendo Red Black Trees :p
On 3 nov, 01:18, Roy Palacios Rezza <roypalac...@hotmail.com> wrote:
> A mi me gusta matar arboles, taba viendo que ya salio la 3ra edicion del Cormen, Septiembre 2009
>
> http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=11866
>
> A romper el chanchito
>
>
>
> > Date: Mon, 2 Nov 2009 22:15:28 -0800
> > Subject: Re: Latin American Regionals 2009
> News, entertainment and everything you care about at Live.com. Get it now!http://www.live.com/getstarted.aspx
Roy Palacios Rezza
Nov 3, 2009, 1:28:33 AM11/3/09
to acm-ic...@googlegroups.com
Mejor que no lo hayas aprendido aun, porque ya lo han mejorado segun el video que aparece en(se habla de lo nuevo en la 3ra edicion):
http://mitpress.mit.edu/algorithms/
> Date: Mon, 2 Nov 2009 22:23:17 -0800
http://mitpress.mit.edu/algorithms/
> Date: Mon, 2 Nov 2009 22:23:17 -0800
> Subject: Re: Latin American Regionals 2009
francisco agustin fernandez berrocal
Nov 3, 2009, 9:39:15 AM11/3/09
to acm-ic...@googlegroups.com
Este es el link:
http://forums.topcoder.com/?module=Thread&threadID=653806&start=0&mc=6
Al parecer, si hay solucion greedy. 2 equipos la hicieron en Bolivia, y según menciona uno de ellos en tc, al menos uno de ellos lo hizo golosamente.
Date: Tue, 3 Nov 2009 00:03:52 -0500
http://forums.topcoder.com/?module=Thread&threadID=653806&start=0&mc=6
Al parecer, si hay solucion greedy. 2 equipos la hicieron en Bolivia, y según menciona uno de ellos en tc, al menos uno de ellos lo hizo golosamente.
Date: Tue, 3 Nov 2009 00:03:52 -0500
Subject: Re: Latin American Regionals 2009
francisco agustin fernandez berrocal
Nov 3, 2009, 9:53:31 AM11/3/09
to acm-ic...@googlegroups.com
Por cierto Victor, tienen sus hinchas al parecer en Bolivia:
http://www.ic.unicamp.br/~rdahab/icpc2009/Welcome_files/Bolivia_summary.html
ver puesto 19
Saludos.
From: trul...@hotmail.com
http://www.ic.unicamp.br/~rdahab/icpc2009/Welcome_files/Bolivia_summary.html
ver puesto 19
Saludos.
From: trul...@hotmail.com
Date: Tue, 3 Nov 2009 14:39:15 +0000
Victor Laguna
Nov 3, 2009, 10:02:10 AM11/3/09
to acm-ic...@googlegroups.com
Haha, si al parecer ya hay hinchas internacionales.
Reply all
Reply to author
Forward
0 new messages