5. Korálkový náhrdelník vzorové riešenie

7
3 1 2 1 2 2 3

5
2 6

6
1 2 5 3 1 2

4
5 2

5
3 9 9 3 9

5
4 3

8
4 5 1 4 6 5 1 2

2
1 2

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