Duda problema solitario


#1

Hola estuve viendo este problema y lo resolvi rápidamente, el problema es que cuando lo probe en el juez note que me excedia de tiempo. La complejidad que yo entiendo en la manera en la que yo lo resolvi es O(N.K). Entonces decidi ver las soluciones y vi la que hizo Agustin Gutierrez y la verdad es que no entiendo la logica que sigue.
Este es mi código:

int solitario(std::vector<int> c, long long N, int K)
{
    std::deque<int> gameCards;
    int j = 0;
    for(int i = 0; i < N; ++i) {
        gameCards.push_back(c[j < c.size()? j : j = 0]);
        j++;
    }

    while(gameCards.size() > 1) {
        gameCards.pop_back();
        for(int i = 0; i < K; ++i) {
            int v = gameCards.back();
            gameCards.pop_back();
            gameCards.push_front(v);
        }
    }


    return gameCards[0];
}

Y este es el código de Agustin:

// Mata las cartas 0, K, 2K, 3K, ...
long long f(long long N, int K)
{
    assert(1 <= N);
    if (N == 1) return 0;
    if (K == 1) return N-1;
    long long restantes = N - 1 - (N-1) / K;
    long long newIndex = f(restantes, K);
    long long restoFinal = (N-1) % K;
    long long siguienteMuerto = K - restoFinal;
    long long indice = (siguienteMuerto + newIndex - 1 + restantes) % restantes;
    // Indice es entre los que quedan vivos luego de borrar los multiplos de K: hay que ajustar eso
    indice += 1 + indice / (K-1);
    assert(0 < indice && indice < N);
    return indice;
}

int solitario(vector<int> c, long long N, int K)
{
    const int M = int(c.size());
    assert(1 <= M);
    assert(M <= 100000);
    assert(0 <= K);
    assert(K <= 100000);
    assert(1 <= N);
    assert(N <= 1000000000000000000LL);
    long long indiceDesdeArriba = f(N, K+1);
    long long indiceDesdeAbajo = N - 1 - indiceDesdeArriba;
    return c[indiceDesdeAbajo % M];
}

Agradecería si alguno puede explicarme ese código.


#2

Hola. Dejo un par de consideraciones para una solución eficiente al problema.

Idea general para resolver el problema

La idea para una solución eficiente está en no simular el proceso carta por carta. Para hacer eso, se va llevando la cuenta de qué índice de carta es el que sobrevive, resolviendo el problema de manera recursiva. Al obtener la solución de un subproblema, requiere cierta manipulación de índices obtener la solución al problema original.

Comentario para entender su solución

En su solución tomó los índices de 0 a N-1 contando desde el tope de la pila hasta el final. Eso parece confundir en un principio (por estar al revés que lo que sugiere el enunciado), pero hace a todas las cuentas más fáciles. Te lo digo porque yo lo resolví con los índices como en el enunciado y no queda muy bello.

Esquema/Dibujo de solución al problema (AVISO: Es bastante quemador)

Te dejo un dibujito explicativo, donde espero que inspire a una solución eficiente del problema. Como yo lo resolví indexando de abajo para arriba, todas las cuentas difieren de las de Agustín.

Se puede ver que se descartan:

\left \lfloor \frac{n}{k+1} \right \rfloor

cartas en cada paso con N > K, y 1 carta en cada paso con N <= K.

La mayor dificultad (y es la parte donde hay que tener más cuidado) es en la traducción de índices que hay que hacer para obtener la solución al problema original en función de la solución al subproblema. Los nombres de las cosas se corresponden a mi último envío en el juez, si querés más detalle podés mirar ahí.


#3

Correcto, tu implementación tiene un complejidad temporal de \mathcal{O}(NK) porque al simular el proceso, por cada carta descartada (y hay N-1 de estas) hacés K+1 operaciones.

Aprovecho para hacer un par de comentarios. Algo que también hay que tener en cuenta es que tu implementación utiliza \mathcal{O}(N) memoria, pues al comenzar se agregan N enteros a \texttt{gameCards}.

Las cotas del problema son:

\begin{matrix} 1 \leq M \leq &100.000 & = 10^5 \\ 0 \leq K \leq &100.000 & = 10^5 \\ 1\leq N \leq &1.000.000.000.000.000.000 & = 10^{18} \end{matrix}

Por lo tanto no hay chance de que una solución obtenga 100 puntos y almacene el mazo de cartas en memoria (hay un límite de memoria en los problemas, que está arriba a la derecha en el juez al lado del límite de tiempo), o que simule el proceso carta por carta.

Por eso en competencia siempre es importante leer las subtareas que existen además de las cotas. En este caso el enunciado nos dice que podemos obtener 20 puntos correspondientes a casos con N \leq 100.000, K \leq 100, que son los que debería pasar tu solución.

En general, las subtareas nos pueden cambiar totalmente el problema. A veces una restricción extra simplifica mucho el problema, e incluso algunas subtareas pueden ser conducentes a una solución de 100 puntos.


#4

¡Hola!

Para 100 puntos se puede implementar la solución eficiente O(K \lg N) explicada en wikipedia.

Las ideas principales de esa solución las comentó ya Guty.