Zadanie
Ako všetci vieme tak Čak Norris má dvojičky - Čaka a Čakinku. Prázdniny už skončili a obaja tak už musia chodiť do školy. Dokonca už dostali aj prvú domácu úlohu. Majú dokázať, že Zem je plochá. Inými slovami majú ukázať, že to je prauda.
Ich tatko, starý Norris kedysi dávno vytesal všetky všeobecne známe praudy na neďalekú skalu. Čak a Čakinka by boli radi ako on a preto domácu úlohu vypracujú práve na túto skalu.
Čakinka je však lenivá, nechce sa jej chodiť až ku skale. Avšak je aj výnimočne bystrá a má skvelé dedukčné schopnosti. A tak ako správny súrodenci si s touto neľahkou úlohou pomôžu. Ich stratégia je nasledovná.
Čak bude behať ku skale a vytesávať novo zistené praudy. Cestou naspäť si niekoľko z už vytesaných práud zapamätá. Dobehne domov ku Čakinke povie jej čo si pamätá a bystrá Čakinka z toho odvodí neaký ďalší výrok (po tomto odvodení sa už aj tento výrok stáva praudou). Čak následne beží ku skale a aj tam tento výrok vytesá, ak tam ešte nie je. Celý cyklus opakujú kým na skale ešte nie je vytesané Zem je plochá.
Čak však nemá moc dobrú pamäť vie si pamätať len obmedzený počet výrokov, keď beží naspať od skaly. Pomôžte im a zistite koľko pamäte Čakovi stačí. Teda zistite koľko výrokov si musí vedieť Čak naraz pamätať (na jednej ceste od skaly domov) aby boli schopný splniť domácu úlohu alebo vypíšte, že to nie je možné bez ohľadu na jeho pamäť.
Úloha
Vo všeobecnosti existuje \(n\) výrokov, ktoré si očíslujeme od \(0\) po \(n-1\). Výrok číslo 0 je “Zem je plochá” a tento dostali za domácu úlohu Čak a Čakinka dokázať.
Ďalej máme \(m\) odvodzovacích pravidiel, pričom \(i\)-te z nich pozná Čakinka v tvare \(a_{i,0}, ..., a_{i,k_i}\). Čo znamená, že ak sú výroky \(a_{i,0}, ..., a_{i,k_{i-1} }\) prauda, tak aj výrok \(a_{i,k_i}\) je prauda.
A na záver máme na skale vytesaných \(l\) výrokov, ktoré sú všeobecná prauda (netreba ich odvádzať).
Zistite najmenší počet výrokov, ktoré si musí Čak pamätať naraz počas cesty domov, pokiaľ Čakinka vie odvádzať len z výrokov, ktoré si Čak pamätá. Alebo vypíšte, že by nám nestačila žiadna pamäť.
Formát vstupu
V prvom riadku vstupu sú čísla \(n\) a \(m\) (\(1\leq m,n\leq 1\,100\,000\)) udávajúce počet možných výrokov a počet odvodzovacích pravidiel.
Nasleduje \(2m\) riadkov. V nepárnych riadkoch je počet výrokov \(k_i\) v odvodzovacej formuly, a v párnych samotné čísla výrokov v odvodzovacom pravidle \(a_0, ..., a_{k,i}\). Pritom môžete predpokladať, že \(\sum_{i=0}^{m-1} k_i\leq 2\,000\,000\).
Na záver je vo vstupe počet všeobecných práud \(1 \leq l \leq n\). V poslednom riadku sú ich čísla.
Formát výstupu
Na výstup vypíšte jediné číslo a to najmenšiu možnú pamäť, pre ktorú vieme dokázať výrok “Zem je plochá”. Ak to nie je možné pre žiadnu pamäť vypíšte \(-1\).
Príklady
Input:
3 2
1
1 0
2
1 2 0
2
1 2
Output:
1
Zjavne si stačí zapamätať všeobecnú praudu \(1\) a potom už len použijeme prvé odvodzovacie pravidlo
Input:
4 3
2
1 2 3
2
1 3 2
2
2 3 0
1
1
Output:
-1
Na dokázanie plochosti zeme potrebujeme najprv dokázať praudu 2 a 3. Na dokázanie praudy 2 však potrebujeme praudu 3, a na dokázanie praudy 3 potrebujeme zasa praudu 2. V tejto čudesnej, fiktívnej realite teda zem plochá asi nieje.
Skúsme najprv vyriešiť jednoduchšiu verziu úlohy. Pokúsme sa len overiť, či sa zo všeobecných práud (ďalej ich budeme volať axiómy) dá odvodiť výrok \(0\).
Naše riešenie sa bude inšipovať myšlienkami pri prehľadávaní grafov. Budeme si udržovať množinu už dokázaných výrokov a takisto frontu výrokov, ktoré postupne budeme spracovávať (už dokázaných). Ku každému pravidlu si budeme navyše pamätať počet predpokladov (výrokov, ktoré treba mať dokázané aby sme vedeli dokázať nové tvrdenie) ktorésúuž dokázané.
Začneme tým, že označíme všetky axiómy za pravdivé a všetky si ich uložíme do našej fronty. Budeme postupne spracovávať výroky z fronty. Keď budeme spracovávať výrok \(v\), ktorý sa nachádza ako predpoklad v odvodzovacích pravidlách \(a_1,...,a_k\). Pre každý z týchto výrokov zvýšime počítadlo dokázaných predpokladov. A pokiaľ sme už dokázali všetky predpoklady môžeme prehlásiť za pravdivý aj jeho dôsledok (výrok ktorý sme dokázali týmto odvodzovacím pravidlom). A zároveň tento novo dokázaný výrok pridáme do fronty.
Až sa nám raz vyprázdni fronta budeme mať dokázané všetky dokázateľné výroky a teda jednoducho overíme, či medzi ne patrí aj výrok 0.
Všimnime si, že celý algoritmus by mal časovú zložitosť \(O(n+ \sum_{i=0}^{m-1} k_i)\). Kde \(n\) je počet výrokov a \(k_i\) počet predpokladov v \(i\)-tom odvodzovacom pravidle. Každý výrok totiž len raz pridáme do fronty a každý predpoklad si teda len raz označíme za splnený.
Jednoduché zaklincovanie
Ak chceme vyriešiť pôvodnú úlohu, stačí vyskúšať všetky možné pamäte Čaka, vyfiltrovať, ktoré odvodzovacie pravidlá si vie zapamätať a vždy spustiť vyššie spomínaný algoritmus. Ba čo dokonca viac, my tú správnu najmenšiu vyhovujúcu pamäť vieme binárne vyhľadať. Vtedy časová zložitosť nášho riešenia pri správnej implementácii vedie ku \(O((n+ \sum_{i=0}^{m-1} k_i) log (max k_i))\)
Vzorák
Vzorák namiesto spúšťania prehľadávania zakaždým od znova bude prehľadávať postupne, najprv pomocou najmenších odvodzovacích pravidiel a potom pomocou väčších. Zabezpečíme to tým, že namiesto jednej fronty ich budeme používať \(max k_i\). Algoritmus bude podobný ako pôvodný. Axiómy pridáme do fronty číslo \(0\). Teraz budeme postupne spracovávať frontu ako vyššie. Avšak ak dokážeme všetky predpoklady niektorého odvodzovacieho pravidla, tak namiesto pridania dôsledku do rovnakej fronty pridáme ho do fronty s poradovým číslom podľa počtu potrebovaných predpokladov. Keď sa nám vyprázdni aktuálna fronta skontrolujeme, či sme už dokázali výrok \(0\). Ak áno, môžeme vypísať poradové číso ukončenej fronty. Ak nie, tak začneme spracovávať frontu s poradovým číslom o jedna väčším.
Celé to bude mať časovú zložitosť \(O(n+ \sum_{i=0}^{m-1} k_i)\). Keďže podobne ako vyššie, každý výrok bude v niektorej fronte maximálne raz (ak už je výrok pravdivý nepridávame ho do fronty aj keď sme ho odvodili znova). Zbytok algoritmu je rovanký ako vyššie. Pamäťová zložitosť bude \(O(n+ \sum_{i=0}^{m-1} k_i)\), keďže si musíme pamätať všetky odvodzovacie pravidlá a k nim to, koľko z predpokladov už bolo odvodených, a takisto fronty, v ktorých bude dokopy najviac \(n\) prvkov (každý výrok maximálne raz).
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ť.