Comptage des inversions dans les fourchettes

j'ai participé à un concours de programmation dans lequel je n'ai pas pu résoudre un problème, le problème était:

étant donné un tableau A de n entiers, je dois compter le nombre d'inversions dans des intervalles donnés. Un entier M est fourni qui indique le nombre de plages, puis les lignes m suivent, dans chaque ligne deux entiers li et ri sont donnés.

nous devons compter les inversions dans la plage spécifiée seulement, c.-à-d. de li à ri inclusivement(indexation basée sur 0).

deux éléments A [i] et un [j] ajoute à l'inversion si A[i]>A[j] et i<j.

par exemple: A=[3 2 1 4]

Les inversions sont:

(2, 1), (3, 1), (3, 2) i.e. total number of inversions are 3.

Entrée:

3 2 1 4    //Array A 
3         // m - no. of ranges
1 2      // range
2 3
0 3

Sortie:

1
0
3

Contraintes:

n<=2*10^4
m<=2*10^4
A[i]<=10^9

je connais des méthodes pour calculer le nombre d'inversions dans O (nlogn) (comme BIT ou merge sort) sur l'ensemble du tableau et si je l'applique ici à chaque gamme la complexité serait O (mnlogn), c'est sûrement pas acceptable car la limite de temps est d'une seconde.

10
demandé sur Akashdeep Saluja 2014-02-13 23:11:03

4 réponses

voici un algorithme de temps O ((n + m) sqrt n log n). Ce n'est probablement pas assez bon pour passer, mais quelque chose ne semble pas tout à fait juste ici -- les trucs habituels du concours de programmation ne fonctionnent pas. (O ((n + m) sqrt n) pourrait être réalisable avec plus de soin.)

divisez le tableau d'entrée en sous-ensembles sqrt n de longueur sqrt n, appelé blocs. En utilisant un algorithme incrémentiel pour compter les inversions, pour chaque paire constituée d'un bloc et d'un préfixe du tableau, calculer le nombre d'inversions où le premier élément provient du premier et le second de ce dernier. (O (N sqrt n log n)) Faire la même chose pour les paires de préfixe-bloc.

pour chaque gamme d'entrées, décomposez - la en l'union de quelques blocs (éléments bloqués) et de moins de 2 éléments carrés (éléments non bloqués). En utilisant les résultats prédéfinis et inclusion-exclusion, trouvez le nombre d'inversions dans la gamme où au moins un élément est bloqué. (O(sqrt n)) Calculer et ajouter à cette quantité le nombre d'inversions dans la gamme impliquant deux débloqué éléments. (O (sqrt n log n))

3
répondu David Eisenstat 2014-02-14 02:24:35

O ((n + m) * sqrt (n) * log(n)) fuseau, O(n + m) l'espace de l'algorithme hors-ligne des requêtes (toutes les requêtes les plages doivent être connus à l'avance):

  1. divisez le tableau A en parties à peu près égales de sqrt(n).
  2. pour chaque partie du tableau faire les étapes 3...7.
  3. initialiser 3 pointeurs (Pbegin,Pmid,Pend) de sorte qu'ils pointent tous vers la fin de la partie courante du tableau (ou encore mieux vers le début le plus à droite de la plage appartenant à cette partie).
  4. Avance Pend; mise à jour de la commande-les statistiques de l'arbre qui détermine le nombre d'inversions entre Pmid et Pend; lorsque Pend coïncide avec la fin d'une certaine gamme qui a commencé dans la partie courante du tableau, faire les étapes 5...7.
  5. Déplacer Pbegin vers l'arrière jusqu'à ce qu'il coïncide avec le début de la plage trouvé à l'étape 4. Accumuler le nombre d'éléments dans l'ordre-arbre statistique moins que les valeurs indiquées par Pbegin (mais ne mettez pas à jour le arbre.)
  6. trouver le nombre d'inversions entre Pbegin et Pmid (en utilisant soit merge sort, soit separate order-statistics tree).
  7. additionnez le nombre d'inversions trouvées aux étapes 4, 5, 6. C'est le nombre d'inversions de la gamme actuelle.

BIT / Fenwick tree peut être utilisé ici comme implémentation efficace de l'arbre des statistiques des commandes. Dans ce cas, un pré-traitement est nécessaire: remplacez les valeurs du tableau par leurs index dans la copie triée du tableau à compresser la gamme de valeur.

O ((n + m) * sqrt (n)) fuseau, O(n * sqrt(n)) de l'espace de l'algorithme avec les demandes. Comme le laisse entendre David Eisenstat.

Pré-traitement:

  1. remplacez les valeurs du tableau par leurs index dans la copie triée du tableau pour compresser la plage de valeurs.
  2. divisez le tableau A en parties à peu près égales de sqrt(n).
  3. Pour chaque partie B du tableau do steps 4...8.
  4. Zéro-initialiser bitset de taille "n". Bits À Bascule correspondant aux valeurs de la partie "B". Pour ce bitset calculer le tableau des sommes des préfixes P et le tableau de suffixe sommes S.
  5. Pour chaque partie C partie précédente B faire l'étape 6.
  6. à partir de la dernière valeur v partie C et en allant vers l'arrière, additionnez toutes les valeurs P[v] et écrire sqrt(n) résultats pour la recherche de la table E. La complexité de cette étape est O(n * sqrt (n)).
  7. Pour chaque partie D partie suivante B l'étape 8.
  8. à partir de la première valeur v partie D et aller de l'avant, additionnez toutes les valeurs S[v] et écrire sqrt(n) résultats pour la recherche de la table F. La complexité de cette étape est O(N * sqrt(n)).
  9. utiliser l'algorithme incremental (Fenwick tree) pour compter le nombre d'inversions dans tous les suffixes de blocs (tous les sous-tableaux commençant à la limite du bloc avec une longueur ne dépassant pas sqrt(n)). Ecrire les résultats dans le tableau de recherche G. La complexité de cette étape est O(N * log n).
  10. utilisez l'algorithme incrémentiel pour compter le nombre d'inversions dans tous les préfixes de bloc. Ecrire les résultats dans le tableau de recherche H. La complexité de cette étape est O(N * log n).
  11. Utiliser E ou F et G ou H pour calculer le nombre d'inversions dans les blocs consécutifs (avec n'importe quelle paire de blocs pour les positions de départ et de fin). Ecrire les résultats à table de recherche R. La complexité de cette étape est O(n).

Après prétraitement nous avons plusieurs LUTs contenant le nombre d'inversions dans les préfixes de bloc / suffixes (G,H O(n) de l'espace), le nombre d'inversions entre blocs complets et de bloquer les préfixes/suffixes (E,F O(n * sqrt(n)) de l'espace), et le nombre d'inversions dans les blocs consécutifs (R, O (n) espace). (Nous pourrions éventuellement fusionner E et FR, ce qui augmente durée de pré-traitement, mais permet à O(1) temps pour la requête première étape).

Requête:

  1. Utiliser R pour obtenir le nombre d'inversions dans consécutives blocs complets, utilisez E et F pour ajouter un nombre d'inversions entre préfixe/suffixe et chacun de ces blocs complets, utilisez G et H pour ajouter le nombre d'inversions dans le préfixe et dans le suffixe.
  2. pour obtenir le nombre d'inversions entre le préfixe et le suffixe, trier les deux avec le tri radix (sqrt(n) 2 passes de comptage, et 2 passes pour distribuer les valeurs), et les fusionner.
  3. ajouter des valeurs à partir des étapes 1 et 2 pour obtenir le nombre d'inversions pour la plage de requête.
2
répondu Evgeny Kluev 2014-02-16 13:37:03

3ème portée: index 0 - 3 contient les 1er et 2ème de la gamme.

si vous savez combien d'inversions ont été contenues dans les gammes précédentes vous les sautez. Ainsi, dans la troisième plage, vous pouvez sauter en comparant 1 à 2 et sauter en comparant 2 à 3.

ainsi, au cours de la troisième gamme, vous ne comparez,

 0 -> 1
 0 -> 2
 0 -> 3
 1 -> 3

ce qui fait le meilleur scénario O(nlogn) et le pire scénario O(mnlogn).

1
répondu Mason T. 2014-02-13 20:01:05

Voici une élaboration d'une réponse précédente, également avec un écart potentiel rempli. Tout d'abord, vous calculez et stockez le nombre d'inversions pour tous les préfixes de votre tableau, dans le temps O(N log n), en ajoutant un élément à la fois de droite à gauche et en faisant la recherche d'arbre de recherche binaire pour trouver l'élément dans l'arbre de tous les éléments précédents pour déterminer le nombre supplémentaire d'inversions ajoutées, puis insérer l'élément dans l'arbre binaire (et maintenir l'arbre comme une recherche binaire auto-équilibrante arbre.) Puis vous calculez et stockez de la même manière le nombre d'inversions dans tous les suffixes. Ensuite, si vous voulez compter le nombre d'inversions dans une plage [L,R], vous ajoutez les inversions pour le préfixe commençant à L aux inversions dans le suffixe se terminant à R, et soustrayez le nombre total d'inversions pour l'ensemble du tableau. Cela vous donne presque la réponse mais pas tout à fait,parce qu'il vous donne la réponse Moins Le nombre d'inversions entre les gammes [1,L-1] et [R+1, n]. Donc, vous devez être en mesure de calculez le nombre d'inversions entre un préfixe arbitraire et une paire de suffixe dans votre tableau. Pour cela, vous calculez le nombre d'inversions entre les préfixes arbitraires et les suffixes spécifiques qui commencent avec un multiple de sqrt(n). Vous pouvez le faire en O(N^(3/2) log N) temps en triant chaque suffixe et puis, pour chaque suffixe, en ajoutant un élément au préfixe de gauche à droite, en faisant une recherche binaire dans le suffixe pour déterminer combien ajouter au nombre d'inversions. De même, vous calculez et store le nombre d'inversions entre chaque préfixe qui se termine par un multiple de sqrt(n) et chaque élément à droite du préfixe en O(n^(3/2) log n) fois.

puis, pour une plage donnée, vous prenez le préfixe et le suffixe et arrondissez le suffixe pour finir dans le plus proche multiple de sqrt(n) plus haut, et regardez le nombre d'inversions, dans le temps O(1). Ensuite, vous prenez les éléments restants dans le suffixe, et de regarder le nombre d'inversions dans le préfixe, qui se termine au plus proche multiple de sqrt(n) inférieur, en O(sqrt(n)) de temps. Ensuite, vous prenez les éléments restants dans le suffixe et les éléments restants dans le préfixe (non inclus dans le sqrt(n) endpoints), et brute-force calcule le nombre d'inversions entre eux dans O(sqrt(n) log n) time. Le temps total de calcul est O (sqrt (n) log n) Par plage, ce qui donne un temps d'exécution total de O ((m + n) sqrt (n) log n), ce qui devrait respecter le délai de 1 seconde.

1
répondu user2566092 2014-02-14 22:01:27