Concursos de Programación ACM-ICPC

Posted: November 8, 2010 in ACM-ICPC

Saludos a todos, como muchos ya saben, existen una gran variedad de concursos de programación, de todos los tipos, cada uno con sus propias reglas(por ejemplo: topcoder, IOI, IEEE, …), pero sin duda el mas importante y el que la gran mayoria de programadores apunta es el ACM-ICPC. La cual en nuestro caso cada año cuenta con  una fase preclasificatoria, donde concursamos con distintos paises como Argentina, Chile y Bolivia por los 3 o quizas 4 cupos para ir la final mundial.

Ahora  bien, el problem set de la ronda preclasificatoria de todas las sedes del mundo y el de la final mundial siempre  son colgados en: http://acm.uva.es/archive/nuevoportal/ de 2 a una semana despues de terminado el concurso, ahi pueden subir sus soluciones, ser juzgadas y recibir su veredicto(El proceso de como se hace el juzgamiento esta muy bien descrito aqui: http://codebreakerscorp.foroperu.org/introduccion-f7/jueces-en-linea-t2.htm).

Por eso les animamos a que traten de resolver los problemas del ACM 2009/2010 y 2010/2011, como una pequeña ayuda pondremos los problemas de la regional con su  dificultad relativa y el tema al que pertenecen.

Si tienen propuestas nuevas o dudas preguntar aqui: http://codebreakerscorp.foroperu.org/regionales-f10/

ACM-ICPC  Latin America 2009/2010

  1. Problema A – Another Crisis: Complejidad: medio -> bfs, dfs o recursividad.
  2. Problema B – Brothers: Complejidad: facil.
  3. Problema C – Code Lock: Complejidad: muy dificil.
  4. Problema D – Dinner Hall: Complejidad: facil -> greedy.
  5. Problema E – Electric Bill: Complejidad: medio-facil -> busqueda binaria.
  6. Problema F – File Recover: Complejidad: dificil -> suffix array(suffix tree), LCP.
  7. Problema G – Grapevine: Complejidad: medio.
  8. Problema H – Hooligan: Complejidad: dificil -> max flow,  Complejidad: medio-dificil -> greedy.
  9. Problema I – Isosceles Triangles: Complejidad: medio-facil -> geometria basica.
  10. Problema J – Jingle Composing: Complejidad: muy facil.
  11. Problema K – Kinglon Levels: Complejidad: medio-dificil.

————————————————————————————————————————–

ACM-ICPC  Latin America 2010/2011

  1. Problema A – Ants Colony: Complejidad: medio-dificil -> LCA, RMQ.
  2. Problema B – Bingo: Complejidad: facil.
  3. Problema C – Cocircular Points: Complejidad: medio -> Geometria básica.
  4. Problema D – Digits Count: Complejidad: medio-facil -> teoria de números básica.
  5. Problema E – Electric Needs: Complejidad: muy dificil(casi imposible..).
  6. Problema F – Flowers Flourish from France: Complejidad: muy facil.
  7. Problema G – Growing String: Complejidad: medio -> DP (lento),   Complejidad: dificil -> multi-patter string matching, DP(dfs),  Complejidad: muy dificil  -> topologocal sort, suffix array, DP.
  8. Problema H – Hyperactive Girl: Complejidad: medio-dificil -> Programación Dinámica.
  9. Problema I – Ingenious Metro: Complejidad: dificil -> Teoria de números.
  10. Problema J – Jollo: Complejidad: facil -> fuerza bruta.
  11. Problema K – Kids’ Wishes: Complejidad: medio -> dfs, pruning.

Keep Coding xD.

Comments
  1. Albert says:

    Hey, How are you?.

    Great Page… I need Help!! I need the Solution of “Another Crisis” on Java Language… Can you send to my email ?? please!! Tenkiu!!

    • Holas, por un lado lamento decirte que en mi caso no programo ni un “hola mundo” decente en java… y por otro, mmmm, seria bueno que primero lo intentes…., y me digas que parte no la tienes clara… , ese es el motivo por el que se creo el foro. Ya si aun asi no te sale, si te puedo brindar algun código en c++ para que lo pases a java.

      • Scorpion says:

        Hola me podrias dar una idea de como realizar el de hyperactive girls, yo lo planteo como un grafo pero para saber los caminos de manera rapida recorro tomo mi arreglo de atras para adelante y voy “inundando” a sus padres, pero me marca wrong answer y no se pr que, o como plantearlo con DP como tu lo dices.
        Gracias de antemano

  2. Kyoo says:

    Hola disculpa no podrias pasarme un link donde expliquen bienla construccion de un suffix array??????????

  3. Darkavenger says:

    Los problemas los clasificaron por que ya lo resolvieron???, si es asi que buen nivel tienen…que es LCA???

  4. Si se resolvieron la mayoria, expecto el q dice casi imposible … En cuanto a LCA significa lowest common ancestor en esta pagina hay un tutorial bastante bueno para entenderlo -> http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

  5. Pancho says:

    Hola, los felicito por la iniciativa.

    Me gustaría preguntarles si tienen disponibles los tiempos máximos de resolución para cada ejercicio, debido a que en ocasiones el algoritmo puede tardar mucho tiempo y uno no sabe si supera el máximo permitido, pese a encontrar la solución correcta.

    Saludos!

  6. JorgeThelaw says:

    hola que tal ,en el problema de ingenous metro como es q lo relacionas con teoria de numeros ?, el dia del concurso solo hice una comparacion y me lo acepto pero tiempo despues recibi un correo donde me diero WA.
    Ahora no encuentro una solucion ..

    • rayner says:

      En el problema Ingenous metro, si mas bien recuerdo, se trata de formar una combinacion lineal con los datos que tienes, y aplicar Bézout’s identity para resolver.

  7. thnkndblv says:

    Hola, tengo una duda, cual seria la idea para resolver el problema de Grapevine.

  8. Luis says:

    Hola, no se si podrias pasar un solucionario del 2011 yo resolvi apenas las preguntas A,B,D,F,J
    o si alguien mas quiere compartir soluciones podriamos compartir soluciones que a veces se aprende viendo el codigo de otros

  9. juancho says:

    no se si seria posible que puedan proporcionar links de los algorithmos mas utiles en la competencia como el dfs,lca etc. Tanto para grafos,programación dinámica, etc.

  10. PC says:

    I believe you are right completely

  11. David says:

    Excelente blog muchachos🙂. Si pueden hacer el problema E me gustaría que compartan la solución, ya que yo aún no he podido dar con ella😦.

  12. Kyoo says:

    Aque dejo 8 problemas que hize de ACM ICPC 2010 Latino America en lenguaje Java
    http://www.megaupload.com/?d=VLV0Z00M

  13. johny says:

    Agradecerìa si me pudieran dar el algoritmo del problema C, code lock, ya que no he podido solucionarlo.
    saludos muy buen blog!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s