Orden de eliminación en el problema de Josefo en O(N logN)

Dados N niños parados en un círculo esperando ser ejecutados, y un número K , que indica que K-1 niños son saltados en el sentido de las agujas del reloj, y el K ^-ésimo niño es asesinado en el círculo, y luego la ejecución de (K+1 ) ^el niño comienza,

Ejemplos:

Entrada: N = 5, K = 2
Salida: 3 1 5 2 4
Explicación: 
Inicialmente, el arreglo es {1, 2, 3, 4, 5} y las operaciones realizadas son:

1. Contando desde 1, el K ^-ésimo hijo es 3. Así que el 3er hijo es asesinado. Después de eso, los hijos que quedan por ejecutar son {1, 2, 4, 5}, y luego comienza la ejecución del hijo 4.
2. Contando desde 4, el K ^-ésimo hijo es 1. Así que el primer hijo muere. Después de eso, los hijos que quedan por ejecutar son {2, 4, 5}, y luego comienza la ejecución del hijo 2.
3. Contando desde 2, el K ^-ésimo hijo es 5. Entonces, el quinto hijo es asesinado. Después de eso, los hijos que quedan por ejecutar son {2, 4}, y luego comienza la ejecución del hijo 2.
4. Contando desde 2, el K ^-ésimo hijo es 2. Así que el segundo hijo muere. Después de eso, el niño que queda por ejecutar es 2, y luego comienza la ejecución del niño 4.
5. Finalmente, el niño 4 es el único niño restante. Entonces el niño será asesinado.

Entrada: N = 7, K = 2
Salida: 3 6 2 7 5 1 4

Enfoque ingenuo: la idea más simple es usar un vector para almacenar la posición de los niños restantes. Luego itere mientras el tamaño del vector es mayor que 1 , y en cada iteración borre la posición deseada del vector .

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando un conjunto ordenado . Siga los pasos a continuación para resolver el problema:

• Inicialice un conjunto ordenado , digamos V , e inserte los elementos en el rango [1, N ] en V.
• Inicialice una variable, digamos pos como 0 , para almacenar el índice del elemento eliminado.
• Iterar hasta que el tamaño del conjunto , V sea mayor que 1 , y realizar los siguientes pasos:
  • Almacene el tamaño del conjunto en una variable, digamos X .
  • Actualice el valor de pos a (pos + K) % X .
  • Imprime el elemento apuntado por pos en V y luego bórralo .
  • Actualice pos a pos%V.size().
• Finalmente, después de completar los pasos anteriores, imprima el último elemento almacenado al comienzo del conjunto V.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <iostream>
using namespace std;
  
// Header files, namespaces to use
// ordered set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set                              \
    tree<int, null_type, less<int>, rb_tree_tag, \
         tree_order_statistics_node_update>
  
// Function to find the child who
// will get killed in the ith step
void orderOfExecution(int N, int K)
{
  
    // Create an ordered set
    ordered_set V;
  
    // Push elements in the range
    // [1, N] in the set
    for (int i = 1; i <= N; ++i)
        V.insert(i);
  
    // Stores the position to be removed
    int pos = 0;
  
    // Iterate until the size of the set
    // is greater than 1
    while (V.size() > 1) {
  
        // Update the position
        pos = (pos + K) % (int)V.size();
  
        // Print the removed element
        cout << *(V.find_by_order(pos)) << ' ';
  
        // Erase it from the ordered set
        V.erase(*(V.find_by_order(pos)));
  
        // Update position
        pos %= (int)V.size();
    }
  
    // Print the first element of the set
    cout << *(V.find_by_order(0));
}
  
// Driver Code
int main()
{
    // Given input
    int N = 5, K = 2;
  
    // Function Call
    orderOfExecution(N, K);
  
    return 0;
}

3 1 5 2 4

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)