AQP TRAINING # 1 – 2011 finalizado! xD

Posted: November 7, 2010 in AQP Contest!

Holas a todos, Acaba de terminar  AQP TRAINING # 1 – 2011!! y felicitamos a Ruben por haber quedado en 1er lugar resolviendo 3 problemas en relativamente corto tiempo, también felicitamos a todos los que participaron, vemos que hay mucho interes por este tipo de concursos🙂. A continuacion vamos a dejar un detalle de las soluciones(luego subiremos el código en c++).

Problema A – Jolly Jumpers: este problema requería mas que conocimiento algoritmico, un buen entendimiento de lo que se pedia. Una posible solución seria tener un array adicional (de booleanos),(bool Check[N]) y ahi chekear que la diferencia absoluta entre cada par de la secuencia digase (A[i]-A[i+1]) este comprendida entre el rango 1..N-1 y que no se repitiera la misma diferencia 2 o mas veces.

Problema B – CheckerGame: Este es un clásico problema de DP(Dynamic Programming)(si no saben de lo que hablo, miren los link de abajo o revisen el cormen), donde el estado se definiria asi: DP[i][j]: El maximo score que se puede obtener partiendo desde la fila i y columna j del tablero. Por lo que  a partir de aqui se pueden tomar dos caminos, utilizar recursividad para ver todos los posibles caminos pero no repitiendo el mismo camino dos veces(con ayuda de DP[i][j]) o llenar DP[i][j] iterativamente.

Problema C – Printer Queue: Este problema basicamente es pura simulación, tenias que definir una cola (p.e. queue< pair<int, int> > cola) y donde tuviera como información el número de job y su prioridad. y tener alguna variable o estructura donde contenga la informacion del job de mayor prioridad que todavia no fue imprimido, (yo use aqui el priority queue del STL,  logicamente deben haber mejores representaciones), de aqui comparar que el job que esta en el tope de la cola tuviera igual prioridad que el job de mayor proridad, si es asi , imprimir ese job, caso contrario, colocarlo al final de la cola y asi seguir hasta que logres imprimir el job que te piden en el input. y dar el # de impresiones que se tuvieron que hacer.

Problema D – Prime Path: Aca, la solución va por hacer aplicar una sieve scando todos los primos de 4 digitos que existen y a partir de ahi hacer un bfs para hallar el shotest path. (para los que no saben de que estoy hablando ver los links de abajo).

Problema E – Freckles: Este es un problema básico de MST(Minimum Spanning Tree) ,puedes revisar el Cormen para referencias, para resolver un MST puedes hacerlo por Prim o Kruskal , en este caso la manera en que se resolvio fue usando Kruskal. Ahora el ingreso no es de la forma convencional el ingreso son coordenadas, cada coordenada la representamos como un nodo por ello primero almacenamos el ingreso en un vector<pair<double,double> > o se puede usar una estructura Punto(vector<Punto>), luego recorremos todos los puntos previamente almacenados y les damos un valor que sera la representacion del vertice(etiqueta), tambien el problema no nos da una valor de la distancia para que podamos aplicar directamente para ello la distancia sera representada como la distancia entre dos coordenadas (x1,y1) con (x2,y2), tomandolo como grado seria Nodo 1 = etiqueta para (x1,y1) Nodo 2 = etiqueta para (x2,y2) Arista = distancia. Finalmente ya armado el grafo aplicamos kruskal y mostramos la distancia con 2 decimales.

Problema F – Word Index: Este problema tiene dos partes, lo primero antes que nada es generar la secuencia, para esto puedes usar 5 fors anidados o recursividad, y guardarlos ya sea en un map<string, int>  que contenga el indice en el orden que fueron creados o en un simple array para que luego en cada query hagas un binary search en esa secuencia.

Ahora finalmente queda decir que las soluciones propuestas no tienen que ser las mejores, si cuentan con una mejor solución nos gustaria que la compartan, de esa forma todos nos beneficiariamos por eso para preguntas y sugerencias sobre las soluciones de este contest porfavor escribirnos a:

http://codebreakerscorp.foroperu.org/concursos-f4/

Los comentarios aqui nomas😀

Otros Links Importantes:

DP: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

DP: http://people.csail.mit.edu/bdean/6.046/dp/

BFS y otros metodos de busqueda: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2

Sieva: http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes

Comments
  1. Digberth says:

    puxa hubo siempre?? :S, a mi me aparecia servidor no encontrado jajaja y me fui, bueno sera para la siguiente😛. Saludos.

  2. A. M. Santos R. says:

    Aunque ya soy un veterano en programming contests xD, voy a estar participando regularmente. El de hoy me lo perdí.

    Keep solving!

  3. Tatanka2011 says:

    Hola gente,

    Mis felicitaciones por este contest, he estado acompañandolos, y felicitaciones a Rubens, creo que la gente de la Cato se enteró tarde, y los de la UCSP también, pero han prometido estar en la próxima, así que si avisamos con unos tres días de anticipación tendremos más participantes.

    Saludos,

    César

  4. Figo says:

    Waaa…!!, me la perdí, weno esta ves fue por motivos familiares pero para la proxima estoy presente ,xD! , pense que digbert ganaria pero acabo de llegar de viaje y veo que no participo -.-!, bueno sera para la proxima, con mas gente de la cato xD!

  5. ness says:

    buena iniciativa😀

  6. Jainor says:

    Me la perdi!!!,pense k seria en la nochep, anteayer viaje y no chekie, espero participar en la proxima, Felicitaciones al ganador 😀

  7. Paul says:

    Hola muchas felicidades por su blog, es muy interesante… me gustaria saber como puedo participar en los AQP contest ??😀 yo tambien quiero ir al mundial de la acm icpc !!! he entrenado un poco en tju pero me gustaria sabes que son los AQP CONTEST Y SI PUEDO APRTICIPAR EN ELLOS COMO ENTRENAMIENTO ??

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