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
Che idee hai per ora?
1 Mi Piace
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
Sarebbe difficile e lungo da implementare
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” 
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] ?
1 Mi Piace
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
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 
Grazie molte 
1 Mi Piace