Cambie las casillas en movimientos mínimos

Question

Esta es una pregunta de una competencia de programación (que ha finalizado). Estaba luchando para resolver este problema, pero no pude encontrar un método saludable para hacerlo.

La pregunta es la siguiente:

IIIT Allahabad celebra su anual Fiesta Tecno-Cultural de la efervescencia MM12 del 1 al 5 de octubre. El chef acordó proveer dulces para esta temporada festiva. El chef ha preparado N cajas de dulces, numeradas del 1 al N (cada número se produce exactamente una vez). El chef es muy particular acerca de la disposición de las cajas. Él quiere que las cajas se arreglen en un orden particular, pero desafortunadamente el Chef está ocupado. Te ha pedido que arregles las cajas para él. Dado el orden actual de las casillas, debe reorganizar las casillas en el orden especificado. Sin embargo, hay una restricción. Solo puede cambiar dos cuadros adyacentes para lograr el pedido requerido. Salida, el número mínimo de tales permutas adyacentes requeridas.

entrada

primera línea de entrada contiene un único entero T, el número de casos de prueba. Cada caso de prueba contiene 3 líneas, la primera línea contiene un número entero N, número de casillas. Las siguientes 2 líneas contienen N números cada una, la primera fila es el orden dado de las casillas, mientras que la segunda fila es el orden requerido.

salida

Para cada caso de prueba, la salida de un número entero single 'K', número mínimo de permutas adyacentes requeridos. Restricciones:

1<=T<=10 
1<=N<=10^5 

Ejemplo

de entrada:

4 

3 
1 2 3 
3 1 2 

3 
1 2 3 
3 2 1 

5 
3 4 5 2 1 
4 1 5 2 3 

4 
1 2 3 4 
2 3 4 1 

Salida:

2 
3 
6 
3 

estaba casi ni idea acerca de esta cuestión. ¿Alguien puede explicar la lógica detrás de la pregunta?

Answer 1

El problema es un problema de programación competitivo bastante "clásico", que es contar las inversiones en una matriz. La inversión se define como un par (i, j) donde i < j y A [i]> A [j].

La versión más general, que contiene una matriz de números arbitrarios y se le pide que cuente el número de inversiones, tiene un O(n log n) solution by modifying merge sort algorithm.

Una versión más restringida ^, en la que hay un límite superior razonable en la valor máximo en la matriz (en cuenta que esta no es la longitud de la matriz), puede ser resuelto en O (log n m), donde m es el valor máximo en la matriz. El punto principal aquí es que la cantidad de código que tiene que escribir es mucho menor que el método de fusión.

El problema en la pregunta es sobre contar el número de swaps para ordenar la matriz a cierto orden, que se puede reconstruir contando el número de swaps para ordenar la matriz en orden ascendente, y se reduce a contar el número de inversiones. ¿Por qué número de inversiones? Porque solo puede resolver como máximo una inversión por intercambio de 2 elementos adyacentes.

Debe crear una matriz que describa la posición actual de las cajas con respecto a la configuración final. A continuación, el algoritmo puede empezar:

1. construir un Fenwick Tree (Binary indexado árbol) con una longitud de m (m = n para el problema en la pregunta).

   Utilizaremos Fenwick Tree para ayudarnos a contar el número de elementos que preceden a en la matriz que es más grande que el elemento actual. Mantendremos la frecuencia de los números que hemos encontrado hasta ahora y usaremos la consulta de suma de rango de Fenwick Tree para obtener el número de elementos menor que el elemento actual (y derivar el número de elementos más grande que el elemento actual).

2. Bucle a través de n elementos de la matriz:

   • Uso rango suma consulta para contar la cantidad de números que es menor que el número actual ha sido registrado.
   • Utilice la información anterior para averiguar cuántos números son más grandes que el número actual. Agregue esto al recuento de inversión. Tome nota para no incluir el elemento que se está considerando. (*)
   • Ajuste + 1 al Fenwick Tree al valor del elemento.

3. Cuenta de inversión que se acumula en el paso (*).

^La pregunta dice claramente que los elementos son únicos, por lo que el algoritmo anterior funcionará. Simplemente no estoy seguro de si la singularidad es una condición necesaria, o el algoritmo puede modificarse para acomodarse al caso en el que haya elementos repetitivos.

Answer 2

No puedo probar esto matemáticamente, pero en 4/4 de los casos de prueba se obtienen los intercambios mínimos al colocar las cajas en la posición correcta empezando por la izquierda (también se puede hacer con la derecha) y moviéndose a la derecha. Es decir.

3 4 5 2 1 //First get the 4 in the right place 
4 3 5 2 1 //Done. Now get the 1 in the right place 
4 3 5 1 2 
4 3 1 5 2 
4 1 3 5 2 //Done. Now the 5 
4 1 5 3 2 //Done. Now the 2 
4 1 5 2 3 //All done. 

Así que este algoritmo parece que le dará el mínimo para cualquier entrada dada. El peor de los casos, en general, parece una inversión, que requerirá N * (N-1)/2 intercambios (ver ejemplo 2).

Answer 3

Suponiendo que el orden deseado es el orden de los números, el problema se reduce a encontrar el número de inversiones en una matriz.

A pair (i,j) se dice que es una inversión si i < j y array[i] > array[j]. Esto se debe a que cada intercambio (óptimo) entre elementos adyacentes reduce el número de inversiones exactamente en 1. Puede encontrar el número de inversiones en O(n log n) mediante un algoritmo de dividir y conquistar que es muy similar al tipo de fusión. Aquí hay una buena explicación with C code.

EDITAR La prueba de que número de inversiones es igual al número óptimo de las permutas:

Vamos i ser cualquier posición en un array. El intercambio de array[i] y array[i+1] reduce el número de inversiones en un máximo de 1. Por lo tanto, el número de intercambios requeridos es al menos igual al número de inversiones. Por otro lado, si array no está ordenado, siempre podemos encontrar un par (i, i+1) tal que array[i] > array[i+1] (es decir, es una inversión), y reducir el número de inversiones en 1, al cambiar array[i] por array[i+1]. Por lo tanto, el número de inversiones es igual al número mínimo de intercambios.

Answer 4

Reduce la lista fuente a una permutación de (1,2, ..., N). (Aplicando el inverso del objetivo a la fuente)

Luego cuente el número de inversiones.

es decir

vector<int> source = ...; 
vector<int> target = ...; 

vector<int> inv(N) 

for (int i = 0; i < N; i++) 
    inv[target[i]] = i; 

vector<int> perm(N); 

for (int i = 0; i < N; i++) 
    perm[i] = source[inv[i]]; 

Luego cuente inversiones en Perm utilizando el algoritmo estándar.

Answer 5

El problema puede ser considerado como un problema de recuento de inversión de la siguiente manera:

Como se dan es decir, en el orden en que se supone que debemos ordenar las prioridades de los números.

Considerar las prioridades y reemplazarlo con los números

por ejemplo:

3 4 5 2 1 
4 1 5 2 3 

En el caso de ensayo anterior se puede observar que 4 se asigna prioridad 1, 1 se asigna prioridad 2, se asignará 5 prioridad 3 y así sucesivamente. ¿Por qué no sustituir el número en la lista original con estas prioridades

es decir, la transformación de la lista original

(3 4 5 2 1) to (5 1 3 4 2) 

(sólo la sustitución del número de sus prioridades respectivas como se mencionó anteriormente)

Ahora nuestra lista tiene transformado a

5 1 3 4 2 

y se supone que debemos ordenarlo en orden ascendente.

Ahora solo se permiten intercambios adyacentes, es decir, algo relacionado con el tipo de burbuja.

recuento de swaps necesarios para sortear burbujas, que es igual a la suma del recuento de elementos en el lado derecho de cada elemento que es más pequeño que el elemento actual.

para por ejemplo: En la lista

5 1 3 4 2 

5 tiene 4 elementos más pequeños que 5 en su lado derecho.

1 tiene 0 elementos más pequeños que 1 en su lado derecho.

3 tiene 1 elemento más pequeño que 3 en su lado derecho.

4 tiene 1 elementos más pequeños que 1 en su lado derecho.

2 tiene 0 elementos más pequeños que 2 en el lado derecho.

Ahora la respuesta final es (4 + 0 + 1 + 1 + 0) = 6.

Ahora el procedimiento anterior se puede calcular utilizando el recuento de inversión que se trata aquí http://www.geeksforgeeks.org/archives/3968.

NOTA: Las respuestas que obtuve fueron de gran utilidad, simplemente describiendo todo en detalle. Gracias