Esta competencia nos resultó entretenida. Los problemas eran muy lindos!
 |
| scoreboard en la posmaratón de la competencia |
Link a los problemas
https://drive.google.com/file/d/0ByI9GfoY63_aVlJmbmNPdGJHYWM/view?usp=sharing
Juez modo posmaratón
https://acm.javeriana.edu.co/maratones/2015/11/
Soluciones
A: Alcoholic Pilots
Este era el trivial de la competencia.
B: Bargaining
Podemos reducir este problema a que comenzamos con un rectángulo de E x D, nuestro polígono inicial. Cada ecuación nos define una recta. Para cada una de estas rectas debemos 'cortar' el polígono y quedarnos con la parte deseada. Se puede cortar un poligono con una recta en O(n), solo basta ver de que lado quedan los extremos de las aristas. (Si quedan en lados diferentes hay que calcular la intersección entre la arista y la recta). Finalmente imprimir el área del poligono final.
C: Cuban Challenge
Acá hay un grafo bipartito! Si pintamos las casillas como un tablero de ajedrez, una pieza de domino SIEMPRE 'conecta' dos casillas de diferente color. En el grafo tenemos por un lado las casillas blances y del otro las negras. Unimos dos casillas si se puede poner una pieza de domino que las cubra. El problema se reduce a calcular el matching maximo sobre este grafo (pues queremos cubrir la mayor cantidad de casillas)
D: Drinking Game
Primero que nada siempre vamos a poder poner un 1 cada número, total gcd(x, 1)=1 para todo x>0. En base a esto la observación más importante es que como los números son menores a 20, nunca voy a poner un número mayor o igual a 39, pues en vez de sumarle 19, le resto 19 y tengo un 1 que me hace menos problema. En base a esto podemos hacer una DP que pruebe todo. Para ver si puedo poner un número, en vez de llevar los números que ya use y ver si es coprimo con todos ellos, me conviene hacer otra cosa. Un número es coprimo con otro si sus factorizaciones no tienen ninguno primo en común. Usando esto puedo llevar los primos ya usados y ver para cada número entre 1 y 39 si lo puedo usar o no. Si lo puedo usar puedo agregar los nuevos primos usados por este número a los que ya tenía y llamar a la DP en la siguiente posición con estos nuevos .
Como los primos que pueden ser usados son los <=39, (los cuales son muy pocos), puedo guardar los usados con una máscara de bits. Nuestra dp quedaría dp[posicion][primosusados].
E: Exquisite Strings
El problema consistía en dada una string S contar la cantidad de pares de subcadenas S[i..j] S[a..b], tales que las primeras k letras de ambas sean iguales (módulo 1000000007). Si clasificábamos los sufijos suf[i]=S[i..n-1] de más de k caracteres según su prefijo (lo podíamos hacer con hashing o con SA+LCP). Examinando un grupito de estos cualquier subcadena que tenga como prefijo los k primeros caracteres de estos sufijos del grupo se puede emparejar con cualquier otra de este grupo (y sólo con esas). Así que sí {i1, i2, ... im} formaban partes de este grupo calculabamos la sumatoria de sum=|S|-ik-k+1 (k=1..m). Luego total+=(sum*(sum-1)/2).
(Para hacer /2 módulo 1000000007 podemos multiplicar por 500000004).
F: File Transmission
Necesitamso tener en claro componentes biconexas.
Veamos que si dados dos nodos existen dos caminos dijuntos que los conectan entonces no tengo que agregar nada (pues mando 50gb por uno y 50gb por el otro). Esto es lo mismo que decir que si ambos nodos esten en una componente biconexa. Si en cambio nos dan dos nodos en distintas componentes biconexas la cosa cambia, tendriamos que 'salir' de la componente, pasar por algunos bridges (y otras componentes biconexas) y por último 'entrar' en la componente biconexa. Condensemos todos los nodos de una sola componente en uno solo (usando union-find por ejemplo). El grafo resultante es un árbol. Las aristas que quedan son los puentes. Ahora para responder la query tenemos que calcular la distancia entre las componentes a los cuales esos nodos pertenecen y multiplicarla por 50. Esto se puede hacer usando LCA.
G: Greedy Artisan
Este problema sale Greedy. Primero ordenamos las matryoshkas por las condiciones que nos dice. Luego de elegir la matryoshka más pesada, la elección de las otras a comprar es greedy.
H: Heavy Luggage
Esto sale con matrices. Imaginemos que nos dan un estado x en un vector de tamaño n (nos indica cuanto peso tiene cada persona).
Entonces se puede calcular fácilmente a partir del grafo el estado siguiente x' (hacer cuentitas). Más aún podemos construir una matriz P / Px=x'
Si P no es inversible quiere decir que hay multiples soluciones (imprimir lost luggage!)
Supongamos que P es inversible. Entonces (P^-1) x' = x
Volviendo al problema, si nos dan el estado final f. Podemos hacer ((P^-1)^k) f y obtenemos el estado inicial, la respuesta al problema.
Queda para analizar como resolver los problemas de precision dado que nos dan un número con 200 dígitos.
I: Incredulous Ed
Dado los números pequeños, podemos hacer simplemente fuerza bruta y probar todas las secuencias posibles. Una forma es hacer una función f(posicion, usados) donde usados es una mascara de bits que indica que números (del 1 al 9) fueron usados por la secuencia y posicion es donde hay que poner el siguiente número. Agregamos el número y llamamos recursivamente en posicion+1 (solo si agregarlo genera una secuencia valida lo cual es chequeable con usados)
J: Jair vs Chadan
El problema de este es que era difícil de entender. La idea central es esta: si yo tengo un juego en donde se va formando un número desde los digitos más significativas hasta los menos. En cada paso yo tengo un conjunto de digitos para elegir. Si yo quiero máximizar el número que se forme, que es lo que me conviene hacer? Es obvio que tengo que elegir el digito más grande, SIN importar lo que pase después. El problema se resuelve basicamente simulando el juego y usando una estrategia así para cada jugador.
K: Keypad Problem
Este problema es una generalización complicada del algoritmo de Euclides extendido. El número se va a poder formar si es múltiplo del máximo común divisor del conjunto de todos los números. https://es.wikipedia.org/wiki/Algoritmo_de_Euclides. Para no tener problemas de overflow, nosotros aplicamos dos heurísticas. Primero disminuir el número objetivo al mínimo posible, asignando greedymente algunas combinaciones. Y luego, se puede demostrar que usando a lo sumo log (20000)=15 números, alcanza para generar el objetivo. Usando un método divide and conquer, podés lograr multiplicar a lo sumo 4 veces (log 15), logrando no tener problemas de overflow. También es posible lograr una solución “menos bonita” usando big integer.
0 comentarios: