# Help: Wheel of Fortune **URL:** \ **Category:** Aiuto\ **Created:** [14 Aprile 2017, 8:33am UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612 "2017-04-14T08:33:08Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![bigsheep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/97f17d/32.png) [@bigsheep](https://forum.olinfo.it/u/bigsheep)\ **Post date:** [14 Aprile 2017, 8:33am UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/1 "2017-04-14T08:33:08Z")
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?? ```auto int main(){ ifstream in("input.txt", ios::in); ofstream out("output.txt", ios::out); int N,M; in>>N; deque vet; for(int i=0, k; i>k; vet.push_back(k);} in>>M; for(int i=0,k; i>k; for(int j=0; k>0; k--){ j=vet.back(); vet.pop_back(); vet.push_front(j); } out<<*min_element(vet.begin(),vet.begin()+N)<<" "<<*max_element(vet.begin()+N, vet.end())< **Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [14 Aprile 2017, 11:36am UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/2 "2017-04-14T11:36:16Z") 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! > [@Wheel of fortune](https://forum.olinfo.it/t/wheel-of-fortune/4131): > > Qualcuno ha risolto wheel? Avevo pensato di usare una coda statica circolare, ma avrei molta difficoltà nell’implentarla, quindi ero in cerca di una soluzione più semplice > [@Wheel aiuto TLE](https://forum.olinfo.it/t/wheel-aiuto-tle/4146/): > > Salve a tutti, sto provando a risolvere il problema ois\_wheel e fin’ora riesco ad ottenere soltanto 70/100, il metodo che utilizzo è basato sulle strutture dati queue e multiset. Infatti utilizzo due code (avrei potuto usare una deque) per memorizzare gli elementi presenti nelle due parti della ruota e due multiset che mi permettono velocemente di vedere il minimo-massimo di ogni insieme. Non trovo altri modi per fare questo esercizio più velocemente… Qualche suggerimento? #include \ [@Wheel of fortune problema](https://forum.olinfo.it/t/wheel-of-fortune-problema/4305/): > > Ciao, sto cercando di svolgere wheel of fortune e sono convinto che per fare 100/100(fino ad ora ho fatto solo 70), devo segnare in una struct i valori del massimo e del minimo per ogni combinazione della ruota. Calcolando il minimo e il massimo con dei cicli for che vanno rispettivamente da 0 a n-1 e da n a 2n l ultimo subtask fallisce per il tempo. ho deciso quindi di creare una deque e due multi set dove inserisco rispettivamente i valori che ci sono all interno nella ruota dopo gli spostam… ---
**Author:** ![bigsheep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/97f17d/32.png) [@bigsheep](https://forum.olinfo.it/u/bigsheep)\ **Post date:** [14 Aprile 2017, 12:00pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/3 "2017-04-14T12:00:26Z")
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 ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [14 Aprile 2017, 12:12pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/4 "2017-04-14T12:12:17Z")
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) ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [14 Aprile 2017, 12:27pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/5 "2017-04-14T12:27:51Z")
> [@bigsheep](#): > > 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 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 ---
**Author:** ![bigsheep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/97f17d/32.png) [@bigsheep](https://forum.olinfo.it/u/bigsheep)\ **Post date:** [14 Aprile 2017, 1:17pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/6 "2017-04-14T13:17:07Z")
per la simulazione dell’indice che scorre mi sono creato una classe. ```auto class circolar{ public: int k=0; vector vet; int& operator[](int i){ if(i+k **Author:** ![bigsheep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/97f17d/32.png) [@bigsheep](https://forum.olinfo.it/u/bigsheep)\ **Post date:** [14 Aprile 2017, 1:20pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/7 "2017-04-14T13:20:02Z") > [@dp\_1](#): > > minqueue/maxqueue per caso dovrei usare una priority\_queue?? ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [14 Aprile 2017, 4:59pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/8 "2017-04-14T16:59:50Z")
> [@bigsheep](#): > > per caso dovrei usare una priority\_queue?? 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. ---
**Author:** ![bigsheep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/97f17d/32.png) [@bigsheep](https://forum.olinfo.it/u/bigsheep)\ **Post date:** [14 Aprile 2017, 5:18pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/9 "2017-04-14T17:18:02Z")
mi dareste una guida per queste strutture?? sulla minqueue e maxqueue non trovo nulla… ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [14 Aprile 2017, 5:37pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/10 "2017-04-14T17:37:32Z")
> [@bigsheep](#): > > mi dareste una guida per queste strutture?? sulla minqueue e maxqueue non trovo nulla… Questa risposta su [stackoverflow](http://stackoverflow.com/a/4802260) 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. ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [14 Aprile 2017, 7:17pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/11 "2017-04-14T19:17:57Z")
Invece di implementarsi la coda con due stack, non basterebbe usare una deque? ---
**Author:** ![bigsheep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/97f17d/32.png) [@bigsheep](https://forum.olinfo.it/u/bigsheep)\ **Post date:** [14 Aprile 2017, 8:06pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/12 "2017-04-14T20:06:34Z")
aspettate non sto capendo. Implementando la coda userei uno stack per il minimo e uno per il massimo? ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [14 Aprile 2017, 10:32pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/13 "2017-04-14T22:32:13Z")
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\ 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 😅 Dario ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [14 Aprile 2017, 11:06pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/14 "2017-04-14T23:06:57Z")
> [@dp\_1](#): > > Invece di implementarsi la coda con due stack, non basterebbe usare una deque? 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 ! ---
**Author:** ![bigsheep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/97f17d/32.png) [@bigsheep](https://forum.olinfo.it/u/bigsheep)\ **Post date:** [15 Aprile 2017, 9:44am UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/15 "2017-04-15T09:44:50Z")
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!!! ---
**Author:** ![erolm\_a](https://forum.olinfo.it/user_avatar/forum.olinfo.it/erolm_a/32/514_2.png) [@erolm\_a](https://forum.olinfo.it/u/erolm_a)\ **Post date:** [21 Dicembre 2017, 3:27pm UTC](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/16 "2017-12-21T15:27:02Z")
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) ```auto void preprocess() { minimal = min_element(wheel.begin(), wheel.begin() + N) - wheel.begin(); maximal = max_element(wheel.begin() + N, wheel.end()) - wheel.begin(); queries[0][0] = wheel[minimal], queries[0][1] = wheel[maximal]; for(int i = 1; i < 2*N; i++) { // rotate wheel.push_front(wheel.back()); wheel.pop_back(); if(wheel[0] <= queries[i-1][0]) minimal = 0; else if(minimal == N-1) minimal = min_element(wheel.begin(), wheel.begin() + N) - wheel.begin(); else minimal++; if(wheel[N] >= queries[i-1][1]) maximal = N; else if(maximal == 2*N - 1) maximal = max_element(wheel.begin() + N, wheel.end()) - wheel.begin(); else maximal++; queries[i][0] = wheel[minimal], queries[i][1] = wheel[maximal]; } wheel.push_front(wheel.back()); wheel.pop_back(); } ``` (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.