Zadanie

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu conditions_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Paulinke na psmolarova@gmail.com

Kde bolo tam bolo, žili si Etka a Jemo. A žili by si šťastne až kým by nepomreli, ak by nenastal ten obávaný deň. Výročie. A Jemo naň, ako inak, zabudol. Spomenul si naň až v poslednú možnú chvíľu a rýchlo trielil do obchodu, kde úspešne kúpil pestrofarebný korálkový náhrdelník a hrdý na svoj počin zazvonil Etke pri dverách.

Lenže, beda prebeda! Jemo vrámci tohto stresujúceho nákupu zabudal na jednu mimoriadne podstatnú vec. Etka nie je veľký fanúšik príliš farebných vecí. Konkrétne, vyžaduje aby všetky jej veci mali nanajvýš dve farby.

Jemo teraz stojí pred dverami, Etka sa blíži a on potrebuje svoju chybu rýchlo napraviť. Najjednoduchšie bude vybrať časť náhrdelníka, ktorá má najviac dve farby, zvyšok odstrihnúť a vybraný úsek zviazať dokopy a podarovať Etke krásny dvojfarebný náhrdelník.

Úloha

Pomôžte Jemovi opraviť náhrdelník skôr ako Etka otvorí dvere.

Náhrdelník sa skladá z farebných koráliek. Na vstupe dostane popis farieb jednotlivých koráliek tak, ako sú za sebou poukladané v náhrdelníku. Dajte si pozor, že po poslednej korálke nasleduje hneď korálka prvá.

Vašou úlohou je nájsť najdlhší1 súvislý úsek náhrdelníka, ktorý obsahuje najviac korálky dvoch farieb.

Formát vstupu

V prvom riadku je číslo \(1 \leq n \leq 100\,000\) udávajúce počet koráliek na náhrdelníku.

V druhom riadku je \(n\) medzerami oddelených čísel \(c_1\)\(c_n\) (\(1 \leq c_i \leq 10^9\)) – farby koráliek v náhrdelníku.

Formát výstupu

Na prvý riadok výstupu vypíšte dĺžku najdlhšieho náhrdelníku ktorý vie Jemo vytvoriť.

Na druhý riadok vypíšte indexy prvej a poslednej korálky ktoré budú tvoriť nový náhrdelník. Dajte si pozor, že náhrdelník je kruhový.

V prípade, že je riešení viac, vypíšte ľubovoľné z nich.

Hodnotenie

Vaše riešenie bude otestované na \(5\) sadách vstupov. Za vyriešenie každej sady získate 3 body. Tieto sady sa líšia veľkosťou vstupných údajov.

Číslo sady 1 2 3 4 5
maximálne \(n\) \(100\) \(1\,000\) \(1\,000\) $100,000 \(100\,000\)
Ďalšie obmedzenia \(1 \leq c_i \leq 100\) \(1 \leq c_i \leq 3\) \(1 \leq c_i \leq 1\,000\) \(1 \leq c_i \leq 3\) \(1 \leq c_i \leq 10^9\)

Príklady

Input:

7
3 1 2 1 2 2 3

Output:

5
2 6

V tomto prípade je najlepší náhrdelník 1-2-1-2-2. Tento vstup by sa mohol nachádzať aj v sadách 2 a 4.

Input:

6
1 2 5 3 1 2

Output:

4
5 2

Všimnite si, že vo výstupe je číslo prvej korálky väčšie ako číslo poslednej. To je v poriadku, pretože náhrdelník je cyklický (posledná korálka je spojená s prvou). Chceme vybrať korálky 1-2-1-2.

Input:

5
3 9 9 3 9

Output:

5
4 3

V tomto prípade je aj pôvodný náhrdelník vyhovujúci. Správne odpovede by boli aj 1 5 alebo 5 4.

Input:

8
4 5 1 4 6 5 1 2

Output:

2
1 2

Tu sa žiaľ nedá spraviť nič lepšie ako použiť niektoré dve susedné korálky. Všimnime si, že nemôžeme vytvoriť náhrdelník 1-4-1, pretože úsek musí byť na pôvodnom náhrdelníku súvislý.


  1. Bolo by fajn keby si ho Etka zvládla pretiahnuť cez hlavu.

Riešenie za 3 body

Poďme sa pustiť do riešenia. Pre každý začiatok náhrdelníku máme \(n\) možných koncov, kde môže končiť. Napríklad pre náhrdelník 3 1 2 1 3 2 a začiatok na tretej korálke (korálke 2) chceme postupne vyskúšať náhrdelníky (2), (2 1), (2 1 3), (2 1 3 2), (2 1 3 2 3), (2 1 3 2 3) a ( 2 1 3 2 3 1). Ako vieme overiť, či náhrdelník spĺňa zadanú vlastnosť? Môžeme si pamätať, ktoré farby korálok sa v ňom nachádzajú. Dokonca nám postačia dve farby, pretože ak by sme mali nájsť tretiu farbu, vieme, že daný úsek nebude vhodný.

Pre každý možný náhrdelník, ktorých je \(n^2\) (pre každý začiatok mám \(n\) koncov) prejdeme týmto náhrdelníkom a skontrolujeme, či obsahuje najviac dve farby. Na pamätanie farieb použijeme dve premenné, v ktorých si na začiatku budeme pamätať hodnotu -1 značiacu, že sme ešte nevideli obe farby.

Takéto riešenie má časovú zložitosť \(O(n^3)\)

n = int(input())
koralky = list(map(int, input().split()))
koralky += koralky; # skopirujeme si pole za seba, aby sa nam jednoduchsie implementovalo to, ze koralky su v kruhu

najlepsia = 0
kde = 0
for i in range(n):
    for j in range(n):
        prva, druha = -1, -1
        moze = True
        for l in range(j + 1):
            if prva == -1: # toto je prva koralka
                prva = koralky[i + l]
            elif prva != koralky[i + l] and druha == -1:
                druha = koralky[i + l]
            elif prva != koralky[i + l] and druha != koralky[i + l]: # mame privela farieb
                moze = False
        if moze and najlepsia < j + 1:
            najlepsia = j + 1
            kde = i
            
print(najlepsia)
print(kde + 1, n if (kde + najlepsia) % n == 0 else ((kde + najlepsia) % n))

Zlepšenie na 9 bodov

Všimnime si, že ak pre daný začiatok nefunguje úsek s dĺžkou \(k\), nebude preň fungovať ani žiaden dlhší úsek. Napríklad v príklade vyššie vidíme, že už úsek (2 1 3) obsahuje priveľa farieb. Je preto prirodzené, že keď tento úsek predĺžime o ďalšie korálky, počet farieb sa nezníži.

Na druhej strane si však môžeme uvedomiť, že ak sme pred chvíľou spracovali úsek dlhý \(k\), tak pri spracovávaní úseku dĺžky \(k+1\) nemusíme začínať odznova. Stačí pridať len tú jednu korálku navyše, skontrolovať či má jednu z dvoch farieb v úseku dĺžky \(k\), poprípade ak bola v úseku dĺžky \(k\) len jedna farba poznačiť si farbu korálky \(k+1\) (ak je náhodou rôzna od tých predtým).

Toto riešenie je rýchlejšie, pretože pre každý začiatok nám stačí iba raz prejsť celým náhdrelníkom. Pri tomto prechode postupne zisťujeme vhodosť každého konca a to vždy iba pridaním jednej korálky. Časová zložitosť je preto \(O(n^2)\).

n = int(input())
koralky = list(map(int, input().split()))
koralky += koralky; # skopirujeme si pole za seba, aby sa nam jednoduchsie implementovalo to, ze koralky su v kruhu

najlepsia = 0
kde = 0
for i in range(n):
    prva, druha = -1, -1
    for j in range(n):
        if prva == -1:
            prva = koralky[i + j]
        elif prva != koralky[i + j] and druha == -1:
            druha = koralky[i + j]
        elif prva != koralky[i + j] and druha != koralky[i + j]: # mame privela farieb
            if najlepsia < j:
                najlepsia = j
                kde = i
            break
        if j == n - 1:
            najlepsia = n
            kde = i
            
print(najlepsia)
print(kde + 1, n if (kde + najlepsia) % n == 0 else ((kde + najlepsia) % n))

Vzorové riešenie

V predchádzajúcom riešení sme využili fakt, že úseky s rovnakým začiatkom a takmer rovnakým koncom sa líšia minimálne. Dokonca ak je rozdiel ich dĺžok jedna, tak sa líšia iba pridaním jedinej guličky. Toto pozorovanie je však symetrické a rovanko dobre vieme povedať, že úseky s rovnakým koncom a začiatkom líšiacim sa o jedna sú rozdielne iba v začiatočnej guličke.

Toto pozorovanie teraz využijeme. Zoberme si nejaký fixný začiatok a postupom vyššie nájdime najdlhší vhodný náhrdelník s týmto začiatkom, nech má dĺžku \(l\). Keďže dlhší náhrdelník neexistuje, musíme sa posunúť na nový začiatok. Uvedomme si však, že nemusíme s koncom začínať opäť od začiatku. Aktuálny koniec nám totiž určite vyhovuje. Na pozíciách od 0 po \(l\) boli najviac dve rôznofarebné guličky. Z toho ale plynie, že aj na pozíciách 1 až \(l\) budú najviac dve farby koráliek. A možno dokonca menej, ak bola na pozícii 0 jediná korálka príslušnej farby v úseku. Po posunutí začiatku preto budeme len ďalej pokračovať v hľadaní konca tohto úseku bez toho, aby sme začínali odznova.

Ostáva nám toto riešenie implementovať. Hlavný rozdiel oproti predchádzajúcim dvom riešeniam je, že prestaneme pouzívať premenné prva a druha. Miesto nich budeme mať dictionary (slovník resp. map pre C++ programátorov). V nej si budeme pamätať všetky korálky, ktoré sú aktuálne v nami vybranom úseku. Toto potrebujeme spraviť preto, lebo korálky už nebude iba pridávať, ale aj odoberať pri posúvaní začiatku. Potrebujeme teda vedieť zistiť, keď odoberieme poslednú korálku nejakej farby, aby sme vedeli, že môžeme pridávať nové korálky.

V našom slovníku si budeme pre každú farbu korálok pamätať, koľko daných korálok sa v našom úseku nachádza. Naviac, ak z danej farby nie je v úseku žiadna korálka, túto hodnotu v slovníku nebudeme mať. Vďaka tomu sa budeme môcť pýtať na veľkosť tohto slovníka (či je menší ako 3), teda počet farieb v aktuálnom úseku. Pri každom posune začiatku odstránime začiatočnú korálku zo slovníka a následne budeme vo while cykle zisťovať, nakoľko vieme náš úsek predĺžiť. Pri predlžovaní budeme samozrejme korálky do slovníka pridávať.

Aká je časová zložitosť takéhoto riešenia? Predstavme si dva indexy – začiatok a koniec úseku – ktoré v našom algoritme posúvame. Index začiatku posunieme práve \(n\) krát, raz pre každý začiatok. A index konca nemôže predbehnúť index začiatka (nezabúdajme, že sme na kruhu), preto ho môžeme posunúť dokopy najviac \(2n\) krát. To vedie k celkovej zložitosti \(O(n)\). Všimnite si ešte v riešení, že namiesto toho, aby sme pracovali s kruhovým náhrdelníkom, tak si náhrdelník nakopírujeme dvakrát za seba. Takéto predĺženie sa chová podobne ako keby sme boli na kruhu, akurát sa nám s tým lepšie pracuje.

n = int(input())

koralky = list(map(int, input().split()))
koralky += koralky

maxi = 1
od = -1
it = -1
aktualne = {}
for i in range(n):
    if i > 0:
        aktualne[koralky[i - 1]] -= 1;
        if aktualne[koralky[i - 1]] < 1:
            aktualne.pop(koralky[i - 1]);
    while it < i + n and len(aktualne) < 3:
        it += 1
        if not koralky[it] in aktualne:
            aktualne[koralky[it]] = 0
        aktualne[koralky[it]] += 1
    maxi = max(maxi, it - i)
    if maxi == it - i:
        od = i

print(maxi)
print(od + 1, n if (od + maxi) % n == 0 else ((od + maxi) % 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ť.