In questo problema abbiamo una stringa $ S = S_{1} S_{2} \ldots S_{n} $ di zeri e uni ed un intero k > 1. Chiamiamo punti di "accumulazione" quegli elementi $ S_{j} $ della stringa tali che: 1. $ S_{j} = 1 $ e 2. esiste un certo i < j tale che in $ S_{i} S_{i+1} \ldots S_{j-1} $ vi sono almeno (j-i)/k zeri.
Ci sono due punti:
a) Descrivere un algoritmo semplice che in tempo O(n) calcola tutti gli indici j per i quali $ S_{j} $ è un punto di "accumulazione"
b) Derivare dal punto a) una dimostrazione del fatto che il numero di punti di "accumulazione" è al piu' (k-1)n / k dove n è la dimensione della stringa
punti di "accumulazione"
Se un elemento $ S_{j} $ è un uno, ma non è un punto di accumulazione, si può eseguire l'algoritmo sul resto della stringa senza preoccuparsi della stringa da $ S_{1} $ a $ S_{j} $, perchè, per definizione, non esiste nessun indice i compreso tra 1 a j tale che ci siano almeno (j-i)/k zeri e quindi un eventuale punto di accumulazione successivo all'indice j sarà tale grazie ad una concentrazione di zeri successiva.
Se un elemento $ S_{j} $ è un punto di accumulazione, vuol dire che esiste un indice i tale che ci siano almeno (j-i)/k zeri; se ci sono più zeri del necessario, c'è una specie di "credito". Poichè il credito si può "accumulare", andrebbe tenuto in conto l'indice che permette di conservare più "credito".
Ecco quindi l'algoritmo:
Ad osservare l'algoritmo, sembra che il modo migliore per avere più punti di accumulazione sia di "accumulare" il credito e poi spenderlo perfettamente, ripetendo queste operazioni fino alla fine della stringa; per esempio, si può ripetere fino all'indice n la sottostringa 0 seguita da k uni. Il numero massimo di punti di accumulazione sarà (k * n )/(k + 1), che ad essere precisi non è (k-1)n / k, ma probabilmente ci sarà da qualche parte un < al posto di un <= o cosette del genere.
Se un elemento $ S_{j} $ è un punto di accumulazione, vuol dire che esiste un indice i tale che ci siano almeno (j-i)/k zeri; se ci sono più zeri del necessario, c'è una specie di "credito". Poichè il credito si può "accumulare", andrebbe tenuto in conto l'indice che permette di conservare più "credito".
Ecco quindi l'algoritmo:
Codice: Seleziona tutto
while (i minore di n) (
accumulazione[i] = false
i = i + 1
)
i = 0
while (i minore di n) (
if (S[i] = 0) (
zeri = zeri + 1 //accumula "credito"
) else (
uni = uni + 1
if (zeri * k >= uni) (
accumulazione[i] = true
) else (
// non è un punto di accumulazione, si può fare tabula rasa
uni = 0
zeri = 0
)
)
i = i + 1
)
Trovato l'errore. Invece di
va messo
In base ai ragionamenti del precedente messaggio, si ottiene come numero massimo di punti di accumulazione (k-1)n / k.
Codice: Seleziona tutto
if (zeri * k >= uni)
Codice: Seleziona tutto
if (zeri * (k - 1) >= uni)