Zadanie
September prišiel a farmár Jožo sa chystá na zber zeleniny zo svojho políčka. Na ňom má pekne v rade zasadených \(n\) zelenín rôznych (alebo aj rovnakých) druhov. Jožo si chce zvoliť jeden súvislý úsek poľa, z ktorého si zeleninu odloží doma; zvyškom prispeje do pohostenia pri najbližšom stretnutí dedinskej futbalovej ligy.
Okrem toho ale Jožo cez leto začal odoberať akýsi časopis o vyrovnanej strave. V ňom sa dočítal, že mu urobí dobre, ak nebude existovať jeden druh zeleniny, z ktorého by mal doma viac kusov ako z každého iného. (Tu sa ukazuje prečo sa Jožo nerozhodol proste zožrať všetko sám – mal by pocit že žije nezdravo.) Inak povedané, musia existovať aspoň dva druhy, z ktorých na jeho vybranom súvislom úseku poľa bude rovnako veľa kusov a zároveň zo žiadneho iného druhu na tom úseku nebude viac kusov.
Samozrejme, aj tak by si chcel Jožo nechať čo najviac zeleniny pre seba. Konkrétne chce, aby z každého z tých najčastejších druhov zeleniny mal doma aspoň \(k\) kusov. Povedzte mu, koľko najviac zeleniny si môže uskladniť doma, alebo aspoň že si nevie podľa svojich požiadaviek vybrať žiadny úsek poľa (a dofrasa aj s časopisom, všetky plány mu prekazil!).
Formát vstupu
Na prvom riadku sú čísla \(n\) a \(k\) – počet kusov zeleniny na poli a minimálny vyžadovaný počet kusov najčastejšieho druhu.
Na druhom riadku je \(n\) čísel \(a_1\) až \(a_n\) – typy jednotlivých kusov zeleniny v poradí, v ktorom rastú na poli. Platí \(1 \le a_i \le n\).
Formát výstupu
Vypíšte jeden riadok a na ňom jedno číslo – dĺžku najdlhšieho úseku poľa, ktorý je možné vybrať, alebo \(-1\) ak nie je možné vybrať žiadny úsek.
Hodnotenie
Je 6 sád vstupov. Platia v nich nasledujúce obmedzenia:
Sada | 1 | 2 | 3, 4 | 5 | 6 |
---|---|---|---|---|---|
\(1 \leq n \leq\) | \(60\) | \(5\,000\) | \(10\,000\) | \(50\,000\) | \(100\,000\) |
\(1 \leq n/k \leq\) | \(60\) | \(5\,000\) | \(20\) | \(100\) | \(200\) |
Príklad
Input:
5 1
2 2 3 1 2
Output:
3
Pole obsahuje napr. zemiak, zemiak, mrkvu, kareláb, zemiak. Optimálne je zobrať mrkvu, kareláb a jeden zo zemiakov ktoré s nimi susedia. Futbalový guľáš získal zvyšné dva zemiaky.
Chceme nájsť najdlhšiu súvislú podpostupnosť \(a_l, \ldots, a_r\) (v skrátenom značení \([l,r]\)), ktorej modus nie je unikátny – musia existovať aspoň dve čísla, ktoré sa v \([l,r]\) vyskytujú práve \(f \ge k\) krát, a žiadne číslo sa v nej nesmie vyskytovať viac ako \(f\)-krát.
Najprv sa zamyslime nad tým, čo nám dáva veľké \(k\). Existuje najviac \(\lfloor n/k \rfloor\) rôznych čísel, ktoré sa môžu vyskytnúť \(\ge k\) krát, lebo ak by ich bolo viac, postupnosť \(a\) by musela mať \(\ge (\lfloor n/k \rfloor + 1) k > n\) prvkov. Volajme ich časté. To nám pri hľadaní efektívneho algoritmu pomôže. Rovno si označme \(c_{v,p}\) počet výskytov častého čísla \(v\) medzi \(a_1, \ldots, a_p\) (teda \(c_{v,0} = 0\)); tieto prefixové sumy môžeme predpočítať v čase aj pamäti \(O(n^2/k)\).
Napr. \(O(n^2)\) riešenie je zjavné – zoberieme si pevné \(l\), začneme s \(r = n\), postupne ho zmenšujeme a pamätáme si v poli, koľko čísel sa v \([l,r]\) vyskytuje práve \(1,2,\ldots,n\) krát; vždy, keď zmenšíme \(r\), sa zmenší počet výskytov jedného čísla, teda vieme ľahko aktualizovať tieto hodnoty a aktuálnu hodnotu \(f\) (ktorá nemôže rásť), a nájdeme dokonca všetky podpostupnosti \([l,r]\) ktoré spĺňajú našu podmienku.
Pridajme teraz do tohto algoritmu podmienku, že sa zastavíme (a pokračujeme s ďalším \(l\)) hneď, keď nájdeme \(r\) pre ktoré je modus neunikátny. Vtedy stačí skontrolovať, či sa modus vyskytuje aspoň \(k\)-krát a aktualizovať odpoveď na úlohu. Tu prichádza kľúčové pozorovanie:
- Označme \(u\) najčastejšie číslo v \([l,n]\) (ak nie je jedinečné, potom niet čo riešiť).
- Pre každé \(i \neq u\) nájdime maximálne \(r\) také, že \(c_{i,r}-c_{i,l-1} = c_{u,r}-c_{u,l-1}\), a označme ho \(r_i\).
- Maximum všetkých \(r_i\) je práve hľadané najväčšie \(r\), pre ktoré má \([l,r]\) neunikátny modus.
Pointa je, že ak zoberieme maximálne \(r_m\) a príslušné číslo \(m\), potom čísla iné ako \(u, m\) môžeme odignorovať, lebo žiadne z nich sa nevyskytuje v \([l,r_m]\) častejšie ako \(u\). Dokážeme to sporom. Ak existuje \(j \neq u,m\) také, že \((c_{u,r_m}-c_{u,l-1}) - (c_{j,r_m}-c_{j,l-1}) < 0\), ale \((c_{u,N}-c_{u,l-1}) - (c_{j,N}-c_{j,l-1}) > 0\), potom musí existovať nejaké \(r > r_m\) také, že \(c_{u,r}-c_{u,l-1} = c_{j,r}-c_{j,l-1}\). Ak totiž posúvame \(r\) od \(n\) po \(r_m\) a sledujeme hodnotu výrazu \((c_{u,r}-c_{u,l-1}) - (c_{j,r}-c_{j,l-1})\), pri každom posunutí \(r\) o \(1\) sa výraz zmení maximálne o \(1\), teda musíme medzi záporným a kladným číslom natrafiť na nulu. Potom by ale bolo \(r_j \ge r\), teda väčšie ako \(r_m\), čo je spor s maximálnosťou \(r_m\).
Na prvý pohľad toto pozorovanie nevyzerá až tak užitočne, ale hovorí nám, že \(u\) bude modus aj pre podpostupnosť \([l,r_m]\) a že hodnoty vo vstupnom poli sú dosť nezávislé – pre dané \(l\) (a teda \(u\)) sa stačí pozrieť na všetky dvojice \((m,r)\), vybrať tie pre ktoré platí \(c_{m,r}-c_{m,l-1} = c_{u,r}-c_{u,l-1}\), a z nich vybrať maximálne \(r\). Prepíšme si túto rovnicu na \[c_{u,r}-c_{m,r} = c_{u,l-1}-c_{m,l-1} \,.\]
Pre každú dvojicu \((u,m)\) teda môžeme spraviť toto: zoskupíme všetky indexy \(i\) podľa hodnoty \(c_{u,i}-c_{m,i}\) v čase \(O(n)\), pre každú hodnotu sa pozrieme na všetky jej indexy \(i=l-1\), pre ktoré je \(u\) modusom \([l,n]\), a vieme pre ne maximálny index \(i=r\), ktorý dá rovnakú hodnotu. Takto pre každé \(l\) spočítame maximálne \(r\), pre ktoré má \([l,r]\) neunikátny modus, alebo zistíme, že žiadne také \(r\) neexistuje. Nakoniec pre každý z týchto \(O(n)\) kandidátov \([l,r]\) skontrolujeme, či sa modus \([l,n]\) (ktorý je aj modus \([l,r]\)) vyskytuje v \([l,r]\) aspoň \(k\) krát a spočítame odpoveď. To funguje v čase \(O(n^3/k^2)\).
Ešte to môžeme zrýchliť. Samozrejme, možných trojíc \((u,m,i=l-1)\) je len \(O(n^2/k)\), lebo \(l\) jednoznačne určuje \(u\). Pre \((u,m,i=r)\) zasa využime nápad s posúvaním \(r\). Na začiatku (\(r=n\)) je \(u\) unikátny modus a bude to tak až kým nenarazíme na \(r=r_m\). Keďže posunutím \(r\) o \(1\) sa môže zmeniť len počet výskytov jedného čísla, pri posunutí z \(r=r_m+1\) na \(r=r_m\) musí to číslo byť \(u\), teda chceme \(a_{r+1} = u\). Vidíme, že celkovo stačí uvažovať len \(O(n^2/k)\) trojíc \((u,m,i)\), a rovnaká je aj časová náročnosť. Pamäťová náročnosť je stále \(O(n^2/k)\).
(Pre zaujímavosť: rozšíriť riešenie úlohy na ľubovoľné \(k\) je pomerne ľahké. Pre pevné \(f < \sqrt{n}\) sa posúvame po poli, pamätáme si pre každú hodnotu jej nasledujúcich \(f+1\) výskytov a na základe najbližších z \(f\)-tých a \(f+1\)-vých výskytov určíme najväčšiu súvislú podpostupnosť s neunikátnym modusom. Pri posunutí o jeden prvok sa veľa nemení, takže z odpovede pre \(k+1\) vieme vypočítať odpoveď pre \(k\) v čase \(O(n)\).)
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ť.