Ciao, io ho svolto questo problema durante le ois ed ho totalizzato soltanto 70 punti (non ho utilizzato STL), oggi sto cercando di risolvere gli ultimi subtask che mi andavano fuori tempo limite, ma faccio sempre 70 punti anche usando una deque. Consigli su come fare??
La ricerca del minimo in una deque impiega comunque O(N), scorre semplicemente tutti gli elementi.
Inoltre devi cercare un modo migliore per simulare le rotazioni della ruota.
Comunque sul forum ci sono già altre discussioni a riguardo, magari leggerle ti può essere d’aiuto!
li avevo già visti ma nulla di esaustivo. secondo me l’unica cosa che va ottimizzata è la ricerca del minimo e del massimo per il resto penso sia decente
Purtroppo la stl non è magica, la ricerca del minimo/massimo nella deque prende tempo lineare.
Esistono almeno due modi diversi per ottenere il massimo/minimo di metà della ruota, una con i rangetree e un’altra, decisamente più elegante e facile da scrivere, con minqueue/maxqueue. Aggiungerei anche che con la seconda soluzione ottieni i due valori in O(1) ammortizzato, mentre il range tree va in O(logN)
Comincia col pensare a come puoi simulare una rotazione di K elementi con una sola operazione, magari identificando uno o due indici di riferimento
A quel punto rimane da precalcolare tutti i possibili min/max che ti potrebbero venire richiesti, che se vogliamo è la parte più complicata del problema. Ci sono più modi per farlo e potrebbe servirti una struttura dati
per la simulazione dell’indice che scorre mi sono creato una classe.
class circolar{
public:
int k=0;
vector<int> vet;
int& operator[](int i){
if(i+k<vet.size())
return vet[i+k];
else{ i-=vet.size();
return vet[i+k];}
}
void operator++(){
k--;
if(k<0){
int i= k*-1;
k=vet.size()-i;
}
}
void operator+=(int i){
k-=i;
if(k<0){
int j=k*-1;
k=vet.size()-j;
}
}
};
e funziona. Ora il problema è trovare il massimo e il minimo in un tempo che non sia lineare. Avevo pensato alla ricorsione ma alla fine è sempre O(N). ora vedrò di studiarmi i metodi che mi avete detto.
Sono due cose diverse, in realtà se ne può anche fare a meno di queste due code.
Quello che devi fare è trovare max e min per ogni K compreso tra 0 e 2N.
Il modo più semplice, non ottimale ma che ti permette comunque di ottenere 100/100, è quello di precalcolarteli con un multiset in O(NlogN) : inserisci i primi N e memorizzi min/max per K = 0, dopodiché rimuovi il primo elemento, inserisci il successivo e memorizzi min/max per K = 1, e così via
Con una minqueue e una maxqueue puoi ridurre la complessità a O(N), però devi implementarti tu la struttura.
C’è una soluzione che non utilizza nessuna struttura e si basa sul fatto che l’intervallo su cui cerchi il valore minimo ha dimensione pari a metà dell’array stesso, quindi passa sempre o per il centro o per gli estremi. A quel punto basta calcolare prefissi/suffissi in modo opportuno.
Questa risposta su stackoverflow dovrebbe fare al caso tuo
Comunque sono 2 passaggi da mettere insieme:
Implementare una coda utilizzando internamente due stack
Implementare uno stack in grado di restituire in O(1) il minimo al suo interno - tramite uno stack aggiuntivo che associa ad ogni elemento un minimo parziale
A questo punto ti basta utilizzare questo nuovo minstack al posto dei due stack classici all’interno della queue per ottenere una minqueue.
Per la maxqueue il procedimento è analogo, o in alternativa puoi mantenere all’interno dello stack “speciale” il valore massimo in aggiunta al minimo.
Se io e @filippos intendiamo la stessa cosa, puoi ignorare la questione degli stack e usare direttamente una deque, che è già implementata nella stl.
Vediamo se riesco a spiegare rapidamente come funziona una minqueue (la maxqueue funziona in modo analogo).
L’obiettivo è quello di realizzare una struttura dati che, scorrendo lungo una lista (o qualsiasi altra struttura lineare) di valori, ci permetta di ottenere il minimo dell’intervallo corrente in un tempo decente.
Quello che possiamo fare è mantenere una coda di “possibili candidati”, ovvero tutti e solo i valori che possono essere minimi dell’intervallo corrente. Manteniamo quindi una deque di pair<indice, valore> che aggiorneremo come necessario, in particolare mantenendo tutti gli elementi inseriti in ordine.
Vediamo le singole operazioni:
-Inserimento. Prima di tutto eliminiamo dalla fine della coda tutti gli elementi che hanno valore maggiore dell’elemento corrente, e inseriamolo (ovviamente come coppia indice-valore). Questo ci garantisce l’ordinamento della deque, e inoltre siamo sicuri che nessuno degli elementi rimossi poteva essere il minimo perché erano tutti maggiori dell’elemento appena inserito.
-Avanzamento. Quando spostiamo la nostra “finestra” in avanti lungo l’array, dobbiamo avere un modo per eliminare gli elementi dell’array che escono dalla finestra. Per spostare la fine della finestra fino ad una posizione p, eliminiamo dalla testa della deque tutti gli elementi che hanno indice minore di p. È garantito che quelli da togliere siano tutti in testa perché li inseriamo sequenzialmente dalla fine della deque.
-Richiesta del minimo. Visto che abbiamo mantenuto l’invariante che gli elementi della deque sono in ordine debolmente crescente dalla testa verso la coda, per ottenere il minimo basta prendere il valore dell’elemento in testa alla coda.
EDIT. Quasi dimenticavo, non ho dimostrato la complessità di esecuzione. Brevemente, ogni elemento dell’array entra ed esce dalla minqueue al più una volta, quindi la complessità è O(N) su tutto l’array, che diventa O(1) ammortizzato per ogni elemento.
Spero di non aver sparato qualche stupidaggine, in caso correggetemi
Si puoi benissimo utilizzare la deque dell’stl
Probabilmente con due stack è più complicato da realizzare ma l’ho letto più volte spiegato in questo modo e penso sia più facile da capire la base che ci sta dietro, nel senso che implementare minstack e queue basata su due stack dovrebbe essere facilmente intuibile.
Inoltre ho trovato prima la versione con il doppio stack che quella con la deque e ho linkato quella
La spiegazione di @dp_1 dovrebbe esserti abbastanza chiara !
Penso di aver capito. Il problema è che avendo una struttura dati che “gira” in questo problema io avrei da togliere ad ogni giro elementi nella minqueue e inserirli nella maxqueue e viceversa… Alla fine il funzionamento è semplice basta che ad ogni inserimento mi controllo se il valore inserito sia maggiore o minore dell’elemento di testa precedentemente in coda. Giusto!!!
Volevo aggiungere una cosa che non ha molto a che fare con la soluzione ma è un “trucco” che ho usato e che spesso ha funzionato. Tra l’altro, si applica anche al problema ricostruzioni.
Mi sono chiesto: “ma se l’elemento che sto rimuovendo dalla coda attuale non era il minimo, perché cercarne un altro?” e similmente per il massimo.
Supponendo che gli elementi sono tutti distinti tra loro, la complessità di un’aggiunta e rimozione può essere resa O(1) nel caso migliore e O(N) in quello peggiore. Mediamente, O(1).
Lo voglio dimostrare. La probabilità che, ad esempio, l’elemento che ho appena rimosso sia il minimo e debba ricorrere a una nuova ricerca è banalmente \frac{1}{N} dove N è il numero di elementi nella nostra coda. Non la faccio lunga con l’analisi randomizzata, basta comunque dire che la complessità “media” è
E[X] = \frac{1}{N} \cdot cN + \frac{N-1}{N} \cdot k = c + k\frac{N-1}{N} \implies \lim_{N\to \infty}\left(c + k\frac{N-1}{N}\right) = c + k = O(1)
(vecchio codice, ancora non ero ermetico come adesso sono… tanto lo dovevo riscrivere )
Con questo voglio solo dire che forse ci volevano dei test case più brutti per fare in modo che la mia soluzione non fosse valida… o magari mi sbaglio ed era contemplato.
)