Ciao a tutti,
sto cercando di risolvere paletta ma ottengo 69/100 a causa del timeout
non saprei proprio come migliorare l’algoritmo,
questo si basa sulla sostituizione dell’elemento i con quello alla posizione i+2 nel caso sia maggiore e di decrementare i di 3 per poi continuare il ciclo
codice:
https://pastebin.com/vJsBWqbE
Sapreste darmi una mano?
non vorrei utilizzare strutture dati che non conosco 
Prima di pensare ad ordinarlo, riesci a trovare una condizione necessaria e sufficiente affinché il vettore sia ordinabile?
Per questo punto ti consiglio di osservare una sequenza come questa: [1, 0, 2]
Al posto di ordinare effettivamente tramite “paletta-sort”, riesci a trovare un modo alternativo per sapere a priori quante mosse ci vorranno?
Immagina di essere alla fine, quindi con il vettore ordinato, e inizia a “disordinarlo”; noti qualcosa?
Oltre i consigli di Vash, guarda l’esercizio partition, risolverlo mi è stato molto utile per questo.
Hint: fenwick
In realtà si può fare anche senza Fenwick 
merge sort?
Scusate ma non so che sia il Fenwick 
In ogni caso, se l’array si può ordinare il risultato può essere la somma del numero di swap degli elementi alla posizione pari e quelli alla posizione dispari?
Scusate ragazzi, non avevo visto che i numeri vanno da 0 a N-1
Ora è molto più facile, grazie
Il caso generico di un array qualsiasi non è troppo diverso in quanto puoi rimappare ogni elemento in [0, N-1] mantenendone l’ordine relativo
Comunque sì, è la somma degli swap, ora devi trovare un modo furbo per contarli
oppure un segment tree
Giusto. Però se usi un segment quando puoi usare il fenwick sei un folle 
fenwick, segment tree, wtf?
altre cose che devo studiare per una medaglia alle oii?
Io l’anno scorso ho preso l’argento sapendo dijkstra e la dinamica 
… ma direi che mi è andata fin troppo bene.
Se punti ad una medaglia ti consiglio di studiarti almeno i segment tree (che a volte troverai indicati come range tree, 'cause reasons), e se riesci anche il fenwick, visto che si tratta veramente di poche righe.
Ti linko un paio di file da cui puoi iniziare:
https://digit.cms.di.unipi.it/resources/rangetree.pdf
https://digit.cms.di.unipi.it/resources/fenwick.pdf
Dario
thanks bruh 
ora me li studio