Aiutino per Vasi


#1

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

Struttura dati Vasi
#2

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).


#3

Segment tree?


#4

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.


#5

Qualche aiutino in più?


#6

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.

#7

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 :confused:


#8

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)).


#9

Sono riuscito, grazie mille per l’aiuto :smiley:


#10

L’approccio per vasi2 è lo stesso? Anche se penso che sia improbabile, io lo chiedo lo stesso :smiley:


#11

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.


#12

C’è un container delle STL in particolare che ti può dare una (grossa) mano


#13

Immagino ti riferisca alle liste. Stavo finendo di implementarle che sono dovuto uscire di casa!


#14
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.

#15
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?

#16
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?)

#17

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.

#18
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?


#19

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

#20
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).