Hago este post para que discutamos ideas sobre “Ubicando fichas en la hilera”.
Hilera.pdf (68,7 KB)
Bueno, este problema me estuvo perturbado estos días
La idea que tengo es hacer una DP Bottom-Up en la que en cada dp[i][j] se almacene la máxima suma que existe ubicando una ficha en el i-ésimo número y con cantidad j de fichas especiales.
Las 2 primeras filas se rellenarian como casos bases y la 3 como subcaso (para evitar el bug de llamar a una posición negativa). De esta manera, cada posición se calcularia así:
Código
ll ans = -1;
ans = max(ans, dp[i - 2][e]); //Caso en el que se deja un número en medio para poder ubicar una comun
ans = max(ans, dp[i - 1][e + 1]); //Caso en el que se ubica una especial adyacente a otra ficha
ans = max(ans, dp[i - 2][e + 1]; //Caso en el que se deja un número en medio para ubicar una especial
ans = max(ans, dp[i - 3][e]); //Caso en el que se dejan dos números en medio para ubicar una comun
dp[i][j] = ans + numero[i];
Pensé que con esto salía pero falta el caso en el que se puede ubicar una común si antes se ubicó una especial. Para resolverlo pensaba agregarle una dimensión a la tabla de memoria para reconocer cuando un valor proviene de haber colocado una especial antes (ll dp[n][k + 2][2]; y no ll dp[n][k + 2]). Pero creo que esto ya ocupa demasiado espacio.
¿Esto entra? ¿Cómo soluciono este problema? ¿O me conviene pensarlo de otra forma? 
2 Me gusta
La idea principal es la que mencionás al principio.
Lo que decís al final no entiendo por qué debería hacerte falta.
Como en muchos casos, hay varias fórmulas de plantear la recursión. Según cómo lo hagas, te quedará un poco distinta la implementación. Paso a explicar en detalle la que entiendo es la más cercana a lo que pensaste. Llamo \texttt{A} al arreglo con los números que vienen en la hilera, y sigo tu notación para i,j. Entonces, si llamamos:
f(i,j) = `` \text{La respuesta en el prefijo } \texttt{A[0..i]} \text{ teniendo a disposición } j \text{ fichas especiales}
¿Qué posibilidades hay para completar la i-ésima posición? Básicamente 3:
- \color{red}\text{No pongo ninguna ficha} en la posición i.
- \color{cyan}\text{Pongo una ficha común} en la posición i.
- \color{lime}\text{Pongo una ficha especial} en la posición i.
Entonces f(i,j) = \max \{ {\color{red}f(i-1,j)}, { \color{cyan} f(i-2,j) + \texttt{A[i]} }, { \color{lime} f(i-1,j-1) + \texttt{A[i]}} \}
Luego, como vos decís. Si vas resolviendo los problemas incrementalmente en i, podés implementarlo Bottom-Up, resolviendo el problema para todo j antes de avanzar al siguiente i (porque siempre que querés calcular f(i,j) ya calculaste los valores de f previos que necesitás haciéndolo en este orden).
Con esta formulación, para contemplar el caso base, probablemente lo más sencillo es agregar agregar ceros al principio y notar que la respuesta es 0 para todo j en esos casos. Finalmente, buscamos f(\hat{n},k), donde \hat{n} es la última posición del arreglo luego de agregarle ceros al principio, y k la cantidad de fichas especiales a disposición.
Para puntaje completo, uno debe guardarse en qué caso se alcanzó el máximo para poder saber qué ficha utilizó en cada posición.
1 me gusta
Esto está mal.
Ahí entendí lo que decís al final. Totalmente, hay que tener en cuenta qué pasa cuando uno pone una ficha común y justo antes una especial (O sea, el problema está en disminuir en 2 la recursión en el caso de la ficha común).
Una forma de corregir esto, es lo que ponés acá
Eso no ocupa mucho espacio, o sea, solo el doble.
La gracia es que el tercer parámetro podés usarlo para saber si podés ubicar una ficha común en la posición actual o no. La recursión quedaría de la forma:
Entonces la recursión quedaría
f(i,j,\texttt{true}) = \max \{ {\color{red}f(i-1,j,\texttt{true})}, { \color{cyan} f(i-1,j,\texttt{false}) + \texttt{A[i]} }, { \color{lime} f(i-1,j-1,\texttt{true}) + \texttt{A[i]}} \}
f(i,j,\texttt{false}) = \max \{ {\color{red}f(i-1,j,\texttt{true})}, { \color{lime} f(i-1,j-1,\texttt{true}) + \texttt{A[i]}} \}
1 me gusta
Ah bien. Estaba testeando a mano lo que decias anteriormente y todavia no daba.
Claro, al ser el doble tampoco es tan crítico, tenés razón.
Y ahora viéndolo recursivamente, parece más fácil de implementar. En competencia lo había intentado recursivo, hasta llegué a pensarlo con la DP de 3 dimensiones pero el problema es que no supe como almacenar bien los datos en la tabla.
Ahora esta todo más claro 
Muchas gracias
1 me gusta
Otra opción es notar que primero analizamos 3 casos, según la situación del casillero i:
Si ahí no ponemos nada, es f(i-1, j).
Si ahí ponemos una ficha especial, es f(i-1,j-1) + A[i]
Ahora bien el tema ocurre cuando analizamos que pasa si ahí ponemos ficha común: No nos queda equivalente al problema con una casilla menos, porque en la última casilla (la i-1) vale poner especial, pero no vale poner común, que es algo “raro” que el problema original no tiene: dependiendo de lo que pongamos ahí, las restricciones que tenemos.
Una opción en este caso entonces es considerar ambos (sub)casos. Son solo dos, pues poner una ficha común en el i-1 no está permitido (estamos analizando qué pasa cuando ponemos ficha común en el i):
Si ponemos una ficha especial en i-1, ahora sí nos queda directamente f(i-2,j-1) + A[i] + A[i-1]
Y si no ponemos nada en i-1, también ya nos queda directamnete f(i-2, j) + A[i]
Así que nos quedan ahora 4 casos pero todo sigue funcionando, y tenemos una recursión correcta casi idéntica a la original:
f(i,j) = max\{f(i-1,j), f(i-1,j-1) + A[i], f(i-2,j) + A[i], f(i-2,j-1) + A[i] + A[i-1]\}
(Siempre considerando las opciones que no se vayan fuera de rango / agregando casos base).
Una observación adicional que se puede hacer para dejar solo 3 casos (pero no es necesaria) es que el último caso en definitiva domina al segundo, ya que no hay números negativos, siempre conviene una solución B que una solución A, si B contiene completamente las fichas de A. Y justamente el último caso (que corresponde a común en i y especial en i-1) es como si hubiéramos entrada en el segundo caso (el de especial en i) y a continuación mágicamente obtuviéramos el número i-1 “gratis”, sin gastar ficha especial ni nada. Así que (si manejamos bien los casos base, por ejemplo agregando un número “0” ficticio al comienzo para no tener problemas) podemos incluso sacar ese caso y dejar solamente:
f(i,j) = max\{f(i-1,j), f(i-2,j) + A[i], f(i-2,j-1) + A[i] + A[i-1]\}
Aunque de vuelta, esto no era importante, con la de arriba de 4 casos basta.
Esta solución usa la mitad de memoria y “aproximadamente la mitad de tiempo”, y es más simple (en mi opinión) que la otra. Pero las dos son válidas Más aún, conviene entender las dos porque el truquito del booleano (en general, de “agrandar el estado”) que usa la otra DP es muy muy común y en muchos problemas necesario.
2 Me gusta
Mi idea fue plantearlo como un DAG, hacer un BFS y calcular sobre una matriz las “distancias”, en donde siempre me quedaba con el mayor número.
Si estamos parados en i, j, significa que estamos en la posición j, habiendo usado i fichas especiales.
Creo que está bien pensado (por favor, corríjanme si me equivoco), pero lo implementé con bugs por falta de tiempo.
3 Me gusta
No sé si estoy logrando entender la idea del todo. ¿Podrías explicar el razonamiento en un ejemplo pequeño?
1 me gusta
Cuando hacemos un BFS usamos una queue y tenemos un vector en donde nos guardamos las distancias a cada nodo. Mi implementación usa queue y una matriz en donde guardo las distancias.
La idea de mi BFS era (sin tener lista de adyacencia) pensar que me podía mover de i a i+1 con una “arista” de costo 1, donde este 1 implicaba usar una ficha especial. También podía moverme de i a i+2, i+3, i+4, … n con una “arista” de costo 0, ya que no usaba ficha especial.
Haciendo este BFS me quedaba con lo mejor, en donde lo mejor era el máximo puntaje que podía obtener.
Entonces, ¿Cuál era la idea?
La idea era pensar las filas de la matriz como fichas usadas y pensar las columnas como el puntaje hasta la posición i del vector del input
Entonces arranco en el nivel 0 (usando 0 fichas especiales) y cada vez que uso una me muevo al nivel siguiente y sigo calculando sobre eso las distancias.
En el proceso me guardo los padres de cada celda, entonces es trivial hacer un backtracking y calcular el array “fichas”.
Espero que se haya entendido un poco mejor.
1 me gusta
Yo no entendí.
Cuando hablás de i, qué representa esa variable?
n es la cantidad de números de la entrada?
Por qué ponés “arista” entre comillas?
Más precisamente, cuál es el grafo exacto sobre el que hacés BFS? (Aunque sea implícito y no esté representado en memoria explícitamente).
Si las columnas son puntajes, no van hasta n sino que pueden ser mucho más grandes, así que se complica por el lado de la complejidad (eso suena parecido a la DP de subset sum con booleanos, que podría verse como BFS / DFS / alcanzabilidad en grafos, pero sin entender bien el grafo / la solución / la recursión no estoy seguro de si te referís a eso o no).
Ojo con la palabra “backtracking” que se confunde con la técnica de backtracking, si bien acá se entiende que te referís a reconstruir el camino desde el final hacia el comienzo.
2 Me gusta