Zadanie

V krajine Absurdistan prekvitá filmový priemysel. A ako sa patrí, každý rok sa koná veľká slávnostná ceremónia, kde sa zídu všetci herci z krajiny a tí najlepší dostanú ceny. Ceny sa udeľujú z absurdného množstva kategórii ako “najžiarivejší úsmev”, “najtragickejší monológ” alebo “najdivokejší výkrik”. Môže to dopadnúť všelijako. Už sa doteraz párkrát stalo, že kategórii bolo viac ako hercov a každému hercovi sa ušla aspoň jedna cena, ale raz aj že jediná ultra-populárna herečka vyhrala úplne všetky kategórie.

Ceremónia prebieha tak, že zaradom v každej kategórii moderátor prečíta meno víťazného herca, potrasie mu rukou, odovzdá mu zlatú sošku a všetci zatlieskajú. Moderátor samozrejme tiež musí byť nejaký herec, lebo diváci majú radi keď je to známa tvár a nie nejaký neznámy človek zo zákulisia. Každá kategória má práve jedného moderátora a jedného víťaza. Medzi kategóriami sa moderátori môžu striedať.

Úloha

Ste členmi organizačného výboru tohtoročnej ceremónie. Zoznam a poradie kategórii už je pevne daný a porota už vybrala všetkých víťazov. Vašou úlohou je už len naplánovať, kto bude kedy robiť moderátora. Na to máte dve dôležité podmienky.

  1. V žiadnej kategórii nesmie byť moderátor a víťaz ten istý človek. Nevyzeralo by dobre, keby odovzdával sošku sám sebe, diváci by si mysleli že je to nejaký podvod. Ktorýkoľvek iný herec môže kategóriu moderovať, len nie víťaz.

  2. Je lepšie aby sa moderátori nestriedali príliš často. Lebo vždy keď sa striedajú, ten starý bude strašne dlho rečniť že prichádza nový moderátor, a ten nový moderátor mu bude celú večnosť ďakovať za privítanie. A to dokonca aj keby ten nový už niečo predtým moderoval. Čas sú peniaze a divákov to hrozne nudí, takže sa snažte aby viaceré kategórie za sebou moderoval ten istý herec.

Nemusíte vypísať detaily kto presne bude kedy moderovať, stačí keď vypíšete koľko najmenej striedaní moderátorov musí nastať. Prvú kategóriu môže moderovať ľubovoľný herec (okrem jej víťaza), jeho nastúpenie sa neráta ako striedanie.

Formát vstupu

Na prvom riadku je číslo \(t\) - počet testovacích vstupov (rôznych ceremónii). Každú ceremóniu vyhodnoťte zvlášť.

V rámci každej ceremónie je na prvom riadku číslo \(h\) - počet hercov. Na ďalších \(h\) riadkoch sú mená jednotlivých hercov v nejakom neurčitom poradí. Mená majú maximálne 100 znakov a môžu obsahovať ľubovoľné normálne znaky (viditeľné ASCII a medzery). Žiadni dvaja herci sa nevolajú rovnako.

Na ďalšom riadku je číslo \(k\) - počet kategórii. Na ďalších \(k\) riadkoch sú mená jednotlivých víťazov (v prvej, druhej, …, \(k\)-tej vyhlásenej kategórii). Každé meno víťaza je naozaj niekto z tých \(h\) hercov čo sa zúčastnili tejto ceremónie.

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2
\(1 \leq t \leq\) \(20\) \(20\)
\(2 \leq h \leq\) \(1\,000\) \(10^5\)
\(0 \leq k \leq\) \(1\,000\) \(10^6\)
Dĺžka celého vstupu \(\leq\) 1 MiB 2 MiB

Formát výstupu

O každej z \(t\) ceremónii vypíšte jeden riadok s jedným číslom: minimálny počet striedaní moderátorov medzi kategóriami.

Príklad

Input:

3
5
Jozef Mrkva
Marina Inoue
Tatiana Lieskovoorieskova
Karol XVI. Gustav
GEORG
10
Jozef Mrkva
Jozef Mrkva
GEORG
Karol XVI. Gustav
GEORG
Marina Inoue
Karol XVI. Gustav
Marina Inoue
Tatiana Lieskovoorieskova
GEORG
3
Adam
Bozena
Cyril
5
Bozena
Bozena
Bozena
Cyril
Bozena
2
Alica
Bob
7
Alica
Bob
Alica
Bob
Alica
Bob
Alica

Output:

1
0
6

Prvú ceremóniu môže začať Tatiana Lieskovoorieskova, vyhrala však deviatu kategóriu, takže ju potom musí niekto prestriedať. Druhú ceremóniu vie celú bez striedania odmoderovať Adam. V tretej ceremónii sa budú Bob s Alicou medzi každou kategóriou striedať.

Pôvodné zadanie síce bolo detailne naplánovať, kto presne bude kedy moderovať, ale vlastne stačí keď určíme v ktorých momentoch sa majú striedať. Na konkrétnych moderátoroch nezáleží. Chceme iba rozdeliť ceremóniu na niekoľko úsekov, v rámci ktorých sa moderátor nemení. Čo o nich musí platiť? Toto: Rozdelenie na úseky je korektné práve vtedy, keď sa v každom úseku vyskytuje maximálne \(h-1\) rôznych víťazov, t.j. keď je aspoň jeden herec čo počas toho úseku nič nevyhrá.

(Dôkaz: Z každého rozdelenia, ktoré spĺňa túto podmienku, by sme ľahko mohli v ďalšom kroku vyrobiť detailný plán. Proste pre každý úsek vyberieme ako moderátora toho herca, ktorý nič nevyhral. Ak sú viacerí, ľubovoľného. Ale náš program nemusí vypisovať zoznam moderátorov, iba počet striedaní, takže toto nebolo treba. A naopak rozdelenie, ktoré túto podmienku nespĺňa, zjavne nemôže byť korektné, lebo v takom úseku by niekto určite odovzdal cenu sám sebe.)

Na výpočet optimálneho rozdelenia použijeme greedy (pažravý) algoritmus. Proste ideme od začiatku do konca, a vždy sekáme úseky čo najneskôr ako môžeme. Pamätáme si množinu hercov čo niečo vyhrali v aktuálnom úseku. Keď uvidíme herca ktorý v nej ešte nie je, pridáme ho tam. Ale ak už ich tam je \(h-1\), respektíve keby po pridaní počet stúpol na \(h\), musíme začať nový úsek. V tom prípade sa ten herec stáva prvým hercom z nového úseku. (Dajte si pozor – asi najčastejšia chyba bola na toto zabudnúť a začať prázdny nový úsek bez neho.)

Aktuálnu množinu hercov si môžeme pamätať ako hashset ich mien (v Pythone set(), v C++ std::unordered_set<std::string>). Sú aj iné dobré možnosti, ale asi druhá najčastejšia chyba bola použiť proste zoznam mien ([], std::vector<std::string>). To je príliš pomalé, lebo kontrolovať či sa hodnota nachádza v zozname (if herec in zoznam) trvá lineárne od jeho dĺžky.

Časová zložitosť je \(O(h+k)\) a pamäťová \(O(h)\).

Dôkaz

Ako vždy, pri greedy algoritmoch treba zdôvodniť alebo formálne dokázať, či naozaj fungujú optimálne. Vo všeobecnosti séria lokálne optimálne vyzerajúcich krokov nie vždy naozaj vedie k globálne optimálnemu cieľu.

Dokážeme to napríklad takto: majme naše rozdelenie ktoré by vypočítal náš algoritmus, a nejaké konkurenčné rozdelenie ktoré sa od neho líši. Ukážeme, že konkurenčné rozdelenie môžeme postupnými malými zmenami prerobiť na naše. Po každej zmene bude rovnako dobré alebo lepšie, a bude ich konečne veľa. Z toho vyplynie, že naše rozdelenie je optimálne – rovnako dobré alebo lepšie než ľubovoľné konkurenčné.

Pozrime sa na najskoršie miesto, na ktorom sa líšia – jedno tvrdí “teraz striedaj” a druhé nie. Určite to konkurenčné tvrdí “teraz striedaj” a naše nie, lebo náš algoritmus z definície strieda najneskôr kedy môže. Tak to konkurenčné rozdelenie trošku upravme: posuňme to striedanie o jedna ďalej.

Takto upravené konkurenčné rozdelenie je stále korektné: predošlý úsek síce trochu narástol, ale ešte stále má maximálne \(h-1\) rôznych hercov (inak by náš algoritmus tiež na tomto mieste striedal), a ďalší úsek sa trochu zmenšil, ale to je určite vždy v poriadku. Počtom úsekov je nové konkurenčné rozdelenie rovnako dobré ako doterajšie konkurenčné, alebo dokonca lepšie (ak tam doteraz bol úsek dlhý 1 a v upravenom zmizne).

Tento postup opakujeme, až kým z konkurenčného rozdelenia nedostaneme postupnými úpravami presne to isté rozdelenie ako vyrobil náš algoritmus. V každom kroku sme zachovali korektnosť a nezmenili alebo zlepšili počet úsekov. Opakovanie časom musí skončiť, lebo dĺžka prefixu čo sa zhoduje s naším algoritmom stále rastie.

Z toho vyplýva, že nech bolo pôvodné konkurenčné rozdelenie akékoľvek, náš greedy algoritmus určite nájde rovnako dobré alebo lepšie.

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