Somme Costose 90/100 [Execution Timed Out]

Ciao, è da un po’ che sto cercando di risolvere il problema “Somme Costose” (ecco il link) ma non riesco ad ottenere 100/100 per via dei testcase 16 e 19 che superano il limite di tempo. L’idea è di trovare di volta in volta 2 numeri la cui somma sia la più piccola possibile, tuttavia questo comporta un continuo riordinamento parziale del vettore in cui memorizzo i numeri. Infatti l’algoritmo lavora in questo modo: partendo da un vettore ordinato, vado a sommare gli elementi in posizione i e i+1; memorizzo il risultato in posizione i+1, dopo di che sposto il risultato in avanti nel vettore fino a quando non è di nuovo ordinato. In questo caso la complessità dovrebbe essere O(N2) ma avevo pensato che poiché i valori iniziali si trovano in un range da 1 a 1000, la complessità non arrivasse effettivamente a N2.
In ogni caso vi lascio qui il codice: è almeno parzialmente corretto o devo utilizzare un approccio diverso? Io francamente non ho trovato altre idee per ora…

Ciao,
la tua osservazione è giusta, ogni volta devo prendere i due elementi più piccoli, sommarli e aggiungere la somma al vettore.
Bisogna stare attenti alla parte in cui si aggiunge il numero al vettore, in particolare se lo aggiungo in fondo e ordino il vettore, l’inserimento diventa \mathcal O(N\log N), se uso il counting sort l’inserimento diventa \mathcal O(N+K) che è ancora troppo elevato. Dobbiamo trovare un modo per fare l’inserimento in \mathcal O(\log N) in modo da ottenere una complessità finale di \mathcal O(N\log N).
Senza implementare niente utilizziamo una struttura dati che abbia inserimento in \mathcal O(\log N), dobbiamo scegliere tra una priority_queue oppure un multiset. La prima scelta sembra fare a caso nostro.

Ciao, grazie della risposta. Potresti spiegarmi in cosa consistono una priority_queue e un multiset? (non ne avevo mai sentito parlare prima…)
Su cplusplus.com le priority_queue vengono descritte così:
Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains.
Però non capisco in che modo potrebbe tornarmi utile dato che gli elementi che di volta in volta vado a considerare sono i 2 minori, e non il maggiore. :thinking:

Puoi utilizzare una priority queue anche per il minimo, basta definire un comparatore nella dichiarazione:

priority_queue<int> p;
priority_queue<int, vector<int>, greater<int> > q;

La coda p ritornerà il massimo, la coda q il minimo elemento.

Greater, così come less e (forse?) altri comparatori, è definito nell’header <functional>, che però viene incluso già da <queue>. Quindi finché lo usi in una priority queue puoi non preoccuparti di includere l’header, mentre se lo usi da altre parti potrebbe servirti.

1 Mi Piace

Allora una priority_queue è -per dirlo in modo semplice- un vettore ordinato.
Le due operazioni principali sono push e pop che rispettivamente aggiungono un elemento alla coda ed eliminano l’elemento in cima. Queste operazioni sono entrambe in \mathcal O(\log N). Si può accedere solo all’elemento in cima mediante top.

Il mutliset è un set che ammette duplicati. Il set è una struttura più complicata di una priority_queue poiché sarebbe un albero binario di ricerca bilanciato (credo?), principalmente in più di una priority_queue ha le funzioni erase, che elimina un elemento (non necessariamente in più grande), e find che controlla se un elemento è presente o meno nel set, entrambe le funzioni sono in \mathcal O(\log N).

Leggendo su internet mi pare di capire che la priority_queue è costituita internamente da un altro container che di default è il vector, ma può essere cambiato come nel tuo secondo esempio @dp_1 specificandolo al posto di vector. Tuttavia non mi è chiaro se la priority_queue si limita a mettere in prima posizione l’elemento maggiore o se anche tutto il resto è ordinato. (Se così fosse potrei tranquillamente evitare di specificare il comparatore e utilizzare pop_back() per accedere all’ultimo elemento).

Grazie ancora @bortoz, mi hai chiarito anche la domanda che ho posto nell’ultima risposta. Adesso cerco di utilizzare questa priority_queue.

Io l’ho risolto con il multiset che in questo caso ha lo stesso utilizzo.
Il multiset è una struttura molto utile in molti casi, è una struttura che mantiene dei valori, solitamente interi ma non solo, in modo ordinato, quindi in ordine crescente, questa caratteristica gli permette di avere vantaggi in molti casi, questo è uno di quelli.

Il multiset lo trovi nella libreria "set"utilizza dei puntatori per gestire i valori che contiene.

Per lavorare con i valori dovrai usare questo tipo di puntatore multiset<int>::iterator it; che se incrementato porta al valore successivo.
Supponiamo di aver dichiarato un multiset di int chiamato A: multiset < int > A;
Le funzioni principali sono:

A.insert(10); //inserisce il 10 quindi adesso A contiene solo 10
facendo
for(int i=0;i<5;i++)
    A.insert(i);
//A contiene : 0,1,2,3,4,10
//La funzione find() restituisce il puntatore all'elemento cercato
multiset<int>::iterator it;
it=A.find (5);
//in questo modo utilizzando l'"*" possiamo conoscere il valore che corrisponde al puntatore
cout<<*it;  //Verrà stampato il numero 5
//la funzione erase() elimina il valore presente al puntatore che gli viene passato come parametro 
//I principali puntatori sono: A.begin() che corrisponde al primo valore, A.rbegin() che 
//corrisponde all'ultimo valore e A.end() che corrisponde al puntatore dopo l'ultimo valore

cout<<*A.begin() //stampa 0
cout<<*A.rbegin()// stampa 10
for(it=A.begin(), it!=A.end();it++)
   cout<<*it; //stampa 0 1 2 3 4 10

//quindi
A.erase(A.begin()); //A contiene 1 2 3 4 10 
A.erase(A.rbegin()); // A contiene 1 2 3 4 


// Altre funzioni utili sono:
A.size(); // che restituisce il numero di elementi presenti nel multiset in questo caso 4
A.count(3);//restituisce il numero di volte che è presente il 3 quindi in questo caso una 

it=A.upper_bound(2),//restituisce il puntatore al valore strettamente maggiore del parametro in questo caso 3

 

L’efficienza del multiset è che molte delle operazioni sono fatte in tempo logaritmico in quanto sfrutta un bbst

In questo esercizio bastano le funzioni di begin(), insert() ed erase()

1 Mi Piace

Grazie @frakkiobello per la spiegazione. :slight_smile:

Magari prova a implementarlo anche con il multiset per vedere se hai effettivamente capito il funzionamento ma comunque è molto semplice.

1 Mi Piace

Indipendentemente dal fatto che sia ordinata o meno, puoi accedere solo al valore in cima.[quote=“Thermix, post:6, topic:4757”]
Se così fosse potrei tranquillamente evitare di specificare il comparatore e utilizzare pop_back() per accedere all’ultimo elemento
[/quote]

Non ho capito cosa intendi dire, non esiste la funzione pop_back nelle priority_queue ma solo pop che elimina l’elemento in cima.

Personalmente penso che in questo caso sia più semplice utilizzare una priority_queue, il set solitamente lo uso solo quando devo avere tutti gli elementi ordinati e devo accedere ad un elemento specifico.

Concordo anche se non ce moltissima differenza, intendo dire che l’implementazione è molto semplice anche con il multiset e la complessità dovrebbe rimanere uguale.

1 Mi Piace

Ho implementato il programma con la priority_queue e ho ottenuto 100/100. Alla fine mi è anche tornato utile utilizzare i comparatori.

Si ho visto, avevo pensato che contenendo un vector avesse grosso modo gli stessi metodi.[quote=“frakkiobello, post:10, topic:4757, full:true”]
Magari prova a implementarlo anche con il multiset per vedere se hai effettivamente capito il funzionamento ma comunque è molto semplice.
[/quote]

Adesso provo, grazie del suggerimento.

Ecco fatto, ho risolto il problema anche con il multiset e ho ottenuto 100/100. A scopo informativo, con la priority_queue in alcuni casi il tempo impiegato è addirittura dimezzato rispetto al multiset (forse ho sbagliato io qualcosa, quindi vi lascio i codici nel caso voleste visionarli).
Soluzione con priority_queue
Soluzione con multiset
Grazie mille a tutti!

Le funzioni di push() ed insert() dovrebbero avere la stessa complessità che corrisponde a \mathcal O(logN), credo che la differenza sia apportata dalla funzioni erase() e pop() che hanno rispettivamente come complessità “amortized constant.” e \mathcal O(1).

Suppongo che anche la maggior vastità di funzione che possiede il multiset portino ad un numero maggiore di operazioni anche se non troppo rilevanti.

Effettivamente se le funzioni a disposizione per la priority_queue sono sufficienti conviene utilizzare quella anche se la differenza è poca

2 Mi Piace

Si infatti, inoltre come ha detto anche Borto in questo caso non era necessario avere tutto il vettore ordinato, bastava che gli elementi estratti corrispondessero di volta in volta al valore minore.