# Antique Street Lights (street lights) **URL:** \ **Category:** Aiuto\ **Created:** [13 Novembre 2016, 7:19pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166 "2016-11-13T19:19:01Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\ **Post date:** [13 Novembre 2016, 7:19pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166/1 "2016-11-13T19:19:01Z")
Ciao ragazzi,sto cercando di risolvere il problema streetlights, ma mi vengono in mente soltanto idee il cui tempo di esecuzione è troppo lungo. C’è qualche algoritmo già implementato che mi permette di ridurre notevolmente il tempo? Il problema dice di in un dato range quante lanterne devono essere accese. Avevo pensato se ci fosse qualcosa che si riferisce a problemi del genere. Grazie in anticipo ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [13 Novembre 2016, 8:44pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166/2 "2016-11-13T20:44:20Z")
Che idee hai per ora? ---
**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\ **Post date:** [13 Novembre 2016, 10:21pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166/3 "2016-11-13T22:21:53Z")
Controllo quante lanterne sono già accese in un determinato range, se le lanterne che sono accese sono minori di K (ovvero le lanterne che dovrebbero essere accese per ogni intervallo), allora setto L[M-1] = 1 (ovvero il valore più a destra nel vettore, in modo da accendere il minor numero possibile di lanterne), tutto questo per ogni intervallo di N ---
**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\ **Post date:** [13 Novembre 2016, 10:22pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166/4 "2016-11-13T22:22:21Z")
Sarebbe difficile e lungo da implementare ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [13 Novembre 2016, 10:26pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166/5 "2016-11-13T22:26:41Z")
No dai che non è così difficile da implementare 😄 Comunque quello che hai detto è corretto, però per ottenere il punteggio pieno ti serve qualche osservazione in più su come contare il numero di lanterne accese per i range “vicini” 😉 ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [14 Novembre 2016, 4:14pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166/6 "2016-11-14T16:14:47Z")
Prova a pensare a come ottimizzare questo algoritmo. Una volta che sai il numero di lanterne accese in un intervallo [i, i + M], come puoi sapere efficientemente quante sono accese nell’intervallo [i + 1, i + M + 1] ? ---
**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\ **Post date:** [15 Novembre 2016, 5:16pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166/7 "2016-11-15T17:16:07Z")
In realtà tra un intervallo ed un altro ci sono sempre degli elementi in comune che sarebbero tutti gli elementi dell’intervallo precedente tranne il suo primo elemento ---
**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:** [15 Novembre 2016, 10:08pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166/8 "2016-11-15T22:08:29Z")
Esatto, quindi una volta che conosci quante e quali luci sono accese in [i, i+M] ti è facile passare all’intervallo successivo concentrandoti solo sulla luce i e la luce i+M+1 🙂 Fatti qualche esempio su carta se non ti viene in mente subito 😛 ---
**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\ **Post date:** [17 Novembre 2016, 7:01pm UTC](https://forum.olinfo.it/t/antique-street-lights-street-lights/4166/9 "2016-11-17T19:01:41Z")
Grazie molte 😃