Qualcuno saprebbe aiutarmi ad ottimizzare il programma che ho fatto?
Ho totalizzato 80/100 punti, perché mi da “Execution timed out” negli ultimi 4 Testcase del Subtask 4.
Codice: https://pastebin.com/yLV4040N
Edit :
Ho risolto ecco la mia soluzione: https://pastebin.com/AAyc5fuD
Prova a spiegare la tua idea.
A una prima vista il tuo algoritmo è O(N^2), troppo lento per le assunzioni in cui N <= 2 *10^5.
Dovresti trovare una soluzione O(N) o O(N log(N)).
Non ho capito che intendi con quelle formule ma comunque ti spiego l’idea su cui è basato l’algoritmo che ho scritto.
In un ciclo infinito ogni volta verifica se l’arrivo della persona i è minore dell’uscita della persona j, se è vero allora controlla se a[i] è maggiore dell’arrivo di j (che aumenta di 1 fino a n-1 ogni volta).
Questo serve per capire se al momento dell’arrivo di i, nella festa siano presenti anche le persone j per poter fare le strette di mano.
Per esempio prendiamo in considerazione i seguenti input:
n=4 (numero di persone andate alla festa)
a[n]={6,2,1,3}(tempi di arrivo delle persone numerate da 0 a n-1)
d[n]={8,4,5,7}(tempi di uscita / / )
Questa tabella rappresenta il mio ragionamento:
Mi sono accorto che le strette di mano all’entrata sono sempre uguali a quelle fatte all’uscita dato che le persone non possono ne entrare ne uscire più di uno per volta. Quindi bastava calcolare (con il loop descritto prima) quante strette di mano avrebbe fatto ciascuno all’arrivo per poi moltiplicare il totale per 2 e sommarlo alle strette con il proprietario.
Le formule indicano il tempo che impiega il tuo algoritmo a risolvere un problema a seconda della grandezza del input. Di solito si usa la variabile N per indicare tale grandezza.
La notazione che sto usando è la Big O Notation che indica il caso peggiore.
Con O(N) si intende che il tuo algoritmo per risolvere un problema itera una volta su tutti gli elementi di input.
esempio :
for(int i = 0; i < N; i++){
// istruzioni
}
O(N^2) invece indica che il tuo algoritmo per ogni elemento presente itera tutti gli altri elementi.
esempio :
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
// istruzioni
}
}
Solo da questa espressione si capisce che per ogni persona iteri tutto il vettore.
Riusciresti a capire se una persona è entrata prima di un altra senza iterare ogni volta su ogni elemento ?
Grazie, ho capito il significato di quelle formule, ma non saprei come trasformare il mio algoritmo da O(N^2) a O(N).
Avresti qualche indizio?
Non so se esista una soluzione lineare O(N), ma proviamo a migliorare la quadratica O(N^2).
In questo momento il tuo algoritmo cerca sempre la persona con l’ arrivo minore o uscita minore che non si è già processata; se invece di cercarla linearmente non la trovassimo con una ricerca più intelligente?
E poi ci interessa sapere quale persona è interessata oppure ci serve un’ altra informazione legata alle entrate e uscite?
Btw per scrivere in modo figo le complessità basta metterle tra il simbolo del dollaro ‘$’.
Ho fatto una versione dell’algoritmo O(n^2) più leggibile ed è un po’ più veloce degli altri due, ma non abbastanza da risolvere gli ultimi 3 Testcase.
codice: https://pastebin.com/va7Fkchy
O(N^2) è troppo lenta come ti ho già detto, il problema richiede una soluzione più veloce.
Le strette di mano avvengono quando una presona entra o esce, quindi ciò che ci interessa è sapere quante persone sono presenti al momento di questi due avvenimenti.
Per essere presenti a uno di questi due avvenimenti una persona deve essere entrata prima ed deve essere uscita dopo.
Prova a cambiare il modo di contare, per pensarci simula l’ andamento della festa dei casi d’esempio.
Cosa noti?
Ho pensato a una soluzione che dovrebbe essere O(N).
codice: Persian Party - Pastebin.com
Osservando la tabella che ho fatto ieri mi sono accorto che V (numero di strette di mano totali), è uguale alle zone colorate cioè i tempi “t” in cui sono presenti le persone (dato che per ipotesi la porta può far passare solo una persona alla volta).
Quindi il mio nuovo algoritmo consiste nel calcolare N volte la differenza tra d[i] e a[i] + 1 (zone colorate orizzontalmente).
Per esempio, prendiamo in considerazione i primi due input:
a=6 e d=8 quindi per calcolare le strette di mano avvenute in quel lasso di tempo “t” si fa 8-6+1=3.
Tuttavia caricandolo mi da come valutazione 0/100 
Non conoscendo gli input non saprei quale sia l’errore.
Di solito quando si cerca di trovare errori e si ha a disposizione una soluzione lenta che però risponde correttamente si può effettuare il cross checking.
Il cross checking in poche parole consiste nel sottoporre ai due algoritmi dei test case per verificare cosa stampano in output. Se le due soluzioni non coincidono puoi cercare nel test case e nel codice la causa.
Se ci pensi la tua idea non ha senso ed è facile intuire cosa sbaglia.
Ecco uno dei tanti casi che il tuo algoritmo non risolve :
input
2
1 10
5 15
output
6
Prendendo in considerazione ogni istante relativo nel primo caso d’ esempio :
input
4
6 8
2 4
1 5
3 7
A = arriva
E = esce
1 2 3 4 5 6 7 8
A A A E E A E E
Quali considerazioni puoi fare?
E’ quello a cui avevo pensato prima che tu mi rispondessi e l’errore che ho trovato è che ho dato per scontato che per ogni istante “t” abbia sempre qualcuno che entri o esca ma a quanto pare non sempre è così.
Dovrei in qualche modo migliorare questo algoritmo o pensare ad uno completamente diverso?
Scusa per queste domande stupide ma è che sono ancora alle prime armi.
Tranqui.
Io direi di trovarne una soluzione completamente diversa ma vorrei provare a farti arrivare alla soluzione esaminando il tuo algoritmo O(N^2).
Nella soluzione quadratica che hai implementato, ciò che rende inefficiente l’algoritmo è la ricerca lineare di quante persone sono presenti all’arrivo e uscita di una persona. La ricerca più intelligente è la ricerca binaria che ti permette di trovare un elemento in O(log_2(N)). La ricerca binaria però vuole che gli elementi siano oridnati (cerca su google std::sort).
Quindi per migliorare la tua soluzione dovresti applicare un ordinamento e poi cercare.
Ma una volta ordinati, ha senso cercare? Se si cosa?
Ho fatto quest’altra soluzione che usa il sort: https://pastebin.com/NN9fHkAx
E’ più veloce delle altre tuttavia fa lo stesso 80/100 sbagliando gli ultimi 3 testcase dando “Execution timed out”.
Non capisco perché, come potrei migliorare ancora di più le prestazioni del programma?
Supponi di avere 2 vettori ingresso[] ed uscita[] entrambi ordinati, allora guardi se avviene prima il prossimo ingresso oppure la prossima uscita:
Se avviene prima l’ingresso allora incrementi il numero di persone attuali.
Se avviene prima l’uscita allora aggiorni la soluzione e decrementi il numero di persone attuali.
Scusa non ho capito, se i vettori sono ordinati non avvengono sempre prima gli ingressi?
Prendiamo come esempio il seguente testcase :
4
6 8
2 4
1 5
3 7
Ed ordiniamo, come detto gli ingressi e le uscite:
ingressi[]={1,2,3,6}
uscite[]={4,5,7,8}
E procediamo come detto:
Grazie, ho risolto il problema ed ora mi da 100/100.
Il mio codice usa un algoritmo simile al tuo ma più veloce perché dato che la somma delle strette di mano fatte all’entrata di ciascuna persona è sempre uguale alle strette fatte all’uscita, il ciclo si ferma a (i<n) calcolando solo le strette fatte all’entrata, quindi in fine basta raddoppiare la somma calcolata “V” aggiungendo 2N .
Codice: https://pastebin.com/CXC3U59B
(ho usato i vettori anziché gli array perché gli ultimi due testcase usano un N troppo alto quindi va in Stack Overflow dando un output errato).
Succede perché allochi l’array sulla memoria sbagliata, puoi fare:
using namespace std;
const int MAXN=1000000;
int a[MAXN], b[MAXN];
int main(){
return 42;
}