Ois_permutation tecnica di risoluzione

Provando a risolvere permutation (https://training.olinfo.it/#/task/ois_permutation/statement) l’unica soluzione che mi è venuta in mente è in O(N^2 \cdot \log(N) ), decisamente troppo elevata per il time limit.
Poi sono andato a sbirciare nella wiki di Chiodini e ho visto che usa un Fenwick tree per contare le inversioni, ma non ho capito bene come procede dopo.
Qualche hint sulla tecnica da utilizzare?

Prima di tutto, sai risolvere il problema se sai qual è la permutazione di arrivo?
(https://training.olinfo.it/#/task/paletta/statement)

Sì, la mia soluzione con complessità O( N^2 \cdot \log(N) ) funziona così: per ognuna delle N differenti permutazioni “di arrivo” verifica quante mosse sono richieste in O( N \cdot \log(N) ) . Poi prendo il minimo numero di mosse richieste.

Immagina di sapere in quante mosse puoi arrivare a 1,2,3,…,N. Riesci a trovare velocemente in quanti arrivi a 2,3,…,N,1? Cambia davvero così tanto?

1 Mi Piace

È vero, quando si passa alla permutazione successiva solo un elemento cambia di posto in modo “significativo”, quindi basta ricalcolare il numero di mosse per quel determinato elemento…
Grazie dell’hint, ora mi viene in O(N \cdot \log(N) )

1 Mi Piace