Página 1 de 1

Google Codejam Qualification Round 2018

Publicado: 09 Abr 2018, 16:09
por luisvasquez
Este último fin de semana se llevó a cabo la primera etapa del concurso de programación competitiva de google, el Google Codejam dicha etapa es la Qualification Round, este año contamos con una nueva plataforma, una más amigable y cuyo sistema de evaluación es más simple que antes ya no es necesario enviar las salidas de los problemas.

Para poder clasificar uno necesita obtener al menos 25 puntos de 100 puntos en total, el concurso duró 27 horas y hubieron 4 interesantes problemas, cada problema tiene 2 tipos de entradas, la entrada pequeña y la entrada grande, la entrada pequeña es juzgada al instante del envió y la entrada grande es juzgada al final del concurso. Esto significa que para resolver la entrada pequeña no significa necesariamente que el envío grande será correcto, uno tiene que hacer un algoritmo lo suficientemente eficiente para resolver la entrada grande.

https://codejam.withgoogle.com/2018/

Los problemas

Problema #1 Saving The Universe Again
Small input: 5 points.
Large input: 10 points.
Descripción del enunciado:

En este problema tenemos que defender la tierra de un ataque extraterrestre, los aliens tienen un rayo solar y nosotros tenemos un escudo cuya capacidad se modela como un número entero.El rayo solar tiene una cierta fuerza inicial(otro número entero) con la cual puede dañar el escudo puede recibir 2 comandos, el comando 'C' charge el cual duplica la fuerza del rayo solar, el comando 'S' shoot ejecuta un ataque a la tierra y hace un daño al escudo equivalente a la fuerza actual. Tenemos una secuencia de caracteres 'C' y 'S' el cual representa los comandos que ejecutarán los aliens en orden. Nos dicen que podemos hacer swaps de caracteres adyacentes a la secuencia. El problema nos pide hallar la mínima cantidad de swaps de tal manera que cuando la secuencia de comandos la tierra sea defendida por el escudo.
Solución:
Una observación clave es que los pares CS son los únicos que nos interesan cambiar, los pares CC, SS básicamente no modifican la secuencia y la secuencia SC empeora las cosas ya que este aumenta la fuerza total del rayo solar.
La idea es hacer un algoritmo goloso(Greedy), en cada iteración buscar el par CS que se encuentre más a la derecha y aplicar un swap, si en algún momento el escudo es capaz de cubrir la fuerza total o el algoritmo no encuentra algún par CS paramos el algoritmo.

Problema #2 Trouble Sort
Small input: 8 points.
Large input: 15 points.
Descripción del enunciado:
Tenemos un algoritmo de ordenamiento muy parecido al bubble Sort que no siempre ordena las secuencias, nos piden verificar si dicho algoritmo ordena una secuencia dada, en caso no ordene la secuencia debemos imprimir el primer mismatch de la secuencia.
Solución:
Viendo el pseudocódigo de dicho algoritmo nos podemos dar cuenta que si partimos la secuencia original en dos secuencias, en la primera secuencia ponemos en el mismo orden que aparecen los elementos de las posiciones pares y en la otra los elementos de las posiciones impares, en realidad lo que hace dicho algoritmo es por cada secuencia el algoritmo aplica un bubblesort entonces la solución simplemente es dividir esas dos secuencias ordenarlas y luego volverlas a poner en una misma secuencia, luego comparar esta secuencia obtenida con la secuencia original pero ordenada.

Problema #3 Go, Gopher!
Small input: 10 points.
Large input: 20 points.
Descripción del enunciado:
En este problema tenemos que cubrir exactamente una grilla rectangular de área al menos 200, lo que podemos hacer en una consulta es mandar un topo a la coordenada x,y a continuación el topo equi-probablemente escoge una de las grillas en las coordenadas i,j donde se cumple que |x - i| <= 1 && |y - j| <= 1, es decir escoge una de las nueve posiciones de un cuadrado de 3x3 con centro en x,y. En el problema podemos ejecutar hasta 1000 consultas.El mecanismo aleatorio que hace el topo escoger se representa en este problema con una interacción(ver problemas interactivos).
Solución:
Primero fijamos el rectángulo que queremos llenar, para llenar el rectángulo tenemos que hacer consultas solamente dentro del rectángulo excepto los bordes. Para evitar las colisiones(es decir que una consulta cubra una casilla que ya fue cubierta) dentro del rectángulo buscamos los centros que tengan la mayor cantidad de grillas vacías.

Problema #4 Cubic UFO
Small input: 11 points.
Large input: 21 points.
Descripción del enunciado:

Este es un problema de geometría en 3D tenemos un cubo cuyo lado mide 1 km con centro en el eje de coordenadas el cual representa una nave espacial, la tierra se supone el plano y = -3, suponiendo que el sol se encuentra infinitamente lejos a lo largo del eje y positivo dicho cubo genera una sombra de cierta área, lo que nos piden es girar el cubo de tal manera que el área de dicha sombra sea igual a un número real que nos dan.
Solución:
Inicialmente el cubo está en una posición básica y el área de la sombra es 1 ya que una de sus caras es paralela al plano y = -3, si consideramos un vector unitario normal a dicho plano y giramos dicho vector junto al cubo tendremos dos cosas dado que dicho vector v = (x, y, z) es un vector unitario su lugar geométrico es el de la esfera unitaria con centro en el eje de coordenadas osea x^2 + y^2 + z^2 = 1, luego dicha sombra se puede calcular mediante una integral como |x| + |y| + |z| = P donde P es el área que nos piden. Si tomamos x >= 0 && y >= 0 && z >= 0, se la ecuación |x| + |y| + |z| = P se convierte en x + y + z = P la cual es la ecuación de un plano, si interceptamos dicha esfera y plano tendremos una circunferencia y cualquier punto de esa circunferencia sería una solución al problema, ahora solo que ya tenemos el vector de rotación tenemos que rotar el cubo.


Consideraciones finales
La tabla de resultados se puede ver aquí https://codejam.withgoogle.com/2018/cha ... scoreboard
Breve resumen de sud-américa.

Rank Nationality Nickname Points Penalty
565 Argentina zylber 100 22:45:30
585 Argentina mjhun 100 23:04:35
698 Perú Boxer 100 25:47:53
978 Brasil marcoskwkm 79 2:46:48
1073 Perú alei 79 5:51:37

Debido a que es una nueva plataforma algunos features no están completos, por ejemplo no se puede filtrar por país o seleccionar amigos.Los organizadores dijeron que en cuestión de días dichos features serán implementados.

Un interesante resumen sobre esta ronda se puede ver aquí https://codejam.withgoogle.com/2018/cha ... b/analysis
La próxima etapa será la Ronda 1A que se llevará a cabo el 14 de abril del 2018.
Suerte a todos los participantes.