Codeforce edu round 93 C accettato in n^2 perchè?

https://codeforces.com/contest/1398/submission/89922404?fbclid=IwAR2k76S9G8ozwy_ybCa-a-BRSqDkeSGZsxzsg0nfR5XCcoBFgGE0dHPXLIc

c è anche un post in top , ma è presente una confusione tra le varie risposte
top https://codeforces.com/blog/entry/81467

La complessità temporale non è sempre affidabile come sembra, tutti i fattori costanti vengono ignorati e, come in questo caso, possono fare la differenza.

In particolare in questo problema il numero di iterazioni eseguite è \frac{n\cdot(n-1)}{2}\approx\frac{10^{10}}{2}=5\cdot10^9 che è un numero relativamente piccolo. Il motivo però per cui il programma è così veloce, è che queste istruzioni sono molto semplici per cui il processore può ottimizzare alcune parti:

  • gli accessi all’array vengono tutti eseguiti sequenzialmente per cui il processore può facilmente salvare in cache gli elementi successivi,
  • l’assenza di if permette al processore di prevedere facilmente le istruzioni successive,
  • vengono utilizzate le istruzioni vettoriali AVX che combinate con -funroll-loops permettono di eseguire in parallelo 8 iterazioni alla volta.

Infine per consentire ai partecipanti di utilizzare python e java, il time limit è stato impostato abbastanza alto permettendo a questa soluzione di risolvere tutti i testcase.

2 Mi Piace