Editorial sfere
Con l’arrivo di hasta, nuovo esercizio della rubrica propongo un editoria di sfere.
Inizio dicendo che per la natura dell’esercizio alcune delle soluzioni trovate nelle 3 settimane non sono deterministiche, nello specifico: una permutazione dei primi X numeri naturali ha ovviamente varie proprietà che devono essere verificate, si può controllare che la somma corrisponda a \frac{X(X+1)}{2}, che il valore massimo è X il minimo è 1 ed altre proprietà meno banali.
Ora tra queste proprietà \texttt{necessarie}, per ottenere una soluzione deterministica bisogna trovarne un sottoinsieme che risulti essere \texttt{sufficiente} per capire se X è una permutazione.
Le soluzioni non deterministiche usano delle proprietà che non sono sufficienti a capire deterministicamente se X è una permutazione ma sono una buona approssimazione ed in particolare risultano essere corrette nelle istanze presenti nei testcases dell’esercizio.
Soluzione deterministica:
Come detto prima dato un segmento [l, r] dobbiamo trovare delle proprietà che sono \texttt{necessarie e sufficienti} ma che allo stesso tempo siano facili da verificare, le proprietà che ho deciso di controllare sono:
- max(sfere_l, sfere_{l+1}, ..., sfere_r)= r-l+1.
- Per ogni elemento del segmento il prossimo l’elemento con lo stesso valore deve avere un indice maggiore di r.
La prima proprietà verifica che il valore massimo sia corretto mentre la seconda verifica che non ci siano 2 occorrenze di uno stesso valore, queste 2 proprietà risultano sufficienti .
- Per verificare la proprietà 1 è sufficiente mantenere un segment tree sui valori delle sfere, ed avere point update per modificare i valori delle sfere e maximum range query per trovare max(sfere_l, sfere_{l+1}, ..., sfere_r).
- Per la seconda proprietà iniziamo calcolando un array succ[] nel quale per ogni indice i succ[i] contiene l’indice della prossima occorrenze di v[i], e mantenendo N set nei quali per ogni valore x il set numero x corrisponde a \{0 \le i \le n-1 | sfere_i=x\}.
Ora costruiamo un altro segment tree sempre con point update ma questa volta con minimum range query su succ[] infatti se il valore minimo tra i successivi nel segmento [l, r] è maggiore di r allora tutti gli elementi sono distinti.
La parte più rognosa è tenere aggiornato il secondo segment tree, per farlo bisogna usare i set in modo di aggiornare tutti i successivi che vengono cambiati con una chiamata di \texttt{modifica}.
La complessità è O(QlogN), infatti per ogni operazione a prescindere dal suo tipo la complessità rimane O(logN).
Invito inoltre @tpoppo, che ha collaborato alla preparazione, a spiegare anche la soluzione probabilistica che ha usato.