8. Akýsi časopis vzorové riešenie

5 1
2 2 3 1 2

3

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)\).)