Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil(a) chyby, prípadne ti poradí, ako vieš svoje riešenia zlepšiť.
Ak máš hocijaké otázky k tejto úlohe, napíš Štepimu na [email protected]
Bolo raz jedno kráľovstvo a v ňom vládol kráľ. Vládnutie v takej veľkej krajine ale bolo veľmi namáhavé, tak si zohnal ministrov, ktorým dával robiť prácu zaňho. Po čase toho ale aj tí ministri začali mať príliš veľa roboty, a tak si aj oni zohnali ďalších úradníkov, ktorým by mohli dávať robiť časť svojej roboty. Ako sa kráľovstvo rozrastalo, úradníci si postupne zháňali ďalších podriadených. (Každý úradník môže byť priamy podriadený iba jedného úradníka.)
Kráľ má teraz problém, že vôbec nevie ani, kto všetko sú vlastne jeho úradníci. Rád by o nich niečo zistil, ale komunikovať vie iba so svojimi ministrami. Všeobecne každý úradník spraví to, čo mu šéf povie, ale komunikovať vie iba so šéfom alebo priamymi podriadenými.
V každej úlohe chce kráľ zistiť nejakú informáciu. Vymysli, ako to má urobiť, teda čo sa má spýtať a čo má povedať svojim podriadeným, aby zistil to, čo ho zaujíma.
Navyše to skús vymyslieť tak, aby kráľ zistil, čo chce vedieť, čo najefektívnejšie. Keď sa jeden úradník niečo pýta druhého, zaberie to nejaký čas, takže môže trvať dlho, kým sa konečne kráľ dozvie odpoveď. Snaž sa teda, aby bolo dokopy treba čo najmenej pýtaní.
a. Kráľ by chcel v prvom rade vedieť, koľko má vlastne úradníkov. Ako to má zistiť?
b. Kráľ by chcel niečo odkázať všetkým svojim úradníkom, ale kým sa k nim tento odkaz dostane, môže to celkom trvať, lebo odkaz musí prejsť cez viacero úradníkov medzi nimi. Kráľ by chcel vedieť, koľko bude musieť čakať, a teda by ho zaujímalo, ako ďaleko je od neho najvzdialenejší úradník (teda cez koľkých podriadených sa k nemu odkaz musí dostať). Ako to má zistiť?
c. Niekedy potrebuje úradník poslať správu inému úradníkovi. To funguje tak, že ju pošle svojmu šéfovi alebo podriadenému, ten ju pošle zas niekomu ďalšiemu, a tak ďalej, až kým sa správa nedostane k adresátovi.
Mohlo by nás teda zaujímať, ako ďaleko sú od seba nejakí dvaja úradníci, teda cez koľko aspoň ľudí musí prejsť správa, ktorú posiela jeden druhému.
Ako vie kráľ zistiť, ako ďaleko sú dvaja najvzdialenejší úradníci?
d. Do kráľovstva prišla vojna a aj úradníci sú v ohrození. Keď nejakého úradníka zajmú vojaci, tak jeho podriadení už nebudú vedieť komunikovať s jeho nadriadenými.
Povieme, že úradník $U$ je posol pre nejakú dvojicu iných úradníkov $A$ a $B$, keď na to, aby si $A$ a $B$ mohli poslať správu, musí tá správa prejsť aj cez úradníka $U$.
Kráľa by zaujímalo, ktorý úradník je posol pre najviac rôznych dvojíc. Ako to má zistiť?
Vzoráky z tohto kola si môžeš pozrieť aj ako video
Kráľ sa môže pýtať len svojich priamych podriadených, takže by sa hodilo, keby oni vedeli, koľko majú pod sebou ľudí. Tieto počty by povedali kráľovi a on by ich sčítal (a ešte pripočítal $1$, ak chce rátať aj seba). Ale ako to zistia kráľovi podriadení? No vlastne tak isto, spýtajú sa svojich podriadených, sčítajú výsledky a pripočítajú $1$ za seba. Takto to pokračuje ďalej, až kým sa to nedostane k úradníkom, ktorí žiadnych podriadených nemajú. Tí vedia, že pre nich je odpoveď $1$ a môžu to rovno povedať svojim nadriadeným. Takto sa to dostane späť až ku kráľovi, ktorý sa dozvie výsledok.
Každý bude chcieť zistiť, ako najďalej pod ním je najvzdialenejší úradník. Pre tých, čo nemajú podriadených, je odpoveď $0$ (majú tam len sami seba a tak nikomu nemusia posielať správy). Ak niekto má podriadených, tak sa ich spýta na odpovede. Najvzdialenejší úradník pod ním bude najvzdialenejší od ľubovoľného jeho priameho podriadeného, ale vzdialenosť bude o $1$ väčšia (lebo správa musí prejsť ešte jeden krok navyše). Úradník teda zoberie najväčšiu z odpovedí svojich podriadených, pripočíta k tomu $1$, a to bude jeho odpoveď. Takto sa odpoveď dostane až ku kráľovi.
Ako úradník budem chcieť zistiť, ako ďaleko je najvzdialenejšia dvojica podo mnou. Nazvime týchto najvzdialenejších úradníkov $A$ a $B$. Jedna možnosť je, že sú pod rôznymi mojimi priamymi podriadenými – nech $A$ je pod mojim priamym podriadeným $U$ a $B$ je pod mojim priamym podriadeným $V$. Potom dĺžka cesty medzi $A$ a $B$ je vzdialenosť $A$ od $U$, plus dva kroky (od $U$ ku mne a odtiaľ k $V$) plus vzdialenosť $B$ od $V$. Dĺžka cesty bude teda najväčšia, ak $A$ a $B$ budú čo najďalej pod $U$ a $V$. Počítať, ako ďaleko sú najvzdialenejší úradníci, vieme z úlohy B. Aby bola cesta čo najdlhšia, tak chceme zobrať takých dvoch mojich podriadených, že vzdialenosti tých ľudí najhlbšie pod nimi sú čo najväčšie. Takto teda vieme spočítať najdlhšiu cestu v tomto prípade, keď tá cesta ide cezo mňa.
Okrem toho sa môže stať, že tá cesta nejde cezo mňa, ale vtedy ide celá podo mnou. To znamená, že stačí, aby si úradníci ešte navyše hovorili svoje odpovede, a ak budem počuť odpoveď, ktorá je väčšia než tá moja z minulého prípadu, tak použijem tú.
Nakoniec sa môže stať, že mám iba jedného priameho podriadeného, v tom prípade ak tá cesta ide cezo mňa, tak musí začínať u mňa, a teda odpoveď je vzdialenosť toho najvzdialenejšieho podo mnou, čo už vieme z úlohy B.
Takto každý zistí dĺžku najdlhšej cesty pod sebou a nakoniec to zistí aj kráľ.
Ako úradník budem chcieť zistiť, čo sa stane, keď zmiznem. Dovtedy bol strom (štruktúra úradníkov) súvislý (dalo sa poslať správu odvšadiaľ všade), ale teraz sa rozpadne na niekoľko častí. Každý môj priamy podriadený bude mať teraz pod sebou jednu samostatnú časť (ktorá nevie komunikovať s nikým mimo tej časti), a ešte jedna samostatná časť bude to nado mnou (teda moji nadriadení a ich podriadení, ktorí nie sú moji podriadení). Takúto samostatnú časť nazveme komponent.
Koľko dvojíc zrazu nebude vedieť komunikovať? Z každej takej dvojice sú buď moji podriadení obaja, alebo len jeden z nich. Pozrime sa na toho, ktorý je môj podriadený. On je v nejakom komponente z tých mojich podriadených. V tomto komponente každý prestane vedieť komunikovať so všetkými ostatnými komponentami podo mnou aj s komponentom nado mnou. Počet takýchto dvojic (ktoré majú jedného človeka v nejakom danom komponente) je počet ľudí v tom komponente krát počet ľudí v tých ostatných komponentoch.
Z podúlohy A viem zrátať počet ľudí pod každým úradníkom, takže z toho viem aj spočítať tie počty, ktoré ma zaujímajú. Nech podo mnou je úradník $U$. Ľudia v jeho komponente sú práve ľudia pod ním, takže ich počet vieme. Počet ľudí v ostatných komponentoch podo mnou je počet ľudí podo mnou, mínus počet ľudí pod $U$, mínus $1$ (za mňa). Počet ľudí v komponente nado mnou je počet ľudí celkovo (čo najprv zistí kráľ a potom to môže rozposlať ostatným), mínus počet ľudí podo mnou (čo už vieme).
Takto pre každý komponent podo mnou zrátam, koľko je dvojíc ktoré prestanú vedieť komunikovať, takých že jeden z tej dvojice je v tom danom komponente. Ešte je ale problém, že dvojice, kde sú obaja podo mnou, som zarátal dvakrát (raz za každého z tých ľudí). Preto ich musím rátať osobitne a počet tých, ktoré sú podo mnou, nakoniec vydeliť dvomi. Tak dostanem celkový počet.
Takto si každý zráta, pre koľko dvojíc je posol. Potom každý zoberie najväčšiu z odpovedí od svojich priamych podriadených a seba, a tú pošle ďalej. Takto sa ku kráľovi dostane najväčšia odpoveď.