3° competencia de la Red de Programación Competitiva (2016)


Aquí va el solucionario. Recordar que si no conocen algún término o algoritmo mencionado es recomandable que dejen de leer la solución y aprendan sobre ese algoritmo antes de seguir.

Juez Online y Enunciados 

https://acm.javeriana.edu.co/maratones/2016/03/




Soluciones


A. Acronyms



B. Tobby Bones



C. Tobby and Query



D. Standard Deviation



E. Tobby and the LED display



F. Triangular Test II



G. Tobby and the line game



H. Painting the Wall



I. Tobby on Tree



Problem J. Tobby Stones



K. Tobby and Seven



L. Tobby and Prime Sum

11 comentarios:

  1. Orale muchas gracias Martín, no tienes la solución del L?

    ResponderBorrar
  2. Excelente Martín, cómo sacaste la fórmula del G?

    ResponderBorrar
    Respuestas
    1. A decir verdad conviene hacer la cuenta con fuerza bruta e intentar encontrar el patrón, que en este caso era muy complicada aparentemente. También notar que lo que pasara en la dimensión x no afecta a lo que pasa en la dimensión y(eso puede ser una pista para la formula).

      Borrar
  3. Martín, te agradezco mucho por el análisis de las respuestas. Estoy iniciando en las competencias y se me ha dificultado poder realizar los ejercicios. Un saludo desde Colombia.

    ResponderBorrar
  4. Muchas gracias Martin, de mucha utilidad el analisis de las respuestas, nos sirve para seguir practicando en el post-marathon, solo un pequeño comentario, al parecer el juez de boca no permite utilizar la función __builtin_popcount(x) por lo que tienen que hacer el conteo con una función aparte, en mi caso convirtiendo el decimal a binario, Saludos desde México.

    ResponderBorrar
    Respuestas
    1. Que raro, nosotros lo usamos varias veces con el juez Boca, estás seguro que no habrá sido un error de tu código? Si querés hacerlo a mano la forma más fácil es con operaciones de bits:
      int q=0; for(int i=0; i<32; i++) q+=(n>>i)&1;

      Borrar
  5. en el ejercicio D (estandar desviation) como encuentro la formula? he intentado calcular el numerador con ciclos (en vez de calcularlo normalmente, solo tomo los números impares menores a n los elevo al cuadrado y los acumulo en una variable y luego multiplico la variable acumuladora por dos) pero da tiempo limite, lo he intentado en una función recursiva pero para casos muy grandes me da java.lang.stackoverflowerror error que quizás se deba a que se repite muchos veces la recursividad y java lo toma como una recursividad infinita(aunque no la sea). entonces no se me ocurre nada mas, podrías ayudarme?

    ResponderBorrar
    Respuestas
    1. Te recomiendo hacerte casitos paso a paso con n=2, luego con 3, con 4, etc. hasta que pilles un patrón, luego verás que ese patrón es una sumatoria conocida (con la que tienes que jugar un poco) y con eso podrás resolverlo. Saludos.

      Borrar
    2. gracias, encontré un cierto patrón y en base a eso pre-calcule todo y ya no da tiempo limite.

      Borrar
  6. Hola, te agradezco que te tomes el trabajo de hacer el análisis, que es algo que no se encuentra en ningún otro lado que yo sepa, además de que está buenísimo y de que está en español (otro aspecto que no se ve casi nunca).

    Además me gustaría agregar que existe una solución con tablas aditivas para el C. Con un array cnt[10][100000], donde cnt[i][j] indica en cada posición j, cuántas veces aparece el número i.

    Aunque teniendo las plantillas del segment tree, sería también sencillo implementarlo así.

    ResponderBorrar