È ora disponibile sfere il quinto episodio della rubrica TAI .
Anche per questo esercizio, tra circa due settimane verrà presentato un editorial, nel frattempo potete cercare una soluzione
Un ringraziamento a @tpoppo per la sua collaborazione nello sviluppo di questo esercizio.
Saremmo anche curiosi di conoscere i vostri pareri sulla rubrica sino ad ora: se trovate gli esercizi interessanti, troppo facili o troppo difficili oppure se vorreste esercizi riguardo una categoria particolare.
Sarebbe quindi gradita un’opinione in risposta a questo post.
Ovviamente devo ancora risolvere l’ultimo esercizio, comunque per ora ho trovato gli esercizi interessanti, alcuni più semplici e altri più difficili. Per quanto riguardo la tipologia, potrebbero essere interessanti dei problemi sui grafi visto che compaiono spesso alle gare nazionali e territoriali.
Gli esercizi sono carini e interessanti , il più diffile secondo me era monete per via della dp. Sarebbe bello se metteste la difficoltà sul pdf perché le stelle del sito non sono affidabili visto che Calano in fretta
Il vero problema della difficoltà è che è abbastanza soggettiva, ed essendo solo in 2 a preparare gli esercizi non avremmo nemmeno un vasto insieme di opinioni per farcene un’idea troppo precisa. Comunque a mio giudizio sfere è, al momento, l’esercizio più impegnativo.
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.
L’idea fondamentale è quella di trovare un modo per confrontare velocemente due insiemi (usando una tecnica simile alle rolling hash). Per ottenere un’operazione di questo tipo ci sono moltissimi modi (che si basano su condizioni necessarie che l’insieme deve avere), uno di questi metodi è quello di associare ad ogni numero da 1 a N un valore casuale tra 0 e 2^{64} e definendo l’identificativo dell’insieme come lo xor dei valori all’interno dell’insieme:
b_i = rand() con i = 1, 2, ..., N f(a_l, a_{l+1}, ..., a_{r}) = b_{a_l} \oplus b_{a_{l+1}} \oplus ... \oplus b_{a_r}
Tramite l’utilizza delle somme prefisse è possibile calcolare l’identificativo degli insiemi che partono da 1 e terminano su ogni altro valore, inoltre usando un fenwick tree (o un segment tree) è possibile calcolare f(a_l, a_{l+1}, ..., a_{r}) e modificare un certo valore a_i velocemente.
Provando a fare una semplice analisi e assumendo che la funzione f abbia la stessa probabilità di restuire ogni valore, abbiamo che la probabilità che l’algoritmo sbagli sia pari a 1 - (1 - \frac{1}{2^{64}})^{100000} e dato che questo valore è molto vicino a 0, è molto difficile che l’algoritmo fallisca.
Essendo la probabilità di errore molto bassa in realtà non è fondamentale che le immagini di f siano perfettamente distribuite, per questa ragione molte soluzioni riescono a totalizzare 100 pt (ad esempio la somma dei quadrati o dei cubi) pur non avendo una distribuzione perfetta delle immagini.
La complessità finale risulta essere O((N + Q)\log{N}).
