AQP TRAINING #3 – 2011 finalizado!

Posted: November 28, 2010 in AQP Contest!

Saludos a todos, el AQP Training #3 ah finalizado y de antemano queremos agradecerles vuestra participación, felicitamos a nuestros ganadores:

  • 1er Lugar: Choby (Roger Quiroz – PUCP) , 6 problemas
  • 2do Lugar: JmJ (PUCP), 6 problemas
  • 3er Lugar:  rsoliss (Ruben Solis . UNSA), 6 problemas

Quienes pudieron resolver todos los problemas en menos de 1 hora!!, asi como tambien felicitamos a los demas participantes🙂 A continuación se mostrarán ideas de como resolver los problemas, seria bueno que intenten resolverlos, a los que no les salieron, con las ideas que se otorgan antes de ver el código:

Problema A – Perfection: Problema bastante sencillo, lo único que se debe realizar es iterar i desde 1 hasta n-1 e ir verificando si n % i ==0, en caso que sea verdad vamos sumando los valores de “i”. Si la suma de divisores es igual al numero entonces es perfecto, si es mayor es abundante de otro modo es deficiente.

Problema B – Computer Transformation: Si tratamos de resolver el problema por fuerza bruta obviamente nos dará TLE, la solución al problema es a través de una recurrencia que es la siguiente:Con esto podremos resolver el problema fácilmente, una buena opción seria precalcular los valores de las respuestas antes de inicial el input, de esta manera ahorraremos bastante tiempo en vez de estar calculando y calculando los mismos valores. Ahora otro punto clave en este problema es que a medida que calculemos para valores mas grandes, las respuestas crecerán de manera que no se podrán dar con int o incluso con un long long (Long para Java), para ello debemos operar sobre números grandes. Java posee la clase BigInteger ya implementada simplemente para usarla, esto es muy útil en concursos de programación, en C++ se tendría que crear una clase BigInteger ya que no cuenta con una.

Problema C – Red and Black: El problema puede ser resuelto por un algoritmo llamado Flood Fill, que es básicamente hacerlo de manera recursiva a partir de la posición arroba. Si tenemos un ‘.’ En cualquiera de los adyacentes (flood(x+1,y), flood(x-1,y), flood(x,y+1), flood(x,y-1) ) continuamos el recorrido por ese camino y marcamos el camino recorrido con ‘#’ para que no lo vuelva a recorrer y así vamos contando cada vez que sea ‘.’ .

Problema D – Find the Diagonal: Una forma de resolver el problema es hallando la columna en la que se encuentra el numero ingresado, esto se halla sacando el modulo con el tamaño (numero % tamaño) las columnas serán identificadas desde 1 hasta tamaño. Una vez obtenida la columna lo que hacemos es almacenar los valores de columnas anteriores (numero – tamaño – 1), recuerda que los valores empiezan en 1 así que solo almacenaremos valores >= 1, por otro lado hacemos lo mismo para las columnas siguientes del numero y hallamos los valores (numero + tamaño + 1) aquí almacenaremos valores menores al tamaño total de la matriz que es tamaño*tamaño.
Finalmente ordenamos los valores almacenados e imprimimos los elementos correspondientes.

Problema E – Intersecting Lines: Problema de geometría el cual podemos resolverlo usando la Regla de Cramer, la regla de Cramer requiere ecuaciones de rectas para operar en la matriz y hallas las soluciones, ello lo hallamos de las coordenadas ingresadas para obtener rectas de la forma A1x + B1y = C1, A2x + B2y = C2 y aplicar la regla de Cramer.

Problema F – Risk: Como se ve en la descripción del problema, este es un problema de grafos y uno muy conocido que es el de hallar la ruta mas corta entre dos nodos, como nos dan varias consultas y pocos nodos, exactamente 20, podemos usar el algoritmo de Floyd-Warshall recuerda la complejidad de este algoritmo es O(n^3) así que para grafos con pocos nodos sirve de mucho.

Las soluciones en código estan adjuntadas en el foro:

http://codebreakerscorp.foroperu.org/aqp-training-3-2011-f61/

Si cuentan con una mejor solución nos gustaria que la compartan, de esa forma todos nos beneficiariamos. Tambien si tienen dudas en las soluciones o ciertas partes no entendieron pueden escribirnos.

Links de Ayuda:

Numero Perfectos: http://es.wikipedia.org/wiki/N%C3%BAmero_perfecto

Interseccion de Lineas: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2
Regla de Cramer: http://www.mathwizz.com/algebra/help/help21.htm

Floyd Warshall:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs3
http://www.algorithmist.com/index.php/Floyd-Warshall%27s_Algorithm

Comments
  1. JmJ says:

    ¿Cuando es el siguiente?

    • Holas .. los contest se realizan todos los domingos ya sea en la mañana o en la tarde, por ahora son problemas no muy complicados, para gente que esta empezando a aprender algoritmos. Por otro lado seria xevere que compartaramos soluciones, para mejorar todos en conjunto.

  2. Acabo de publicar en el foro http://codebreakerscorp.foroperu.org/aqp-training-3-2011-f61 una breve explicación para el problema B, del porque se tiene que aplicar esa función de recurrencia, todo para aquellos que no saben como se hizo.
    Trate de hacerlo lo mas entendible posible.
    keep coding and solving.

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