2. Láska kvitne v júni vzorové riešenie

5 5
1 2 3 4 5

8

6 4
1 2 3 2 3 2

5

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)