Zadanie

V Anurovej lekárničke pribudla mocná zbraň – všeliek všetkých otvorených zranení, všemocná alpa1. Tak sa mu osvedčila a zapáčila, že ampuliek alpy nosí so sebou vždy nekonečne veľa.

V sobotu sa, tak ako asi všetci, zabával na gladiátorských hrách. Tak veľmi sa mu tam páčilo, až sa rozhodol, že ani porazení gladiátori si nezaslúžia zomrieť. Preto hneď, ako dotlieskal, zoskočil z tribúny a vytiahol alpu, odhodlaný vyliečiť čo najviac bojovníkov.

Každý bojovník má niekoľko zranení, ktoré treba vyliečiť. Ak ostane bojovníkovi čo i len jedno zranenie nevyliečené, dostane infekciu a zomrie tak či tak. Na vyliečenie hocijakého zranenia stačí jedna kvapka alpy. Keďže alpa je balená v znovu neuzatvárateľných obaloch, Anura má teraz veľkú dilemu:

Chce vyliečiť čo najviac bojovníkov. Zároveň si však alpu veľmi váži2 a teda ak nejakú jej ampulku otvorí, chce ju celú do poslednej kvapky minúť (zužitkovať, nie premrhať vyhodením, alebo kvapnutím na už zahojenú ranu). Anura nemá to srdce prejsť počas liečenia okolo bojovníka a nevyliečiť ho. Teda ak niekde začne liečiť, bude postupne za radom liečiť všetkých bojovníkov, až k nejakému, od ktorého potom nenápadne odíde, snažiac sa nemyslieť na ostatných nevyliečených.

Úloha

V rade vedľa seba stojí \(n\) bojovníkov čakajúcich na vyliečenie. O každom bojovníkovi vieme jeho počet zranení \(z_i\), a teda aj počet kvapiek alpy potrebných na jeho zachránenie.

V každej ampulke je \(a\) kvapiek alpy. Zistite, aký najdlhší súvislý úsek bojovníkov môže Anura vyliečiť bez toho, aby čo i len kvapka alpy vyšla nazmar. Počet použitých ampuliek nás nezaujíma.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú medzerou oddelené prirodzené čísla \(n\) a \(a\) (\(1 \leq n, a \leq 100\,000\)) – počet zranených bojovníkov a počet kvapiek v jednej ampulke alpy. Nasleduje \(n\) riadkov, v \(i\)-tom z nich sa nachádza prirodzené číslo \(z_i\) (\(1 \leq z_i \leq 10^9\)) – počet zranení \(i\)-teho bojovníka zľava.

Formát výstupu

Na jediný riadok výstupu vypíšte maximálny počet bojovníkov, ktorých sa dá za daných podmienok vyliečiť.

Príklady

Input:

5 9
1
2
3
4
5

Output:

3

Troch vyliečime, ak začneme liečiť druhého bojovníka a skončíme predposledným.

Input:

6 2
3
4
1
2
4
3

Output:

5

Napríklad vyliečime prvých piatich.

Input:

5 22
9
1
6
2
3

Output:

0

Je nám to ľúto, ale nie sme ochotní premrhať čo i len kvapku.

  1. Ako každý vie, všeliek všetkých zatvorených je konská masť.↩

  2. Príprava alpy je veľmi náročná, ako súčasť procedúry musí alpa prejsť tráviacim traktom Púnskeho slona.↩

Čo vám napadne ako prvé po prečítaní úlohy? Pravdepodobne priamočiaro vyskúšať všetky možnosti. V tomto príklade to znamená vyskúšať liečiť všetky možné podúseky bojovníkov a pre každý overiť, či po ich vyliečení nezostanú v nejakej ampulke ešte nejaké kvapky. Pre každý možný začiatok a koniec úseku spočítame, koľko kvapiek alpy na tomto úseku minieme. Ak je tento počet deliteľný veľkosťou jednej alpulky \(a\), potom sa daný úsek dá vyliečiť bez plytvania alpou. Zapamätáme si a vypíšeme dĺžku najdlhšieho vyliečiteľného úseku. Easy!

Asi tušíte, že toto nebude vzorové riešenie. Hlavne kvôli svojej časovej zložitosti \(O(n^3)\) - máme totiž \(O(n^2)\) možných podúsekov a pre každý z nich potrebujeme sčítať všetky čísla v ňom (ktorých je \(O(n)\)).

Šikovnou implementáciou (alebo aj bezduchým použitím prefixových súm) sa dá časová zložitosť tohto algoritmu zlepšiť na \(O(n^2)\). To je však stále pomalé. Pre počet bojovníkov \(100\, 000\) už počítač jednoducho nebude stíhať.

Prefixové súčty

Predstavme si, že by sme si nad zraneniami bojovníkov spočítali prefixové súčty. Súčet čísel medzi \(i\)-tym a \(j\)-tym bojovníkom (vrátane) potom vieme vypočítať ako rozdiel \(j\)-teho a \(i-1\)-vého prefixového súčtu.

Ak je počet zranení na nejakom úseku deliteľný veľkosťou ampulky \(a\), potom musia mať príslušné dva prefixové súčty rovnaký zvyšok po delení \(a\) (lebo ich rozdiel je deliteľný \(a\)). Toto platí aj obrátene: ak majú dva prefixové súčty rovnaký zvyšok po delení \(a\), potom sa úsek bojovníkov medzi nimi dá vyliečiť bez plytvania alpou.

Aby sme teda našli najdlhší vyliečiteľný úsek bojovníkov, stačí nám nájsť dva najvzdialenejšie prefixové súčty, ktoré dávajú rovnaký zvyšok po delení \(a\).

Už to len nakódiť

Ak si všetky prefixové súčty vymodulujeme1 číslom \(a\), bude nám stačiť nájsť dve rovnaké čísla, ktoré sú čo najďalej od seba.

Toto sa dá implementovať napríklad tak, že budeme prechádzať pole s vymodulovanými prefixovými súčtami zľava doprava a v ďalšom poli o veľkosti \(a\) (pretože všetky čísla budú po upravení z tohto rozsahu!), si budeme pamätať prvý výskyt každého čísla. Akonáhle narazíme na číslo, ktoré už poznamenané máme, vieme, že sme objavili podúsek dlhý od prvého výskytu až po aktuálny index. Takto vieme vypočítať správny výsledok v jednom prechode a teda v časovej zložitosti \(O(n)\). Pamäťová zložitosť je \(O(a)\), teda závislá od veľkosti alpy.

INFINITY = 10 ** 9 + 47

n, MOD = [int(x) for x in input().split()]
A = [int(input()) for x in range(n)]

P = [INFINITY for x in range(MOD)]
P[0] = -1

s, mx = 0, 0
for i in range(n):
	s += A[i]
	s %= MOD

	if P[s] == INFINITY:
		P[s] = i
	else:
		mx = max(mx, i - P[s])

print(mx)

Poznámka na záver - mega veľké alpy

Dalo by sa to riešiť aj keby \(a\) bolo veľké?2 Áno ide to, jediná zmena by bola v pamätaní prvých výskytov. Nepoužili by sme pole, ale napr. hashmapu. Vďaka nej by čas stále ostal \(O(n)\) a pamäť by bola závislá už iba od počtu bojovníkov, tiež \(O(n)\).

  1. operácia modulo znamená zvyšok po delení↩

  2. Na Orave som naozaj videl v potravinách predávať litrovú alpu ;).↩

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.