# "Execution timed out" su Persian Party **URL:** \ **Category:** Aiuto\ **Created:** [3 Marzo 2019, 2:01pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598 "2019-03-03T14:01:05Z")\ **Posts on this page:** 18\ **Page:** 1
**Author:** ![Ez\_Pz](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ez_pz/32/597_2.png) [@Ez\_Pz](https://forum.olinfo.it/u/Ez_Pz)\ **Post date:** [3 Marzo 2019, 2:01pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/1 "2019-03-03T14:01:05Z")
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](https://pastebin.com/yLV4040N) Edit : Ho risolto ecco la mia soluzione: [https://pastebin.com/AAyc5fuD](https://pastebin.com/AAyc5fuD) ---
**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\ **Post date:** [3 Marzo 2019, 4:14pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/2 "2019-03-03T16:14:08Z")
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)). ---
**Author:** ![Ez\_Pz](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ez_pz/32/597_2.png) [@Ez\_Pz](https://forum.olinfo.it/u/Ez_Pz)\ **Post date:** [3 Marzo 2019, 7:55pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/3 "2019-03-03T19:55:59Z")
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: ![Immagine](https://forum.olinfo.it/uploads/default/original/1X/12445703f8ff682a5f8c21549feb4a10fdcee5be.jpeg) 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. ---
**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\ **Post date:** [3 Marzo 2019, 8:10pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/4 "2019-03-03T20:10:57Z")
> [@Ez\_Pz](#): > > Non ho capito che intendi con quelle formule ma comunque ti spiego l’idea su cui è basato l’algoritmo che ho scritto. 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 : ```auto 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 : ```auto for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ // istruzioni } } ``` > [@Ez\_Pz](#): > > 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). 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 ? ---
**Author:** ![Ez\_Pz](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ez_pz/32/597_2.png) [@Ez\_Pz](https://forum.olinfo.it/u/Ez_Pz)\ **Post date:** [3 Marzo 2019, 8:56pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/5 "2019-03-03T20:56:55Z")
> [@zJack1342](#): > > 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? ---
**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\ **Post date:** [3 Marzo 2019, 9:39pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/6 "2019-03-03T21:39:38Z")
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 ‘$’. ---
**Author:** ![Ez\_Pz](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ez_pz/32/597_2.png) [@Ez\_Pz](https://forum.olinfo.it/u/Ez_Pz)\ **Post date:** [4 Marzo 2019, 9:55am UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/7 "2019-03-04T09:55:27Z")
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](https://pastebin.com/va7Fkchy) ---
**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\ **Post date:** [4 Marzo 2019, 11:07am UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/8 "2019-03-04T11:07:09Z")
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? ---
**Author:** ![Ez\_Pz](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ez_pz/32/597_2.png) [@Ez\_Pz](https://forum.olinfo.it/u/Ez_Pz)\ **Post date:** [4 Marzo 2019, 6:18pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/9 "2019-03-04T18:18:12Z")
Ho pensato a una soluzione che dovrebbe essere _O(N)_. codice: [Persian Party - Pastebin.com](https://pastebin.com/AWi4zd3x) 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 😕 ![Immagine](https://forum.olinfo.it/uploads/default/original/1X/4746993b9ca3540d66178eebf2582e2caa60b0de.jpeg) Non conoscendo gli input non saprei quale sia l’errore. ---
**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\ **Post date:** [4 Marzo 2019, 8:30pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/10 "2019-03-04T20:30:44Z")
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 : ```auto 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? ---
**Author:** ![Ez\_Pz](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ez_pz/32/597_2.png) [@Ez\_Pz](https://forum.olinfo.it/u/Ez_Pz)\ **Post date:** [4 Marzo 2019, 9:30pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/11 "2019-03-04T21:30:28Z")
> [@zJack1342](#): > > 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. 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. ---
**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\ **Post date:** [4 Marzo 2019, 10:33pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/12 "2019-03-04T22:33:04Z")
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? ---
**Author:** ![Ez\_Pz](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ez_pz/32/597_2.png) [@Ez\_Pz](https://forum.olinfo.it/u/Ez_Pz)\ **Post date:** [6 Marzo 2019, 7:35pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/13 "2019-03-06T19:35:37Z")
Ho fatto quest’altra soluzione che usa il sort: [https://pastebin.com/NN9fHkAx](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? ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [6 Marzo 2019, 10:06pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/14 "2019-03-06T22:06:20Z")
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. ---
**Author:** ![Ez\_Pz](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ez_pz/32/597_2.png) [@Ez\_Pz](https://forum.olinfo.it/u/Ez_Pz)\ **Post date:** [7 Marzo 2019, 12:04pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/15 "2019-03-07T12:04:40Z")
Scusa non ho capito, se i vettori sono ordinati non avvengono sempre prima gli ingressi? ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [7 Marzo 2019, 1:33pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/16 "2019-03-07T13:33:14Z")
Prendiamo come esempio il seguente testcase : ```auto 4 6 8 2 4 1 5 3 7 ``` Ed ordiniamo, come detto gli ingressi e le uscite: ```auto ingressi[]={1,2,3,6} uscite[]={4,5,7,8} ``` E procediamo come detto: - Il prossimo ingresso è 1 mentre l’uscita 4, quindi avviene prima l’ingresso: il numero di persone aumenta ad 1. - Il prossimo ingresso è 2 mentre l’uscita 4, quindi avviene prima l’ingresso: il numero di persone aumenta a 2, e le strette aumentano a 1(il numero di persone presenti). - Il prossimo ingresso è 3 mentre l’uscita 4, quindi avviene prima l’ingresso: il numero di persone aumenta a 3, le strette di mano diventano 3. - Il prossimo ingresso è 6 mentre l’uscita 4, quindi avviene prima l’uscita: il numero di persone diventa 2, e le strette di mano diventano 5. - Il prossimo ingresso è 6 mentre l’uscita 5, quindi avviene prima l’uscita: il numero di persone diventa 1 e le strette di mano 6. - Il prossimo ingresso è 6 mentre l’uscita 7, quindi avviene prima l’ingresso: il numero di persone aumenta a 2 e le strette a 7. - Rimangono solo uscite quindi prima esce il 7, che stringe la mano all’altra persona ed infine esce l’8. Le strette sono 7 alle quali si aggiungono le 2N strette con l’host, e diventano 16. ---
**Author:** ![Ez\_Pz](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ez_pz/32/597_2.png) [@Ez\_Pz](https://forum.olinfo.it/u/Ez_Pz)\ **Post date:** [10 Marzo 2019, 8:49pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/17 "2019-03-10T20:49:53Z")
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\ **Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [10 Marzo 2019, 9:42pm UTC](https://forum.olinfo.it/t/execution-timed-out-su-persian-party/5598/18 "2019-03-10T21:42:36Z") > [@Ez\_Pz](#): > > (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: ```auto using namespace std; const int MAXN=1000000; int a[MAXN], b[MAXN]; int main(){ return 42; } ```