Aiutino per Vasi


#61

Non credo sia sbagliato, eseguendo le istruzioni passo passo partendo da un insieme di 15 valori totali che vanno da 0 14

pos 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
val 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

rad diventerà quindi 4 e le deque saranno:

A[0]={ 0, 1, 2, 3}
A[1]={4, 5, 6, 7}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}

Simulando un’operazione di scambio “s 5 8”

primo=5, secondo=8, primadeq=1, secondadeq=2

val=A[1][1]=5 ed è corretto

A.erase(A.begin()+1): quindi toglie il 5 ed le deque diventano:

A[0]={ 0, 1, 2, 3}
A[1]={4, 6, 7}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}

pos=secondo%rad 8%4=0 ed è corretto

A[secondadeq].insert(A[secondadeq].begin()+pos,val); A[2].insert(A[2]+0, 5) e quindi diventeranno:

A[0]={ 0, 1, 2, 3}
A[1]={4, 6, 7}
A[2]={5, 8, 9, 10, 11}
A[3]={12, 13 ,14}

for(int j=primadeq;j<secondadeq;j++)
– A[j].push_back(A[j+1].front());
– A[j+1].pop_front();

A[0]={ 0, 1, 2, 3}
A[1]={4, 6, 7, 5}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}

ed è corretto, e credo di poter affermare la stessa cosa anche con primo>secondo ma provo lo stesso

Partendo dal caso corrente effettuo un s 6 1

primo=6 secondo=1 primadeq=6/1 =1 secondadeq1=1/4=0

val=A[1][6%4]=A[1][2]=7 ed è corretto

pos=secondo%rad= 1

A[secondadeq].insert(A[secondadeq].begin()+pos,val);= inser(A[0]+1, val)
e diventa:

A[0]={ 0,7, 1, 2, 3}
A[1]={4, 6, 7, 5}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}

A[primadeq].erase(A[primadeq].begin()+primo%rad);

A[1].erase(A[1]+2) e diventa

A[0]={ 0,7, 1, 2, 3}
A[1]={4, 6, 5}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}

            for(int j=secondadeq;j<primadeq;j++)
            {
                A[j+1].push_back(A[j].back());
                A[j].pop_back();
            }

quindi solo in questo caso for(int j=0;j<1;j++)

A[0]={ 0,7, 1, 2,}
A[1]={3, 4, 6, 5}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}

Ed è corretto, quindi sono ancora più perplesso, ripeto che comunque mi sembra strano che il mio worst_case sia solo 0,130s e quindi credo ci sia qualche errore che non è legato alle operazioni sulle deque [quote=“VashTheStampede, post:60, topic:3800”]
n questo momento non sono a casa quindi non riesco ad aiutarti molto,
[/quote]

Nessun problema :smile:


#62

Perdona il ritardo, sono riuscito a pulire un po’ il codice.

Prima di tutto, all’inizio quando creavi le deque leggevi anche da input, quando invece dovresti crearle al volo con i valori da 0 a N-1 :stuck_out_tongue:

Un’altra svista che ho notato è nel ciclo delle query: la condizione dell’if dovrebbe essere primadeq<secondadeq, non primo<secondo.

Poi, dovresti prima fare l’erase, poi la serie di push/pop e solo dopo l’insert, altrimenti ti ritrovi con delle posizioni sfasate (prova a fare la stampa delle deques ad ogni query e te ne accorgi subito).

Infine ci sono problemi di TLE, sinceramente ho provato in tutti i modi a farlo stare dentro: ho sostituito deque<deque> con vector<deque>, ho sostituito gli ifstream con gli scanf, i for con i while, i push con gli emplace, ma continua a darmi casi peggiori di 1.54s.

Quando l’ho fatto io non ho usato insert/erase ma usavo una serie di pop per scovare la posizione giusta; sinceramente non so se è più veloce (mi sembra strano che la STL non abbia implementato insert/erase a dovere).
Credo però di aver usato getchar_unlocked per leggere :see_no_evil:

Codice corretto


#63

Nessun problema , anzi grazie mille!!

Questo era il problema che molto probabilmente non trovavo

non sapevo che i while fossero più veloci dei for e tanto meno che gli emplace fossero più veloci dei push

Onestamente non so di cosa si tratti, ma dai messaggi scritti precedentemente in questo topic credo si tratti di fastInput e fastOutput? e se si di cosa si tratta?

Per quanto riguarda la tempistica cerco di fare un bel po si sottoposizioni hahah


#64

getchar_unlocked() legge e ritorna un unico carattere e lo fa veramente velocemente.

Puoi scriverti una funzione per leggere interi e caratteri sfruttando getchar_unlocked(), devi solo fare attenzione agli spazi e agli \n, perché, appunto, legge tutto e non salta niente.
Per gli interi di solito uso questo dando per scontato la corretta formattazione dell’input (altrimenti dovresti fare dei controlli in più)

void readInt(int& n)
{
    n = 0;
    char c = getchar_unlocked();
    while(c>='0' and c<='9') { //si ferma appena leggo ' ' o '\n'
        n = (n<<1) + (n<<3) + (c-'0'); // n = n*2 + n*8 + digit = n*10 + digit
        c = getchar_unlocked();
    }
}

Ma solo se è veramente richiesto un plus in prestazioni, altrimenti è più comodo e sicuro usare scanf/cin e printf/cout.

Ormai alle Olimpiadi si utilizzano i grader quindi non è più necessario leggere l’input :slight_smile:


#65

Ok grazie mille, sono anche riuscito ad ottenere 100/100 dopo “solo” 16 sottoposizioni, adesso la vera domanda è come fare vasi2 :smile:, da quello che ho letto precedentemente nel topic servirebbe un range tree ma onestamente non so cosa sia, per adesso con gli “alberi” non so fare ancora nulla tranne il fenwick, da dove mi consigli/ate di cominciare e quali dispense utilizzare?


#66

No per vasi2 ti serve un altro tipo di albero e credimi che è troppo una scocciatura da scrivere :joy:


#67

Dici che non “ne vale la pena”, nel senso, è un algoritmo/strategia che ha un vasto utilizzo?Nel caso credo che ci darò comunque un’occhiata


#68

Sfrutta (a meno di complicazioni, perché ho saputo che alcuni l’hanno risolto scrivendo una struttura ad hoc per il problema) un albero che è già in STL, con l’unica differenza che la chiave va ricercata implicitamente nella struttura dell’albero.

Quindi no, non ha un vasto utilizzo per le Oli, quasi sempre ti basteranno le strutture della STL :stuck_out_tongue:


#69

MI sto accorgendo qui sul forum la grande quantità delle miei carenza :rofl:, anche se effettivamente di queste strutture/algoritmi non si parla a scuola. [quote=“VashTheStampede, post:68, topic:3800”]
STL
[/quote]

STL è la libreria che contiene i container? :smile: , ossia questi:http://www.cplusplus.com/reference/stl/

Comunque credo che mi manchino le basi sugli alberi, che devo imparare , prima di svolgere questo problema, perché l’unico esercizio, se lo si può definire tale con gli alberi che saprei fare attualmente è quello di ricerca di cammino massimo e minimo tramite una matrice, quindi nemmeno totalmente sugli alberi.
Come dispensa credo di poter utilizzare questa giusto?
https://cses.fi/book.html

Per quanto riguarda le olimpiadi ormai è tardi, perché entrambi gli anni mi sono qualificato abbastanza facilmente alla selezione territoriale, ma l’anno scorso essendo anche il primo anno che ho usato un linguaggio di programmazione a scuola era praticamente impossibile passare per le mie capacità, mentre quest anno mentre si svolgeva la selezioni mi trovavo in stage a Dublino quindi non l ho potuta fare(Ho provato a fare gli esercizi qui su cms e ho ottenuto 100/100 nel primo, 100/100 in quello delle carte e non è nemmeno provato a fare quello dei grafi, in quanto con i 30 pt sarei passato :rage: ), per lo meno sono arrivato sesto nelle olimpiadi a squadre dove abbiamo failato rescalin con un 5/100 pensando solo 10 minuti dopo che era finita la gara alla soluzione(con un 100/100 saremmo arrivati primi a parimerito).
Il vantaggio di non essere arrivato alla finale di Trento è non poter essere umiliato da @lukecavabarrett e @dp_1 , :stuck_out_tongue_winking_eye:


#70

Dimenticavo quasi di ringraziarti per l’aiuto ahhaha, praticamente stai rispondendo a tutti i quesiti che propongo dandomi di fatto lezioni di informatica fra tutti i vari topic :relaxed: , Se avessimo iniziato queste “lezioni” qualche mese fa forse la finale nazionale sarebbe andata meglio. :wink:


#71

Se davvero vuoi fare vasi2, vatti a vedere i bbst e gli avl. Io però ti avverto, senza aver fatto strutture come range et similia prima ti sembreranno abbastanza complicati.


#72

Tanto per info, sono false entrambe le cose in quanto l’assembly generato dai due casi è identico:
for vs while
push_back vs emplace_back

C’è un caso però in cui il while è consigliato in quanto più veloce sia da scrivere che probabilmente da leggere, potrebbe inoltre essere leggermente (aka non rilevante) più efficiente in quanto usa un registro in meno (non deve tenere conto di i) e si risparmia qualche op.


#73

Per la serie, chi non muore si rivede :heart_eyes_cat:.
A volte il while è meglio, ad esempio se devo fare una certa cosa N volte è meglio fare

while(N--)
{
   //cose varie
}

#74

Ahah pur di non studiare per la maturità questo ed altro!
Comunque sì, usato in quel modo è più veloce sia da scrivere che probabilmente da leggere, concordo. Tuttavia in quanto velocità di esecuzione è pressoché uguale alla sua controparte for come dimostrato nel 3° link.
(ora edito il mio commento precedente affinché sia più chiaro che quello è un buon modo per farlo)


#75

while(N--) è uguale a for(;N--;) ma non a for(int i=0;i<N;i++)


#76

Quali fonti mi consigli?


#77

Se non conosci ancora i BST, guardateli, sono alla base dei BBST: https://en.wikipedia.org/wiki/Binary_search_tree. La pagina di wikipedia che ti ho linkato è abbastanza dettagliata, dovresti essere in grado di implementare un bst usando le informazioni che dà.

Con i solo bst comunque non riesci a risolvere vasi2, hai bisogno di un BBST (Balanced Binary Search Tree). Uno dei più semplici che puoi usare è l’AVL, che funziona in modo molto simile a un BST normale ma mantiene l’altezza limitata a \mathcal O(logN). Per prima cosa ti consiglio di studiarti le rotazioni, capite quelle hai praticamente finito. Qui trovi un’implementazione che mi è sembrata facile da capire, mentre su visualgo puoi “giocare” con bst o avl graficamente.

Per vasi2 devi aggiungere un ultimo dettaglio all’avl, perchè alla fine quello che ti serve è cercare un elemento per posizione e non per valore. Posso lasciarlo come esercizio al lettore? :innocent:

Dario


#78

Ok adesso guardo i vari link sperando di capirci qualcosa :smile:

A cosa ti riferisci?


#79

Al fatto che normalmente un (b)bst ti permette di accedere agli elementi per valore, mentre in vasi devi accederci per posizione.


#80

Ok, per ora mi sono letto il Binary Search Tree,(un dubbio, il valore che contiene un nodo è la sua chiave?) e come funziona, quindi i figlio di ogni nodo n , l e r, avranno rispettivamente un valore minore e maggiore rispetto a n, poi ho capito il fatto dell’altezza dell’albero, ogni operazione (inserimento o ricerca) a un worst_case di h passaggi e nel bst normale l’altezza arriva fino a sqrt(n) mentre bilanciandolo, quindi mantenendo la proprietà detta precedentemente, grazie a delle rotazioni (che non ho ancora visto bene :smile: ) si può mantenere h<=log(n) veloccizzando inerimenti e ricerche?

Questo è quello che ho capito fino ad ora spero sia giusto. Mi manca da vedere bene l’implementazione e come adattarlo a questo problema, perché non capisco come sfruttare questa struttura :smile: