Hay una matriz con N entero (N <5x10 ^ 5) y hay dos jugadores (A y B) que están eliminando los elementos de esta matriz secuencialmente. A está tratando de hacer que el último número permanezca más grande y B está tratando de hacerlo más pequeño.

* Ambos jugadores pueden eliminar solo el primer elemento o el último elemento. * A comienza a eliminar primero.

Digamos; A = [3,100,4,50]

-A eliminará 50 porque si A elimina 3, entonces B puede eliminar 100, que no es lo que A quiere.


He resuelto el problema usando programación dinámica pero el problema es la memoria. Utilicé una matriz de enteros 2D para la memorización y cuando recibo una matriz con un tamaño de 10 ^ 5, consume toneladas de memoria (para este caso 10 ^ 5x10 ^ 5x2 = 2x10 ^ 10 bytes, que es 18.6 gigabytes), pero quiero para resolver este problema con 512 mb de memoria como máximo. Mi pregunta es "¿cuál sería la forma más eficiente en cuanto al espacio para resolver este problema?".

3
M.Soyturk 21 ene. 2018 a las 22:19

3 respuestas

La mejor respuesta

En realidad, no creo que necesites programación dinámica aquí. La respuesta siempre será el elemento en el medio, y en caso de que N sea par, la respuesta es el máximo entre los dos elementos del medio. Aquí está la prueba:

Suponga que usted es el jugador A y desea que el elemento restante sea mayor que el del medio. Si el elemento está en la mitad derecha de la matriz, seguramente comenzará a tomar elementos desde el inicio de la matriz (manteniendo el elemento que desee durante el mayor tiempo posible). Ahora piensa cómo reaccionará el jugador B , ¿por qué te ayudaría a lograr tu objetivo? Por supuesto, el jugador B comenzará a tomar elementos del final de la matriz para deshacerse del gran elemento que desea.

Lo mismo sucede si eres el jugador B y estás tratando de mantener un elemento que es más pequeño que el del medio, el jugador A comenzará a tomar elementos del otro lado para elimine el elemento pequeño que desea.

En caso de que los elementos grande y pequeño estén en el mismo lado de la matriz, ambos jugadores pueden calcular si pueden tener o no el elemento que desean. Si uno de ellos no puede obtener el elemento que desea, empujará al otro jugador a mantener el elemento central con seguridad quitando siempre el elemento del otro lado.

El único caso especial es si N es par, en este caso el paso final será realizado por el jugador A , y la matriz tendrá 2 elementos restantes (que son los dos elementos en el medio). En este caso, seguramente el jugador A eliminará el elemento más pequeño y conservará el más grande.

4
Said A. Sryheni 21 ene. 2018 a las 20:01

Esto me recuerda mucho a la poda alfa-beta (https: //en.wikipedia .org / wiki / Alpha% E2% 80% 93beta_pruning). La poda A / B es aplicable a situaciones en las que tienes un juego competitivo de dos jugadores y puedes asignar un puntaje a cada movimiento del juego, por ejemplo, ajedrez o damas, pero esto debería funcionar igual de bien.

El problema se reduce a una búsqueda en árbol sobre posibles estados y puntajes del juego, en este caso puntajes diferenciales entre los jugadores, para cada estado. La poda A / B permite que se reduzca el espacio de búsqueda, que se corten subárboles enteros, según el puntaje esperado para el jugador contrario . La idea es que los subárboles que conducen a un puntaje para el jugador contrario que sea más alto que su propio puntaje esperado no necesitan ser tomados en cuenta.

1
Matti Lyra 21 ene. 2018 a las 19:27

Suponga que calcula la mejor puntuación para todas las matrices de longitud k (k comenzará en 1 y aumentará gradualmente) y con ambas opciones de primer jugador.

Puede calcular la mejor puntuación para todas las matrices de longitud k + 1 solo a partir de las matrices de longitud k (considerando eliminar el primer o el último elemento y elegir el mejor).

Por lo tanto, puede hacer esto con la memoria O (N) manteniendo solo dos copias de esta matriz (k y k + 1) y descartando todas las longitudes más pequeñas.

En otras palabras, si almacena los resultados en una matriz 2d de tamaño [2] [N], puede almacenar el resultado para matrices de longitud k en la posición k% 2 (que será 0 o 1).

4
Peter de Rivaz 21 ene. 2018 a las 19:25