Links útiles
- Info de la competencia http://torneoprogramacion.com.ar
- Enunciados http://torneoprogramacion.com.ar/wp-content/uploads/2017/10/tap2017.pdf
- Scoreboard http://torneoprogramacion.com.ar/2017/10/05/resultados-tap-2017/
- Juez online para enviar soluciones http://redprogramacioncompetitiva.com/contests/2017/11/
Solucionario
A
Si ponemos simplemente las notas en un arreglo [do, do#, re, re#, mi, fa, fa#, sol, sol#, la, la#, si], podemos encontrar la respuesta encontrando la nota actual y restando S posiciones. Si la respuesta queda negativa, simplemente sumamos 12. Otra opción es copiar el arreglo una 2da vez para evitar este caso borde o trabajar con el módulo.
Código: https://pastebin.com/gFzPsdbL
Código: https://pastebin.com/gFzPsdbL
B
Consideramos los Pi en orden creciente ( Pi <= Pj , i0). Podemos ubicar el primer pirata que no es satisfecho por cada cofre buscando el upper bound de Ci en P (luego de ordenar P). Esto tiene una complejidad de NlogN (logN por cada upper_bound).
Con el procesamiento que hicimos podemos saber cuantos cofres podríamos asignar a cada pirata. Analicemos los Pi de derecha a izquierda (comenzando por el más grande) y empecemos a asignar cofres. La cantidad de opciones que barajamos para asignarle cofre al pirata i es la cantidad de cofres mayor o igual a sus requerimientos menos la cantidad de cofres ya asignados a los piratas de su derecha (n-i-1).
Complejidad: O(NlogN)
Código: https://pastebin.com/YrU2PS6G
Con el procesamiento que hicimos podemos saber cuantos cofres podríamos asignar a cada pirata. Analicemos los Pi de derecha a izquierda (comenzando por el más grande) y empecemos a asignar cofres. La cantidad de opciones que barajamos para asignarle cofre al pirata i es la cantidad de cofres mayor o igual a sus requerimientos menos la cantidad de cofres ya asignados a los piratas de su derecha (n-i-1).
Complejidad: O(NlogN)
Código: https://pastebin.com/YrU2PS6G
C
*g[i] es lo que quiere cada amigo.
*a[i] es la cantidad usada en cada cebada.
Las diferencias g[i] - g[i-1] determinan cuánto debe valer a[i] - a[i-k(mod N)].
Sea D = gcd(N,K), como sabemos las diferencias cada K elementos, podemos seguir ese ciclo (i, i+k, i+2k, …. (módulo N)) hasta saber todas las diferencias entre elementos de diferencia D.
Elegimos el ciclo que empieza en 0, con diferencia D. Con lo dicho antes podemos encontrar el más pequeño de ese ciclo y suponer que es 0. De esta manera ninguno de todo el ciclo puede ser menor ya que todos los a[i] deben ser positivos. Lo único que podemos hacer es sumarle una cantidad entera a cada elemento de ese ciclo. Hacemos lo mismo con cada ciclo.
Como ya sabemos las diferencias, solo tenemos que ver si es posible cumplir las necesidades de alguno de los amigos y ahí cumpliríamos todas. Para esto vemos algún amigo en particular. Si la suma de los a[i] mínimos supera lo que quiere ese amigo, requeriríamos cebadas negativas, IMPOSIBLE. Si da justo, es posible (cada ciclo tiene un elemento mínimo en 0.
Si es menor, necesitamos aumentar los valores de los ciclos. Sea C = K/D, la cantidad de elementos del mismo ciclo que hay cada K elementos. Si lo que necesitamos aumentar es múltiplo de C, es POSIBLE, modificando cualquiera de ese ciclo. Si no, tendríamos que hacer cebadas fraccionarias, lo cual es IMPOSIBLE.
Código: https://pastebin.com/Xq6TPWsB
*a[i] es la cantidad usada en cada cebada.
Las diferencias g[i] - g[i-1] determinan cuánto debe valer a[i] - a[i-k(mod N)].
Sea D = gcd(N,K), como sabemos las diferencias cada K elementos, podemos seguir ese ciclo (i, i+k, i+2k, …. (módulo N)) hasta saber todas las diferencias entre elementos de diferencia D.
Elegimos el ciclo que empieza en 0, con diferencia D. Con lo dicho antes podemos encontrar el más pequeño de ese ciclo y suponer que es 0. De esta manera ninguno de todo el ciclo puede ser menor ya que todos los a[i] deben ser positivos. Lo único que podemos hacer es sumarle una cantidad entera a cada elemento de ese ciclo. Hacemos lo mismo con cada ciclo.
Como ya sabemos las diferencias, solo tenemos que ver si es posible cumplir las necesidades de alguno de los amigos y ahí cumpliríamos todas. Para esto vemos algún amigo en particular. Si la suma de los a[i] mínimos supera lo que quiere ese amigo, requeriríamos cebadas negativas, IMPOSIBLE. Si da justo, es posible (cada ciclo tiene un elemento mínimo en 0.
Si es menor, necesitamos aumentar los valores de los ciclos. Sea C = K/D, la cantidad de elementos del mismo ciclo que hay cada K elementos. Si lo que necesitamos aumentar es múltiplo de C, es POSIBLE, modificando cualquiera de ese ciclo. Si no, tendríamos que hacer cebadas fraccionarias, lo cual es IMPOSIBLE.
Código: https://pastebin.com/Xq6TPWsB
D
El primer paso es observar cuál va a ser la estrategia para ganar dinero. Lo que se debe hacer es comprar dólares en una ciudad y venderlos en otra, COMPLETAMENTE. La estrategia consiste en hacer este paso repetidas veces de forma de tener cada vez más.
En segunda instancia hay que ver el carácter binario del problema (en este caso es ver que con menos de lo mínimo no voy a poder pero con más de lo mínimo siempre se va a poder), esto siempre es un fuerte indicio de que hay que aplicar búsqueda binaria. Por esta razón realizamos búsqueda binaria para encontrar el mínimo. Ahora, como es la función de evaluación? Es decir, cómo evaluamos si al iniciar con x cantidad de pesos podemos volvernos infinitamente ricos?
Para hacer esto se tiene que tomar en cuenta la estrategia mencionada al principio, esto limita considerablemente las posibilidades a tener en cuenta. Resulta que modelar esta estrategia se vuelve simple creando un grafo ‘especial’ con las ciudades, recorrer una arista en este grafo será equivalente a hacer un paso de nuestra estrategia.
Es recomendable hacer un Floyd-Warshall para pre-calcular la distancia mínima entre dos ciudades cualesquiera, utilizando estas distancias nuestro algoritmo tiene en cuenta rutas entre ciudades indirectas.
El grafo es ‘especial’ porque los pesos de las aristas no son distancias sino que guardan cuánto podemos aumentar nuestro dinero actual. Si en la ciudad X el cambio está 1 a 20 y en la Y 1 a 17, y nuestro dinero es Z, entonces recorrer la arista X->Y modificaría nuestro dinero a Z*20/17-dist(X, Y). Una vez construido el grafo, la función de evaluación consiste en aplicar Bellman-Ford desde nuestro nodo inicial, para encontrar ciclos infinitos. Notar que no es necesario buscar explícitamente el ciclo, basta con ver si luego de N-1 iteraciones el nodo inicial tiene más dinero que con el que se comenzó.
Para hacer esto se tiene que tomar en cuenta la estrategia mencionada al principio, esto limita considerablemente las posibilidades a tener en cuenta. Resulta que modelar esta estrategia se vuelve simple creando un grafo ‘especial’ con las ciudades, recorrer una arista en este grafo será equivalente a hacer un paso de nuestra estrategia.
Es recomendable hacer un Floyd-Warshall para pre-calcular la distancia mínima entre dos ciudades cualesquiera, utilizando estas distancias nuestro algoritmo tiene en cuenta rutas entre ciudades indirectas.
El grafo es ‘especial’ porque los pesos de las aristas no son distancias sino que guardan cuánto podemos aumentar nuestro dinero actual. Si en la ciudad X el cambio está 1 a 20 y en la Y 1 a 17, y nuestro dinero es Z, entonces recorrer la arista X->Y modificaría nuestro dinero a Z*20/17-dist(X, Y). Una vez construido el grafo, la función de evaluación consiste en aplicar Bellman-Ford desde nuestro nodo inicial, para encontrar ciclos infinitos. Notar que no es necesario buscar explícitamente el ciclo, basta con ver si luego de N-1 iteraciones el nodo inicial tiene más dinero que con el que se comenzó.
E
Este problema tiene dos soluciones. Una es probar, a cada momento, todas las combinaciones posibles de cartas a jugar con el objetivo de maximizar la cantidad de manos a ganar de cada uno de los jugadores. La fuerza bruta no tarda mucho tiempo.
Y la otra es hacer los casos a mano.
* Si Eduardo no tiene el 1, excepto el caso 2-3-4, su abuelo (como puede tener el 1 y una del {2,3,4}) puede dejarle ganar posiblemente la primera mano para encajar {2,3,4} con la carta débil de Eduardo y ganar la otra mano con el 1 en las dos últimas.
* Si Eduardo tiene el 1, tiene que ganar alguna otra mano más. No es difícil ver que le conviene tirar la más baja para tener la mayor cantidad de chances de jugar su 2da mejor carta contra la que le convenga de su abuelo una vez que este le gane la 1er mano. Y hay que analizar los distintos casos.
Hubo soluciones aceptadas que solo contenían 3 ifs.
Código: https://pastebin.com/1gHDXh2X
https://pastebin.com/ADCi0UhJ
Y la otra es hacer los casos a mano.
* Si Eduardo no tiene el 1, excepto el caso 2-3-4, su abuelo (como puede tener el 1 y una del {2,3,4}) puede dejarle ganar posiblemente la primera mano para encajar {2,3,4} con la carta débil de Eduardo y ganar la otra mano con el 1 en las dos últimas.
* Si Eduardo tiene el 1, tiene que ganar alguna otra mano más. No es difícil ver que le conviene tirar la más baja para tener la mayor cantidad de chances de jugar su 2da mejor carta contra la que le convenga de su abuelo una vez que este le gane la 1er mano. Y hay que analizar los distintos casos.
Hubo soluciones aceptadas que solo contenían 3 ifs.
Código: https://pastebin.com/1gHDXh2X
https://pastebin.com/ADCi0UhJ
F
Existen distintas soluciones a este problema pero la que considero más simple es calculando el complemento. Es decir en lugar de calcular cuánta felicidad hay dentro del intervalo pedido llamémosle [S, E], mejor cálculo la felicidad total y le resto la que queda afuera de ese intervalo. Resulta que esto último es ligeramente más simple: lo que ‘queda afuera’ se puede subdividir en dos conjuntos DISJUNTOS: los recitales que terminan antes que S, y los recitales que empiezan luego de E. Si voy manteniendo un contenedor con sólo los comienzos de los recitales y otro para los finales de los recitales esto debería ser fácil. Tal contenedor podría implementarse con un segment tree o un árbol balanceado.
G
A primera vista el problema tiene pinta de ser una combinatoria resuelta a partir de programacion dinamica. Podemos pensar que si tuviéramos una dinámica de la forma:
f( x , p1, p2 ) que sea la cantidad de formas de que se obtenga un resultado p1,p2 con x rondas tendríamos la solución al problema en f(N,P1,P2). Esto lo podríamos calcular en O(M) por estado. Pero la complejidad total seria O(P^2*N*M) lo cual es demasiado.
Notar que en esa dinámica p1 y p2 son bastante independientes. Podemos calcular g(x, p1) la cantidad de formas de obtener p1 en x rondas no nulas para un solo jugador. Esto lo haríamos en O(M) en cada paso, con una complejidad total de O(P*N*M).
Luego podemos contar el total de juegos con resultados P1, P2 en N rondas (la respuesta al problema) analizando los casos con x rondas no nulas para el jugador 1 e y rondas no nulas para el jugador 2 y sumar todas (son disjuntas evidentemente) con x+y<=N. Para saber cómo las distribuimos en N formas las x e y tenemos comb[N][x]*comb[N-x][y], teniendo un total de g(x,P1)*g(y,P2)*comb[N][x]*comb[N-x][y]. Con una complejidad O(N^2) pre calculando los combinatorios en O(N^2) también.
Complejidad: O(P*N*M + N^2)
Código: https://pastebin.com/1i7JwYtg
Luego podemos contar el total de juegos con resultados P1, P2 en N rondas (la respuesta al problema) analizando los casos con x rondas no nulas para el jugador 1 e y rondas no nulas para el jugador 2 y sumar todas (son disjuntas evidentemente) con x+y<=N. Para saber cómo las distribuimos en N formas las x e y tenemos comb[N][x]*comb[N-x][y], teniendo un total de g(x,P1)*g(y,P2)*comb[N][x]*comb[N-x][y]. Con una complejidad O(N^2) pre calculando los combinatorios en O(N^2) también.
Complejidad: O(P*N*M + N^2)
Código: https://pastebin.com/1i7JwYtg
H
Si no hubiera números consecutivos iguales se puede ver que podemos garantizar que existe una montaña con la presencia de una cúspide (es decir un numero v[i] que es mayor que su predecesor y sucesor). Entonces eliminamos (como si comprimiéramos) consecutivos repetidos y contamos la cantidad de cúspides. Para qué predecesor y antecesor este definido en caso de que solo haya un número podemos considerar 0 auxiliares en los extremos.
Complejidad: O(N)
Código: https://pastebin.com/jiqn0v02
Complejidad: O(N)
Código: https://pastebin.com/jiqn0v02
I
Para determinar si son similares hay que notar que los puntos pueden llegar a lo sumo ser una rotación de los originales (o una rotación invertida). Podemos probar con cada una de las rotaciones posibles (y su rotación invertida) chequeando si se corresponde con la original. Para hacer el chequeo basta con comprobar que los ángulos internos son iguales y que los lados son proporcionales.
J
Lo primero que hay que notar es que por cada nombre N, como no es compartido y cada jurado tiene sólo 2 nombres, tiene que tener un opuesto N’ (N’ esté presente en cada edición si y solo sí no esté N).
Entonces si le podemos asociar a cada nombre un posible opuesto (con el caso especial de los nombres que estén siempre), claramente es posible que siempre hayan sido los mismos (lo probamos constructivamente). Caso contrario no.
Para esto, podemos guardar para cada nombre una lista de apariciones y simplemente buscar un posible opuesto y eliminar ambos hasta que no quede ningún nombre disponible.
Código: https://pastebin.com/r5pPqGXT
Entonces si le podemos asociar a cada nombre un posible opuesto (con el caso especial de los nombres que estén siempre), claramente es posible que siempre hayan sido los mismos (lo probamos constructivamente). Caso contrario no.
Para esto, podemos guardar para cada nombre una lista de apariciones y simplemente buscar un posible opuesto y eliminar ambos hasta que no quede ningún nombre disponible.
Código: https://pastebin.com/r5pPqGXT
K
Sea M la cantidad de elementos impares en el arreglo.
*Para M = 0 la respuesta es 0. Supongamos M >= 1.
- Se pueden convertir a todos los elementos en pares haciendo M + 1 operaciones de la siguiente forma:
* Si M = 1: dividimos el único número impar a[i] y multiplicamos alguno de los pares a[j] (existe porque N >= 2). Después dividimos a[j] y multiplicamos a[i].
* Si M > 1: Seleccionamos 2 impares, uno se divide, otro se multiplica. Nos queda un impar menos gastando una operación. Repetimos esto hasta que M <= 1.
Lema.: la respuesta es <= M si y sólo si existe algún a[i] (par o impar) y un k (1 <= k <= M) tal que el k-ésimo bit de a[i] es 0.
Dem (super resumida):
* (=>) Supongamos que no existen a[i] y k como se describen arriba. Supongamos que aplicamos M operaciones o menos. Necesitamos multiplicar cada impar (las divisiones no generan pares) plus una extra previa para el último número que dividimos. Contradicción, necesitamos más de M.
* (<=) Sea i el índice descrito, y k el bit. Aplicamos M-k veces el protocolo de tocar otros dos impares (uno lo dividimos, otro lo multiplicamos). Finalmente dividimos k veces el a[i] mientras que multiplicamos impares. Luego de a lo sumo M operaciones (dependiendo de si a[i] era impar) se obtienen todos pares.
Ahora que sabemos que la rta <= M, a cada impar se le asigna un valor g[i] que es la cantidad mínima de divisiones que necesita para hacerse par.
Se puede demostrar que, dada R la respuesta, el algoritmo que “parifica multiplicando” R impares y “parifica dividiendo” los M-R restantes es posible si y sólo si la sumatoria de los g[i] (de los M-R) es menor o igual a R.
* Por lo tanto se puede aplicar el algoritmo greedy para encontrar la solución que “parifica dividiendo” los de menor g[i].
Código: https://pastebin.com/VSTUxsDY
*Para M = 0 la respuesta es 0. Supongamos M >= 1.
- Se pueden convertir a todos los elementos en pares haciendo M + 1 operaciones de la siguiente forma:
* Si M = 1: dividimos el único número impar a[i] y multiplicamos alguno de los pares a[j] (existe porque N >= 2). Después dividimos a[j] y multiplicamos a[i].
* Si M > 1: Seleccionamos 2 impares, uno se divide, otro se multiplica. Nos queda un impar menos gastando una operación. Repetimos esto hasta que M <= 1.
Lema.: la respuesta es <= M si y sólo si existe algún a[i] (par o impar) y un k (1 <= k <= M) tal que el k-ésimo bit de a[i] es 0.
Dem (super resumida):
* (=>) Supongamos que no existen a[i] y k como se describen arriba. Supongamos que aplicamos M operaciones o menos. Necesitamos multiplicar cada impar (las divisiones no generan pares) plus una extra previa para el último número que dividimos. Contradicción, necesitamos más de M.
* (<=) Sea i el índice descrito, y k el bit. Aplicamos M-k veces el protocolo de tocar otros dos impares (uno lo dividimos, otro lo multiplicamos). Finalmente dividimos k veces el a[i] mientras que multiplicamos impares. Luego de a lo sumo M operaciones (dependiendo de si a[i] era impar) se obtienen todos pares.
Ahora que sabemos que la rta <= M, a cada impar se le asigna un valor g[i] que es la cantidad mínima de divisiones que necesita para hacerse par.
Se puede demostrar que, dada R la respuesta, el algoritmo que “parifica multiplicando” R impares y “parifica dividiendo” los M-R restantes es posible si y sólo si la sumatoria de los g[i] (de los M-R) es menor o igual a R.
* Por lo tanto se puede aplicar el algoritmo greedy para encontrar la solución que “parifica dividiendo” los de menor g[i].
Código: https://pastebin.com/VSTUxsDY
L
Este problema consta de dos partes. Una es encontrar las 6 combinaciones posibles de bolsitas que se pueden armar, a las que enumeramos:
1. LLLL
2. OOOO
3. TTTT
4. LLSS
5. LSTT
6. LLOO
Podemos suponer greedymente que los paquetes 5 y 6 están a lo sumo una vez, puesto que si no también existe una solución usando los paquetes (3,4) y (1,2) respectivamente por cada parcito de los anteriores que da lo mismo.
A partir de ahí, es fácil ver que si seguimos el orden 4-3-2-1 encontramos la solución óptima. Por lo tanto solo es necesario probar los 4 casos sobre la paridad de bolsas hechas con p5 y p6 y seguir con el algoritmo.
También hay una solución sin probar los 4 casos que sigue un orden greedy particular de eliminación que se la deja al lector como ejercicio.
Código: https://pastebin.com/cFVUDHBH
1. LLLL
2. OOOO
3. TTTT
4. LLSS
5. LSTT
6. LLOO
Podemos suponer greedymente que los paquetes 5 y 6 están a lo sumo una vez, puesto que si no también existe una solución usando los paquetes (3,4) y (1,2) respectivamente por cada parcito de los anteriores que da lo mismo.
A partir de ahí, es fácil ver que si seguimos el orden 4-3-2-1 encontramos la solución óptima. Por lo tanto solo es necesario probar los 4 casos sobre la paridad de bolsas hechas con p5 y p6 y seguir con el algoritmo.
También hay una solución sin probar los 4 casos que sigue un orden greedy particular de eliminación que se la deja al lector como ejercicio.
Código: https://pastebin.com/cFVUDHBH