Kako se resava zadatak parni podnizovi sa sio 2013?
Jedna opcija (koja je, koliko vidim, ono sto su svi takmicari koji imaju 100 poena radili) je:
Za svaki prefiks A_0, A_1, \dots, A_i cemo pronaci brojeve koji se u njemu pojavljuju neparan broj puta (sto mozemo lako odrzavati ako znamo ovaj skup za i-1). Izracunamo neku hes funkciju ovog skupa i sacuvamo je kao H_i. Jedna opcija za hes je, na primer (gde je S_i skup brojeva koji se pojavljuju neparno puta, p mali prost broj, a M veliki prost modul):
H_i = (\sum_{x \in S_i} p^x) \text{ mod } M
Sada znamo da (pod uslovom da nema kolizija u hes funkciji) da ako H_i = H_j, onda je parnost pojavljivanja svih brojeva u prvih i i u prvih j ista, tako da se svi brojevi pojavljuju jednako puta u H_{i+1}, \dots, H_j. Dakle, da bi izracunali koliko ukupno podnizova sa ovom osobinom postoji, dovoljno je da za svaku vrednost u H prebrojimo koliko se puta pojavljuje (oznacimo ovo sa c) i na resenje dodamo c (c-1) / 2.
Ostaje jos jedno pitanje: da li je verovatno da necemo imati kolizije, tj. koliko velik modul N nam je potreban da do njih verovatno ne dodje? Racunamo najvise N \leq 353535 heseva. Za datu vrednost M, ako su hesevi uniformno distribuirani, broj razlicitih heseva koje mozemo izracunati pre nego sto je verovatnoca kolizije 50\% je otprilike \sqrt M (teorija), tako da nam treba M > N^2 \approx 1.24 \cdot 10^{11}. Dakle, nije dovoljno da imamo jedan 32-bitni hes (M ne moze biti 64-bitno jer u suprotnom dolazi do overflow-a u mnozenju), vec je potrebno da cuvamo dve vrednosti H_i i H_i', racunate sa razlicitim parametrima (p,M), i da sortiramo parove umesto pojedinacnih heseva.