# Anno Luce (annoluce) **URL:** \ **Category:** Aiuto\ **Created:** [19 Giugno 2017, 8:01pm UTC](https://forum.olinfo.it/t/anno-luce-annoluce/4681 "2017-06-19T20:01:19Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\ **Post date:** [19 Giugno 2017, 8:01pm UTC](https://forum.olinfo.it/t/anno-luce-annoluce/4681/1 "2017-06-19T20:01:19Z")
Ciao a tutti, ho provato a risolvere il problema Anno Luce ma ho avuto dei problemi nel tempo di esecuzione. Tutti i risultati che non vanno in timed-out dannno risultato corretto tranne 4 test. Il mio codice e’ qui : [https://pastebin.com/NmU4tHCX](https://pastebin.com/NmU4tHCX) ---
**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:** [19 Giugno 2017, 10:11pm UTC](https://forum.olinfo.it/t/anno-luce-annoluce/4681/2 "2017-06-19T22:11:41Z")
La discussione era già stata aperta qui [Problema Anno luce: execution timed out](https://forum.olinfo.it/t/problema-anno-luce-execution-timed-out/4671/8) ---
**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:** [19 Giugno 2017, 10:43pm UTC](https://forum.olinfo.it/t/anno-luce-annoluce/4681/3 "2017-06-19T22:43:39Z")
Comunque il problema è la ricerca del numero di stelle che puoi raggiungere, perché tu stai utilizzando una ricerca di tipo lineare quindi O(n) e dovresti invece cercare di portarla ad un O(logN). Un piccolo suggerimento: quando svolgi degli esercizi qui sul forum controlla sempre i suoi tag, anche se effettivamente in gara non vengono mostrati quindi sarebbe come ottenere un indizio “illegalmente”. ---
**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\ **Post date:** [19 Giugno 2017, 10:52pm UTC](https://forum.olinfo.it/t/anno-luce-annoluce/4681/4 "2017-06-19T22:52:04Z")
Ho visto dall’inizio il tag della binary\_search ma non ho capito a che serve la ricerca binaria in questo esercizio… ---
**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:** [19 Giugno 2017, 11:25pm UTC](https://forum.olinfo.it/t/anno-luce-annoluce/4681/5 "2017-06-19T23:25:50Z")
Potresti tenere le distanze delle stelle ordinate che inizialmente ti porta uno rallentamento in quanto devi appunto ordinarle O (nlogn) ma successivamente per ogni q tramite le ricerca binaria potrai trovare la risposta il O (logn) e non O(n) , cambiano la complessità attuale da O (q\*n) ad O (NlogN + q\*logn) , che nel caso in cui q abbia un valore molto maggiore a n diventa molto conveniente ---
**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\ **Post date:** [20 Giugno 2017, 12:02am UTC](https://forum.olinfo.it/t/anno-luce-annoluce/4681/6 "2017-06-20T00:02:25Z")
Grazie @frakkiobello. Ho implementato l’ordinamento e la ricerca binaria. Ho risolto tutti i problemi di timed out ma restano “rossi” per l’output non corretto… Qui c’è il mio nuovo codice : [https://pastebin.com/3WtR6yGV](https://pastebin.com/3WtR6yGV) ---
**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\ **Post date:** [20 Giugno 2017, 7:27am UTC](https://forum.olinfo.it/t/anno-luce-annoluce/4681/7 "2017-06-20T07:27:57Z")
Temo sia overflow: ogni coordinata può arrivare fino a 2^{30}, quindi quando fai `X[i]*X[i]` arrivi a 2^{60} che esce dagli `int` 🙂