Zadanie

Záhradník rád záhradníčil, pestoval ovocie a zeleninu a užíval si pokojný život. Táto idylka však skončila, keď jedného dňa na Záhradníkovu hlavu vyskočil Krtko a začal Záhradníka ovládať. Záhradník sa už viac nestaral o baklažány, kaleráby, jablká, ananásy či petržleny a namiesto toho kopal krtince a organizoval sústredenia. A hoci už nemal viac v živote pokoja, aspoň robil radosť mnohým deťom, ktoré sa na sústredenia veľmi tešili.

Ani táto radosť však netrvala dlho, lebo Záhradníkove schopnosti sa rozhodla využiť aj hlavná kubrická ploštica. Tej bolo smutno, že ploštice kvôli svojej zlej reputácii medzi ľuďmi klesajú na počtoch a rozhodla sa proti tomuto trendu bojovať a pre ostatné ploštice zorganizovať speed dating. Vyskočila na hlavu Krtkovi, ktorý sedel na hlave Záhradníkovi a začala ho ovládať, aby jej speed dating pripravil.

Speed dating ploštíc prebieha následovne. Máme \(n\) ploštíc a každá dvojica z nich pôjde na rande na večeru. Večerať budú účastníkov sústredenia a každá ploštica si na svojho účastníka počká v jednej z dvoch postelí na izbe. No každá ploštica má rada iný typ posteľných obliečok a chce byť iba v posteli s tými obliečkami. Tie bude Záhradník ovládaný Krtkom ovladaný kubrickou plošticou medzi jednotlivými rande v prípade potreby prezliekať. Toto sťažuje fakt, že postele v izbe sú rôzne veľké, čo plošticiam síce neprekáža, no znamená to, že treba kúpiť iný rozmer obliečky na jednu posteľ, a iný na druhú.

Kubrická ploštica potrebuje nakázať Krtkovi, nech nakáže Záhradníkovi koľko kusov obliečok treba nakúpiť, nech každá dvojica z jej \(n\) ploštíc môže spolu ísť na rande.

Úloha

Pre daný počet ploštíc a ich preferencie zistite minimálny počet obliečok, ktoré treba nakúpiť na sústredenie, aby každá dvojica ploštíc mohla ísť spolu na rande, každá do inej postele s jej obľúbeným typom obliečok. Ak na speed dating príde iba jedna ploštica, pôjde sa navečerať osamote (a spoznať sa sama so sebou).

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) a \(k\) (\(1 \leq n,k \leq 2 \cdot 10^5\)) udávajúce počet ploštíc a počet rôznych typov obliečok.

V druhom riadku následuje \(n\) čísel, \(p_1, p_2, \cdots, p_n\) kde \(p_i\) je preferovaný typ obliečok \(i\)-tej ploštice.

Sú dve sady. Pre prvú sadu platí, že \(p_i\) sa rovná \(i\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo - počet kusov obliečok, ktoré treba nakúpiť.

Príklady

Input:

5 5
1 2 3 4 5

Output:

8

Aj keď každú obliečku chce iba jedna ploštica, aj tak musíme z niektorých typov kúpiť dva kusy. Keby sme napríklad kúpili obliečku typu 4 a 5 len v rozmeroch prvej postele, keď pôjdu ploštice 4 a 5 na rande, nebudeme vedieť obliecť druhú posteľ tak, aby ju niektorá z nich chcela. Rozmyslite si, ktoré obliečky stačí kúpiť pre obe postele, aby nám ich stačilo dokopy 8 kusov.

Input:

6 4
1 2 3 2 3 2

Output:

5

Záhradník potrebuje kúpiť obliečky typu 2 a 3 pre obe postele, a obliečku typu 1 len pre jeden rozmer. Bez ohľadu na to, ktoré dve ploštice pôjdu na rande, budeme každej vedieť obliecť posteľ do jej obľúbenej obliečky.

Zádrhel tejto úlohy spočíva v tom, že dve postele na izbe potrebujú obliečky rôznych veľkostí. To znamená, že v niektorých prípadoch budeme musieť kúpiť dva kusy obliečok rovnakého typu (ale rôzných veľkostí). Keď sa rozhodujeme, z ktorých typov obliečok potrebujeme dva kusy, potrebujeme zvážiť niekoľko prípadov.

Každá ploštica preferuje iný typ obliečok

Tento prípad zodpovedá prvej sade, kde platí, že preferencia ploštice \(p_i\) sa rovná \(i\).

V tomto prípade, keď \(n\) sa rovná 1, vieme, že ploštica pôjde na rande sama a je jedno, akú veľkosť obliečok kúpime, stačiť bude jeden kus.

Ak \(n\) sa rovná 2, tak vieme, že každá z ploštíc pôjde na rande presne raz, a to naraz s druhou plošticou z páru. Tým pádom pre každú plošticu potrebujeme presne jedny obliečky (rôznej veľkosti) a výsledok, ktorý hľadáme je 2.

Komplikovanejšie to začína byť v prípade, že máme viac, ako dve ploštice. Bez ujmy na všeobecnosti si môžeme povedať, že prvá z \(n\) ploštíc sa bude vždy nachádzať na posteli číslo 1, a tak pre ňu zaobstaráme iba jednu veľkosť obliečok. Pri druhej ploštici si podobne môžeme povedať, že sa vždy bude nachádzať na posteli číslo 2, a tak pre ňu stačí tiež zaobstarať iba jednu veľkosť obliečok. Zatiaľ nám v tom nič nebráni, keďže tieto ploštice vedia spokojne ísť spolu na rande. No akonáhle by sme chceli povedať, že tretia ploštica bude vždy na posteli číslo 1, zistíme, že nebude vedieť ísť na rande s prvou plošticou. Takisto, ak povieme, že bude vždy na posteli číslo 2, nebude môcť ísť na rande s druhou plošticou.

Vieme teda povedať, že pre tretiu plošticu musíme kúpiť obe veľkosti obliečok, aby mohla ísť na rande s prvou aj s druhou plošticou. Toto platí aj pre všetky zvyšné ploštice. Tým pádom máme 2 ploštice (prvú a druhú), pre ktoré kúpime jeden kus obliečok a \(n-2\) ploštíc, pre ktoré kupime dve obliečky. Celkový počet obliečok, ktorý kúpime je teda \(2 * (n - 2) + 2\), po úprave \(2n - 2\).

n, _ = [int(x) for x in input().split()]

if n <= 2:
    print(n)
else:
    print(2*n-2)

Ploštice môžu preferovať rovnaký typ obliečok

V druhej sade sa stretneme so situáciou, kde rôzne ploštice môžu preferovať rovnaký typ obliečok. Tu je dôležité si uvedomiť, že ak existujú aspoň dve ploštice, ktoré majú rady rovnaký typ, potrebujeme presne dva kusy tohoto typu, aby dve ploštice s touto preferenciou mohli ísť spolu na rande. Taktiež nepotrebujeme viac ako 2 kusy, každý na jednu posteľ, keďže jeden kus obliečok môže byť použitý viackrát.

Poďme sa pozrieť len na tie typy obliečok, ktoré sú preferované len jednou plošticou. Zmenila sa nám situácia tým, že sme niektoré obliečky rovno kúpili dva krát? Nie, keďže bezohľadu na to, ako pokúpime tie obliečky, ktoré preferuje len jedna ploštica, budú vedieť ísť randiť s plošticami, ktorým sme práve kúpili obliečky na obe postele.

Obliečky, ktoré preferuje práve jedna ploštica, teda môžeme ponakupovať úplne nezávisle a spravíme to tak, ako sme si vysvetlili v predošlej sekcií. Čiže z týchto obliečok môžeme zobrať maximálne dva rôzne typy, z ktorých nám stačí kúpiť jeden kus a pre zvyšné typy platí, že musíme kúpiť dva kusy.

Dokázali sme si, že opäť môžeme mať maximálne dva typy obliečok, z ktorých kúpime jeden kus. A podmienkou je, že tieto typy musia byť preferované len jendou plošticou. Otázkou je, ako zistíme, či takéto typy existujú a koľko ich je.

Potrebujeme použiť dátovú štruktúru, ktorá nám pre každý typ obliečok povie, koľko ploštíc danú obliečku preferuje.

Jednou takouto dátovou štruktúrou je vector (v pythone list) veľkosti \(k\), v ktorom každá pozícia prezentuje typ obliečky a hodnota na danej pozícii reprezentuje počet ploštíc, ktoré danú obliečku preferujú. Pri načítavaní sa pozrieme na preferenciu konkrétnej ploštice a navýšime zodpovedajúcu hodnotu vo vectore o 1. Na konci celý vector prejdeme a v osobitnej premennej \(raz\) si zapamätáme, koľko hodnôt vo vectore sa rovnalo 1 a v premennej \(viac\) koľko ich bolo aspoň 2.

Každú z \(viac\) typov obliečky budeme musieť kúpiť dva krát a obliečok z \(raz\) typov kúpime podľa predošlého vzorca: \(raz\) kusov, ak sú najviac 2, inak \(2raz - 2\).

Časová zložitosť načítania vstupu a prejdenia listu je \(O(n + ǩ)\) a pamäťová je \(O(k)\), keďže si vytvárame pole veľkosti \(k\).

n,k = [int(x) for x in input().split()]

pocty = [0 for _ in range(k)]

preferencie = input().split()
for x in preferencie:
    pocty[int(x)-1] += 1

raz, viac = 0, 0
for pocet in pocty:
    if pocet == 1:
        raz += 1
    elif pocet >= 2:
        viac += 1

pre_jednotlivcov = raz if raz <= 2 else 2*raz-2

print(viac*2 + pre_jednotlivcov) 

Použitie mapy

Riešenie, ktoré sme si predstavili, môže byť ešte efektívnejšie, ak použijeme dátovú štruktúru map (dictionary v pythone). Táto štruktúra nám dovoľuje držať v pamäti a prechádzať hodnoty zodpovedajúce len tým typom obliečok, čo sú preferované aspoň jednou plošticou. Ak napríklad máme veľké \(k\) (\(10^9\)), ale všetky ploštice preferujú ten istý typ obliečok, v mape si budeme pamätať údaje práve o tomto jednom type.

Časová a pamäťová zložitosť sa nám teda zhodí na \(O(n)\). Nebolo nám to však pri daných obmedzeniach treba.

from collections import Counter

n,m = [int(x) for x in input().split()]

cnt = Counter(input().split())

one, more_than_one = 0, 0
for c in cnt.values():
    if c == 1:
        one += 1
    else:
        more_than_one += 1

for_ones = one if one<=2 else 2*one-2

print(more_than_one*2 + for_ones) 

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ť.