# Aiutino per Vasi **URL:** \ **Category:** Aiuto\ **Created:** [29 Aprile 2014, 10:04am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800 "2014-04-29T10:04:58Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\ **Post date:** [29 Aprile 2014, 10:04am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/1 "2014-04-29T10:04:58Z")
Credevo bastasse usare semplicemente le list del C++ e invece va in timeout. Ho pure utilizzato una variabile che tenesse conto dell’ultima posizione puntata dall’iterator così da accorciare i tempi della funzione advance() passandogli come parametro di avanzamento un “delta pos” eppure va ancora in timeout! Qualcuno mi dà un aiutino o un consiglio per risolverlo? :3 ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [29 Aprile 2014, 2:02pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/2 "2014-04-29T14:02:47Z")
Che complessità hai attualmente in ricerca ed update? Prova a ragionare su una possibile soluzione che abbia tempo di ricerca e di update uguali. Indizio: O(√n). ---
**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\ **Post date:** [29 Aprile 2014, 7:13pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/3 "2014-04-29T19:13:55Z")
Segment tree? ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [30 Aprile 2014, 2:44pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/4 "2014-04-30T14:44:42Z")
Mmm… in tal caso sarebbe facilmente generalizzabile e avrei detto O(log n). Parti dalla soluzione banale O(n) update e O(1) ricerca, ovvero tieni l’array e ogni volta che lo modifichi sposti tutti gli elementi da spostare. Da lì, cerca un modo di ridurre la complessità di update a discapito della ricerca. ---
**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\ **Post date:** [3 Agosto 2014, 11:34pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/5 "2014-08-03T23:34:38Z")
Qualche aiutino in più? ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [4 Agosto 2014, 2:27pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/6 "2014-08-04T14:27:43Z")
Ok, abbiamo detto che per adesso mantieni un array _S_ di lunghezza _N_ con i valori su cui devi fare le operazioni. L’idea è di usare (al posto di _S_) una sequenza di _M_ array più piccoli _S0, S1, …, SM_ non necessariamente della stessa lunghezza che, quando concatenati, formano l’array iniziale _S_. Rimane da capire: come scegliere _M_, come fare le operazioni con questa nuova struttura. ---
**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\ **Post date:** [4 Agosto 2014, 2:35pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/7 "2014-08-04T14:35:08Z")
Dato che O(sqrt(N)), direi che l’array N va diviso in sqrt(N) parti, lunghe ciascuna sqrt(N). In pratica si utilizza la sqrt-decomposition. Ora resta solo da capire come effettuare le operazioni 😕 ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [4 Agosto 2014, 2:43pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/8 "2014-08-04T14:43:48Z")
Parti dall’operazione “c”. Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell’array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)). ---
**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\ **Post date:** [4 Agosto 2014, 3:36pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/9 "2014-08-04T15:36:42Z")
Sono riuscito, grazie mille per l’aiuto 😃 ---
**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\ **Post date:** [8 Agosto 2014, 6:40pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/10 "2014-08-08T18:40:17Z")
L’approccio per vasi2 è lo stesso? Anche se penso che sia improbabile, io lo chiedo lo stesso 😃 ---
**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\ **Post date:** [8 Agosto 2014, 7:18pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/11 "2014-08-08T19:18:35Z")
Io mi ci sono messo appena 20 minuti fa a fare vasi1, però non ho ancora capito come fare l’update con la sqrt decomposition. ---
**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\ **Post date:** [8 Agosto 2014, 8:01pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/12 "2014-08-08T20:01:18Z")
C’è un container delle STL in particolare che ti può dare una (grossa) mano ---
**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\ **Post date:** [8 Agosto 2014, 9:59pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/13 "2014-08-08T21:59:28Z")
Immagino ti riferisca alle liste. Stavo finendo di implementarle che sono dovuto uscire di casa! ---
**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\ **Post date:** [9 Agosto 2014, 11:18am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/14 "2014-08-09T11:18:39Z")
> Parti dall'operazione "c". Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell'array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)). > > wil93 Ma se io divido l'array in _sqrt(N)_ array lunghi _sqrt(N)_ ognuno, dato che la richiesta del problema non è di trovare un valore in particolare ma di trovare l' **_i_** -esimo valore, Se io so che concatenando gli _sqrt(N)_ ottengo l'array, per ricercare l'elemento **_i_** non basta accedere alla _( **i** / sqrt(N))_ parte alla _( **i** % sqrt(N))_ posizione? Forse mi sono perso qualcosa nel ragionamento. ---
**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\ **Post date:** [9 Agosto 2014, 11:29am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/15 "2014-08-09T11:29:15Z")
> > Parti dall'operazione "c". Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell'array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)). > > > > wil93 > > Ma se io divido l'array in _sqrt(N)_ array lunghi _sqrt(N)_ ognuno, dato che la richiesta del problema non è di trovare un valore in particolare ma di trovare l' **_i_** -esimo valore, Se io so che concatenando gli _sqrt(N)_ ottengo l'array, per ricercare l'elemento **_i_** non basta accedere alla _( **i** / sqrt(N))_ parte alla _( **i** % sqrt(N))_ posizione? > > Forse mi sono perso qualcosa nel ragionamento. > > simone.pri Invece è corretto, perché non dovrebbe esserlo? ---
**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\ **Post date:** [9 Agosto 2014, 11:49am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/16 "2014-08-09T11:49:24Z")
> > > Parti dall'operazione "c". Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell'array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)). > > > > > > wil93 > > > > Ma se io divido l'array in _sqrt(N)_ array lunghi _sqrt(N)_ ognuno, dato che la richiesta del problema non è di trovare un valore in particolare ma di trovare l' **_i_** -esimo valore, Se io so che concatenando gli _sqrt(N)_ ottengo l'array, per ricercare l'elemento **_i_** non basta accedere alla _( **i** / sqrt(N))_ parte alla _( **i** % sqrt(N))_ posizione? > > > > Forse mi sono perso qualcosa nel ragionamento. > > > > simone.pri > > > > Invece è corretto, perché non dovrebbe esserlo? > > Lawliet Io l'ho risolto nella stessa maniera ma usando le deque, dato che la lettura è costante mentre nelle liste è lineare (confermate?) ---
**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\ **Post date:** [9 Agosto 2014, 12:06pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/17 "2014-08-09T12:06:12Z")
Vero, infatti anch’io mi sono reso conto che con le deque è più veloce. Soprattutto per le operazioni di push/pop\_back/front che sono in O(1). Solo che nonostante questo non riesco ad andare oltre come punteggio. Prende tutti gli input fino al penultimo del secondo subtask. EDIT: Come non detto, penso di averlo risolto. ---
**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\ **Post date:** [9 Agosto 2014, 1:02pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/18 "2014-08-09T13:02:51Z")
> > > Parti dall'operazione "c". Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell'array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)). > > > > > > wil93 > > > > Ma se io divido l'array in _sqrt(N)_ array lunghi _sqrt(N)_ ognuno, dato che la richiesta del problema non è di trovare un valore in particolare ma di trovare l' **_i_** -esimo valore, Se io so che concatenando gli _sqrt(N)_ ottengo l'array, per ricercare l'elemento **_i_** non basta accedere alla _( **i** / sqrt(N))_ parte alla _( **i** % sqrt(N))_ posizione? > > > > Forse mi sono perso qualcosa nel ragionamento. > > > > simone.pri > > > > Invece è corretto, perché non dovrebbe esserlo? > > Lawliet Allora perchè la ricerca dovrebbe avere complessità O(N/M) + O(M) ?? E comunque per quanto riguarda l'update, non capisco come si migliori da O(n) a O(sqrt(N)) Se io ho un Vettore diviso in parti comunque per fare un update devo spostare le altre parti, quindi la complessità è la stessa giusto? Se io uso una Lista oppure sqrt(N) liste che differenza cè? Con la lista posso rimuovere con .remove, poi effettuare un serch e inserire il valore rimosso. Avere più liste invece che una che miglioramento avrebbe? ---
**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\ **Post date:** [9 Agosto 2014, 1:14pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/19 "2014-08-09T13:14:54Z")
Sostanzialmente non dovresti usare remove e search ma le funzioni per aggiungere e togliere valori dalla fine è dll’inizio della lista (push\_back(), push\_front(), pop\_back(), pop\_front()) per tutte le liste “centrali” tra i due indici coinvolti nell’update. Per i segmenti che invece contengono questi due indici devi usare remove e insert. Il problema è che le liste sono lente, quindi ti conviene usare varie deque. La complessità migliora perché tu fai solo 2 operazioni per ogni segmento, diventando quindi O(2\*sqrt(N))=O(sqrt(N)). Non so se sono stato chiaro ---
**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\ **Post date:** [9 Agosto 2014, 1:35pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/20 "2014-08-09T13:35:14Z")
> Sostanzialmente non dovresti usare remove e search ma le funzioni per aggiungere e togliere valori dalla fine è dll'inizio della lista (push\_back(), push\_front(), pop\_back(), pop\_front()) per tutte le liste "centrali" tra i due indici coinvolti nell'update. Per i segmenti che invece contengono questi due indici devi usare remove e insert. Il problema è che le liste sono lente, quindi ti conviene usare varie deque. > La complessità migliora perché tu fai solo 2 operazioni per ogni segmento, diventando quindi O(2\*sqrt(N))=O(sqrt(N)). > > Non so se sono stato chiaro > > Lawliet Esatto, dato che pop/push\_back e pop/push\_front hanno coplessità costante (O(1)). Quindi ti fai un vettore di sqrt(N) deque, ognuna con sqrt(N) elementi (o meno, nel caso dell'ultima, dato che sqrt(N) non è sempre un intero). [Pagina seguente](https://forum.olinfo.it/t/aiutino-per-vasi/3800.md?page=2)