# Problema Anno Luce (ois\_annoluce)

**URL:** <https://forum.olinfo.it/t/problema-anno-luce-ois-annoluce/3986>\
**Category:** Aiuto\
**Created:** [11 Settembre 2016, 12:50pm UTC](https://forum.olinfo.it/t/problema-anno-luce-ois-annoluce/3986 "2016-09-11T12:50:20Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![RayperZ](https://forum.olinfo.it/user_avatar/forum.olinfo.it/rayperz/32/358_2.png) [@RayperZ](https://forum.olinfo.it/u/RayperZ)\
**Post date:** [11 Settembre 2016, 12:50pm UTC](https://forum.olinfo.it/t/problema-anno-luce-ois-annoluce/3986/1 "2016-09-11T12:50:20Z")

</div>

Salve a tutti, ho provato a risolvere il problema Anno Luce (ois\_annoluce), ma ho un problema riguardo al tempo di esecuzione. Tutti i task che non vanno in timeout, mi danno risultato corretto ma non capisco in che modo posso riuscire a velocizzare l’esecuzione del codice.

Il codice è il seguente: [http://pastebin.com/aeSkkXeh](http://pastebin.com/aeSkkXeh)

L’algoritmo in se è corretto, solo che non capisco come posso fare per ottimizzarlo e risucire a superare l’errore del timeout.

---

<div class="post-metadata">

**Author:** ![paolo](https://forum.olinfo.it/user_avatar/forum.olinfo.it/paolo/32/3203_2.png) [@paolo](https://forum.olinfo.it/u/paolo)\
**Post date:** [11 Settembre 2016, 1:47pm UTC](https://forum.olinfo.it/t/problema-anno-luce-ois-annoluce/3986/2 "2016-09-11T13:47:53Z")

</div>

Quale è l’altro tipo di ricerca che conosci??

---

<div class="post-metadata">

**Author:** ![GiackAloZ](https://forum.olinfo.it/user_avatar/forum.olinfo.it/giackaloz/32/594_2.png) [@GiackAloZ](https://forum.olinfo.it/u/GiackAloZ)\
**Post date:** [11 Settembre 2016, 5:55pm UTC](https://forum.olinfo.it/t/problema-anno-luce-ois-annoluce/3986/3 "2016-09-11T17:55:43Z")

</div>

Dato lo scopo del problema (come anche evidenziato dal tag) la soluzione che ti permette di non incorrere in TLE è la ricerca binaria.  
Sai di cosa si tratta o come funziona?  
Se si, vorresti avere ulteriori suggerimenti?

La tua soluzione è di complessità attuale O(NQ) ossia per ogni query, devi scorrere l’Intero vettore di distanze.  
Con l’approcio in ricerca binaria, la complessità diventa O(QlogN), in quanto usando un vettore di distanze sortato (tralascio il conteggio del sorting O(NlogN) ) è possibile adottare questo tipo di ricerca.

Fammi sapere se ti serve qualche indizio su come implementarla.

GiackAloZ

Ps: personalmente preferisco non calcolare le distanze usando la radice quadrata, ma elevare al quadrato gli anni richiesti dalle query, perché è leggermente più ottimizzato 🙂 (ovviamente non dimenticare di usare dei long long int per memorizzare gli interi)

---

<div class="post-metadata">

**Author:** ![RayperZ](https://forum.olinfo.it/user_avatar/forum.olinfo.it/rayperz/32/358_2.png) [@RayperZ](https://forum.olinfo.it/u/RayperZ)\
**Post date:** [11 Settembre 2016, 7:59pm UTC](https://forum.olinfo.it/t/problema-anno-luce-ois-annoluce/3986/4 "2016-09-11T19:59:33Z")

</div>

Ti ringazio per il consiglio, avevo già iniziato a sviluppare una variante tramite il Binary search ma non ho avuto molto tempo per completarlo, ma mi fa piacere che avevo puntato nella strada giusta. Comunque avevo già provato ad elevare al quadrato le distanze delle query senza calcolare la radice quadrata, ma in 3 dei casi del Sub Task 7 dava output non corretto, quindi ho preferito perdere qualche millesimo in calcoli e guadagnare in precisione, spero che la variante con il binary search funzioni 🙂

---

<div class="post-metadata">

**Author:** ![GiackAloZ](https://forum.olinfo.it/user_avatar/forum.olinfo.it/giackaloz/32/594_2.png) [@GiackAloZ](https://forum.olinfo.it/u/GiackAloZ)\
**Post date:** [11 Settembre 2016, 8:03pm UTC](https://forum.olinfo.it/t/problema-anno-luce-ois-annoluce/3986/5 "2016-09-11T20:03:42Z")

</div>

Certamente 🙂  
Per qualsiasi cosa sono qui.

GiackAloZ