Éste es el orden de dificultad (creciente) de los problemas que pensé aún antes del TAP (fui problemsetter!):
A, J / L, C, F, H, B, G / D, E, I, K. Muy probablemente difiera con lo que muchos piensen pués es una prueba dónde se han concentrado mucho los problemas en la franja media (abarcando muy bien el espectro de medio-fácil a medio-difícil).
Pienso que en general ha sido una muy bella prueba con problemas muy divertidos y creo que podría hablar por todos los problemsetters si digo que todo salió bastante bien.
 |
| Los equipos compitiendo en la sede de Rosario |
A continuación el solucionario, que hicimos junto a Martín.
Problema A
(ad hoc)
El problema trivial. Imprimir "S" o "N" según si había o no la letra 'i'.Solución Python de una línea:
print("SN"["i"in input()])
Problema B
(programación dinámica)
- Dividimos los puntos que no son E ni S en dos conjuntos: A = { E+1, E+2, ... S-1 } (mod N) y B = { E-1, E-2, ... S+1 } (mod N)- Sea A_i y B_i los i-esimos de los respectivos conjuntos en el orden mencionado (partiendo desde E), observar que el recorrido óptimo recorre los A_i y B_i en orden.
- El problema puede resolverse con programación dinámica en N^2.
- La recursion nos queda de la forma f(i,j,flag) respuesta óptima de llegar a S habiendo recorrido hasta A_i del conjunto A y B_i del conjunto B, flag indica si nos encontramos en i o j.
- Se podría prescindir de flag ya que dado un par (i,j) sin saber cual corrresponde a A y cual a B podemos determinarlo (los puntos son bien de A y otros de B) y podemos considerar que la segunda componente del par es el elemento donde nos encontramos.
Problema C
(DFS)
- Guardamos para cada materia la cantidad de correlativas no aprobadas y marcamos como no aprobadas a todas las materias.- Al principio la respuesta de cantidad de materias en el sistema es 0.
- Cada vez que aprobamos una materia la marcamos como aprobada y la "procesamos". El procesamiento consiste en ver si está aprobada y la cantidad de correlativas no aprobadas es 0, de ser así incrementamos la respuesta, disminuimos en 1 la cantidad de correlativas no aprobadas de sus hijos y los procesamos.
- Ver que la condición del procesamiento se satisface sólo una vez. Luego sólo una vez se recorrerán a sus hijos. El procesamiento es invocado sólo por el padre y cuando se aprueba la materia. La complejidad es O(N+M).
Problema D
(geometría, giro ó intersección círculos ó set)
- Para cada par de puntos (x,y) calculamos todos los posibles valores de lados de un triángulo semejante al original con un lado igual al segmento formado por estos puntos (6 casos).- Podemos utilizar intersección de círculo para determinar donde se encontrarían el tercer punto (dos posibilidades para cada elección de lados).
- Chequeamos si estos puntos existen en nuestro input. Lo podemos hacer con un set en O(log(N)).
- Complejidad: O(N^2 log(N)).
- Tener cuidado de no estar contando repetidos. Tener en cuenta el caso donde el triángulo usado es isósceles.
Solucion alternativa:
Esta solución me dio AC, según mi análisis de complejidad es O(N^3). Aunque puede que las restricciones propias de la geometría euclídea y puntos enteros hagan que sea mucho menor.
- Creamos map< long long, bitset<1000> > mp[MAXN]. Donde para cada vertice v y distancia a otro vertice d mp[v][d] representa el conjunto de vertices a distancia d de v con subíndice mayor que v.
- Para cada par de puntos (x,y) calculamos por proporcionalidad todos los posibles valores de lados de un triángulo semejante al original con un lado igual al segmento formado por estos puntos (6 casos). Este punto es igual a la solucion anterior. Ver que solo nos importan si estas distancias al cuadrado son enteras.
- Siendo l1 y l2 el tamaño de los lados para el par de vértice (x,y) obtenido en un caso del apartado anterior actualizamos la respuesta con size( interseccion(mp[x][l1],mp[y][l2]) ).
- Si usamos un unordered_map (mas el uso de bitset para representar conjuntos), la cantidad de operaciones es de N cubo. Aunque hay que resaltar que la interseccion posiblemente sea O(N) pero con una constante muy baja (1/64) por el uso de bitset. Además la intersección sólo se ejecuta si l1 y l2 calculados resultan enteros y además l1 y l2 existen como claves en mp[x] y mp[y] respectivamente. Lo cual no siempre sucede y hace más rápida a nuestra solución.
Problema E
(grafos DFS)
- La observación clave es: "Existe una cadena de botones que independientemente de donde me halle me lleve al 1 sí y sólo sí para todo par de estados existe una cadena de botones que independientemente de cual de los dos me halle me lleva al estado 1".- => trivial
- <= induccion sobre el conjunto de estados donde posiblemente estoy. La premisa me permite ir reduciendo en 1 la cantidad aplicando la cadena que me da.
- Luego si consideramos el grafo cuyos vertices son pares de aplicaciones (i,j) y existe una arista a (a,b) si apretando un boton paso del estado i al a y del j al b. (N^2 vértices N^2M aristas). Existe existe una cadena de botones que independientemente de cual de las dos aplicaciones A,B me halle me lleva a la 1 sii existe un camino (A,B) a (1,1).
- Tenemos que chequear que para todas las aplicaciones a,b del vertice (a,b) se pueda alcanzar el vertice (1,1) en el grafo descripto.
- El grafo tiene N^2 vertices y N^2M aristas. La complejidad total es de O(N^2M).
Problema F
(greedy)
Para resolver este problema se deben hacer primero varias observaciones.
1) Sólo las letras D y R importan, podemos eliminar todas
las demás letras.
2) Si hay dos D o dos R consecutivas en un nombre es lo mismo que solamente tener una.
3) La tercera es que si existe un DR en un nombre, entonces de forma greedy podemos pintar ambas letras de fucsia
(sumando 1 a la respuesta) y ya borrarla de la palabra.
Utilizando todas estas observaciones, los posibles nombres se reducen a tres: D, R y RD.
Resta
ver como combinar estas palabras de forma óptima. Si tenemos al menos
una D, se la puede juntar con una RD: DRD. Aplicando 3) esta DRD se
transforma en una D (y le suma uno a la respuesta).
Análogamente R+RD se transforma en R (sumando uno a la respuesta).
En
cambio si no tenemos ninguna R ni ninguna D, solamente nos queda juntar
las RD (aquí se desperdician las dos letras de los extremos).
Por último, cuando sólo nos quedan D's y R's, la cuenta es muy simple. La fórmula quedaría:
if(cant_RD>0){
if(cant_D+cant_R>0) ans += cant_RD
else ans += cant_RD - 1
}
ans += min(cant_D, cant_R)
Problema G
(trie)
- El costo en el camino es el xor del costo de las aristas.- Usando la promoción ir del nodo A al B cuesta lo mismo haciendo cualquier camino (usar dos veces un tramo sale gratis).
- Tomando una ráiz arbitraria R, costo(A,B) = costo(A,R) xor costo(B,R).
- Sean val[A] = costo(A,R) (podemos computarlo con un DFS). Ahora la respuesta para un nodo v es max_{a in V} val[a] xor val[v]. Este es un problema clásico lo podemos resolver pensando a cada val[v] como string de 0's y 1's y construyéndonos un trie con ellas (con el bit mas significativo a la izquierda). Luego para cada v obtenemos la respuesta utilizando el trie, siempre eligiendo el caracter más conveniente "encendiendo" bits en el resultado siempre que sea posible.
Problema H
(programación dinámica)
- Sea f(X,Y,N) la respuesta a nuestro problema podemos hacer programación dinámica.- Observar que f(X,Y,N) cuando Y>0 y N>1 depende solo posiblemente de f(X,Y-1,N-1) y f(X-1,Y-1,N-1) (cuando Y==0 o N==1 es un caso base). La cantidad de estados visitados es NN ya que Y y N son recuperables uno del otro.
- Tirar el parámetro que podemos recuperar y hacer la DP en N^2.
Problema I
(matemática, ec lineal modular, grafo, Prim)
La idea principal es esta: Imaginar un grafo donde los vértices son
las ranas y las aristas indican el tiempo (absoluto) en que esas dos ranas se
encuentran. Pensamos ahora como resolver el problema utilizando este grafo. Un algoritmo posible es
similar al Prim, comenzando desde la rana infectada. La idea es que en cada paso del Prim, de todas las ranas no infectadas se elija la se encuentre primero con una infectada, luego esta rana se infecta. Así el árbol recubridor representaría la historia de las infecciones.
En lugar
de generar el grafo explícitamente (el cual puede tener infinitas
aristas), para cada nodo expandido, buscaremos el tiempo de encuentro
con las ranas no infectadas. Es importante tomar en cuenta solamente los
encuentros después de que la rana fue infectada (razón por la cual este algoritmo no es exactamente Prim).
Resta ver como calcular los tiempos de encuentro:
Supongamos que tenemos dos ranas i y j, y queremos saber el próximo encuentro después del tiempo t, llamemosle t'.
Fijamos en que punto del patrón se van a encontrar: llamemosle m (es decir t'%K==m)
Calculamos
en que posición se encuentra cada rana en el tiempo t + el tiempo que
le lleva alcanzar el primer m, llamemosle p_i y p_j.
Si después de una ciclo completo del patrón la rana i avanza c_i charcos, se puede inferir que los puntos en los que t'%K==m
tienen la forma:
t' = p_i + x * c_i (mod n)
Utilizando estos datos podemos plantear la siguiente ecuación:
p_i + x * c_i = p_j + x * c_j (mod n)
Resolviendo esta ecuación es posible encontrar el primer tiempo de encuentro de las ranas (si es que existe).
Luego hacemos un for para todos los posibles m y tomamos el mínimo.
Problema J
(greedy)
- Ir poniendo las palabras en orden decreciente de longitud, empezando una nueva columna de ser necesario anchura igual a la palabra a insertar es óptimo.Problema K
(teoría de juegos, greedy ó programación dinámica)
Por simplicidad dividimos en dos partes la explicación.Parte I:
- Existe un único camino simple de M a P. Veamos el problema como un camino M <-> P y "subarboles" colgantes de el mismo conformado por los nodos que no pertenecen al camino.- Inicialmente M y P pertenecen al camino. Para todo vertice no perteneciente al camino visitarlo implica "salirse del camino" y no se puede volver a entrar. Tanto M como P sólo pueden visitar un único de los subárboles mencionados.
- La respuesta óptima de salirse del camino desde un vértice v es fácilmente calculable con un DFS. El problema quedó reducido a un camino y un vértice que se desprende de cada nodo del camino:
M - o - o - o - o - o - o - P
| | | | | | | | |
o o o o o o o o
Si bien creo que hay una solución que yo categorizaría de greedy para este problema (se basa en de observaciones matemáticas) esta es la solución con DP que hice, lo bueno es que es muy simple entender que funciona.
Parte II:
- En lo sucesivo c[i] es el valor de cada vértice del camino, ca[i] del que se desprende de él con i=0..len-1. Donde len es la cantida de nodos del camino M-P, el nodo 0 representa a M y len-1 a P. Además consideramos len impar (si no és se puede agregar un nodo con c y ca igual a 0) y mid será la posición del vértice del medio.- Es fácil calcular con programación dinámica (en el código pueden ver las fórmulas)
- sumMid[i]: el acumulado de c[i] de i hasta el mid.
- toMid[i]: estando en el nodo i la máxima cantidad de puntos podemos hacer yendo a lo sumo hasta mid.
- fromMid[i]: estando en el nodo mid la máxima cantidad de puntos podemos hacer yendo para el lado donde se encuentra i, y llegando a lo sumo hasta un nodo antes de i.
- Ahora resolveremos el problema con programación dinámica, siendo f(i,j) la cantidad de puntos si ambas juegan óptimo arrancando M en la posición i del camino y P en la j. Nosotros queremos calcular f(0,len-1).
Caso base:
f(mid-1,mid+1) = max ( ca[mid-1] - max(ca[mid+1],ca[mid]+c[mid]) , ca[mid]+c[mid] - ca[mid+1] )
Como M juega primero puede elegir salirse del camino (primera opción) o ir al medio. P juega el máximo posible a consecuencia de ello.
Paso inductivo: (Acá i y j están a distancia mayor que dos)
(A) i puede elegir irse del camino y ganar ca[i], con lo cual j puede seguir por el camino hasta a lo sumo un vértice antes de dicho nodo. Así la óptima es en este caso: ca[i] - max( sumMid[j] + fromMid[i] , toMid[j] )
(B) i puede elegir seguir en el camino, sumando c[i+1]. Luego j puede:
(B.1) seguir en el camino sumando c[j-1]. A lo cual el juego sigue en f(i-1,j-1). Teniéndose el valor óptimo para j de esta opción (dado que i ya eligió seguir en el camino) resulta: c[j-1] - f(i+1,j-1)
(B.2) abandonar el camino en j, teniéndose una fórmula análoga al apartado (A) (pero ahora es j el que abandona el camino y ya se ha avanzado M hasta i+1): ca[j] - max( sumMid[i+1] + fromMid[j] , toMid[i+1] )
Así la fórmula para el apartado (B) es: c[i+1] - max( c[j-1] - f(i+1,j-1) , ca[j] - max( sumMid[i+1] + fromMid[j] , toMid[i+1] ) ) (j elije la mejor opción de ambas).
Quedando el max entre las fórmulas de (A) y (B).
- La dinámica f(i,j) se basa sólo en el estado anterior f(i-1,j-1). Sólo se visitan O(N) estados. Podemos tirar un parámetro y recuperarlo del otro y la complejidad total será O(N).
Problema L
(ad hoc, greedy)
Existen muchas soluciones posibles, a continuación la que yo creo más corta y simple. El problema nos define un árbol, y luego nos da una cadena. Nuestra tarea es decir si esta cadena es un camino en el árbol o no. Notar que en este árbol el padre es siempre mayor a sus hijos, por lo que todo camino válido va a estar dividido en dos partes: una ascendente y otra descendente. El máximo M de la cadena nos dara el punto de separación.Para los elementos que estén en la parte ascendente tenemos que chequear que su anterior es el hijo. Para los elementos que estén en la parte descendente tenemos que chequear que su siguiente es el hijo. Para chequear si a es hijo de b podemos utilizar directamente la definición dada en el enunciado: b>2 and (a+1==b or a+2==b).
Por último debemos asegurarnos que la parte ascendente y la descendente sean disjuntas. Para esto basta con solo verificar que el anterior y siguiente de M son distintos.
12 comentarios: