AQP Training Contest #7 finalizado!

Posted: February 27, 2011 in AQP Contest!

AQPTraining Contest #7 ah finalizado y agradecemos a los participaron del contest, a continuación presentamos el analisis de los problemas propuestos en el contest:

PROBLEMA A: Cola

El problema puede ser resuelto simplemente simulando el 1er método dado en el enunciado del problema. Ello es iterando sobre el numero de botellas e ir restando 3 mientras se tenga mas de 3 botellas, a la vez que incrementamos en 1 la respuesta. Si el número final de botellas restantes es 2 entonces podemos tomar prestado una botella para maximizar el número de botellas, por lo tanto incrementamos en uno nuestra respuesta.

PROBLEMA B: Count DePrimes

Dado dos numero a y b, hallar la cantidad de numeros entre a y b ( inclusive ) cuyos factores primos suman un numero primo,Si un numero primo es factor de algun numero n, entonces p*k = n, para algun numero primo p, y algun k. Si el valor de k varia obtendremos otros numero de los cuales p es factor es decir los multiplos de p.Para obtener la suma de factores primos de un numero n, debemos sumar todos los numeros primos tal que p * k = n, Una forma de hacer es iterar sobre todos los numeros primos y sumar este numero primo a sus multiplos en un array.

PROBLEMA C: Sumsets

Una forma de resolver el problema es usando fuerza bruta con 4 for anidados ( O( n ^4 ) ). Primeramente almacenamos los números de ingreso en un arreglo y lo ordenamos. Luego hacemos los 4 for de la siguiente manera, el 1ero tendrá el ultimo elemento del arreglo e ira decreciendo en tamaño, este será el valor de “d” por ser el mayor. Los otros 3 for representaran el valor de “a”, “b” y “c”. Por lo tanto dentro del ultimo for quedaría la comparación de si “a + b + c = d” retornar el valor de “d”, de otro modo seguir iterando. Si al final no se hallo resultado imprimimos “no solution”.

PROBLEMA D: LCM

Dado un n, encontrar el LCM de todos los enteros positivos menores o iguales que n, ya que el numero puede ser muy grande, imprimir el ultimo digito diferente de cero.Si representamos dos numero como el producto de la potencias de sus factores primos, su lcm sera:

lcm ( a, b ) = p1 ^ max ( e1_1, e1_2 ) * p2 ^ max ( e2_1, e2_2 ) * p3 ^ max ( e3_1, e3_2 ) * ..

Esta definicion se puede extender para todos los valores menores o iguales que n:

lcm ( 1..n ) = p1 ^ max ( e1_1, .., e1_n ) * p2 ^ max ( e2_1, .., e2_n ) * ..

Para hallar el maximo exponente que puede tener cada primo en el rango 1..n es equivalente a encontrar el maximo k tal que p ^ k <= n, ya que p ^ k * m = n, para algun m.
Ya que solo queremos el ultimo digito diferente de cero, debemos evitar multiplicar por 10, esto los conseguiremos modificando los exponentes del 2 y 5,

lcm ( 1..n ) = 2 ^ ( max_e2 – k ) * .. * 5 ^ ( max_e5 – k ) , donde k = min ( max_e2, max_e5 ).

El resultado sigue siendo grande asi que debemos usar modulo

PROBLEMA E: Light and Transparencies

Para este problema el eje “y” no será de ayuda, solo usaremos el eje “x”. En cada ingreso podemos almacenarlo en una estructura Segmento que contenga el “x” menor, “x” mayor y el valor “r”. También en otro vector podemos almacenar todos los puntos del eje “x” y luego ordenar dicho vector para iniciar el recorrido. Casos –inf +inf siempre se imprimirá 1, para los demás recorremos el vector de valores “x” y vemos a que segmentos pertenece dicho valor, puede ser una función como sigue:

double segment( vector<Segment> s , double x ){
     double value = 1.0;
     for(int i = 0 ; i < s.size() ; ++i )
         if( s[ i ].xmin <= x && x < s[ i ].xmax ) value *= s[ i ].r;
     return value;
}
PROBLEMA F Dropping balls

Dadas las indicaciones para recorrer una arbol binario completo, el problema nos pide hallar el numero del nodo hoja donde caera la i-esima bola, de las indicaciones del recorrido nos damos cuenta que la i-esima posicion en el arbol padre es la (i/2) posicion de algunos de sus hijos, la eleccion del hijo depende de las pardidad del indice, ya que solo escogemos 1, la complejidad se reduce a log(n) ( solo buscamos en una del las mitades ).

int solve ( int cur_deep, int max_deep, int i, int cur ) {
	if ( cur_deep >= max_deep ) return cur;
	return i%2? 
	solve ( cur_deep + 1, max_deep, i/2, 2*cur + 2 )
	: solve ( cur_deep + 1, max_deep, i/2, 2*cur + 1 );
}

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