Druhá série třicátého druhého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Poněkud opožděně vydáváme komentáře k úlohám druhé série KSP-H, přesněji řečeno k té jedné úloze, která za komentování stála.
Pokud se vám cokoliv nezdá nebo máte nějaký dotaz, neváhejte se ozvat na našem fóru nebo emailem na známou adresu.
Komentáře k úlohám
32-2-4 Družicová komunikace (Zadání) (Řešení)
Spousta řešení začala nalezením maximální kostry. To je pěkné usnadnění dalších výpočtů, ale časově to nebylo potřeba, všimněme si, že hledání kostry v podstatě simulujeme ve vzorovém řešení a hrany této kostry odpovídají těm, u kterých se ve výpočtu změní počet komponent.
Taky pozor na to, že původní graf nemusí být souvislý a u několika řešení toto očekávání vedlo k nekorektnímu algoritmu. Taky tedy nemůžeme mluvit o maximální kostře, ale o kostrách jednotlivých komponent, což je ale jen věc pojmů, protože algoritmus se tím nezmění.
Ne všichni znali strukturu DFU, což je samozřejmě nevýhoda, ale ona nebyla potřeba (pro dosažení vzorové složitosti), čehož si taky všiml jeden řešitel, podívejme se teď na použitý trik: místo DFU stromku můžeme mít pro každou komponentu uložený počet jejích vrcholů a jejich seznam a pro každý vrchol index jeho komponenty. To nám umožní komponenty sjednocovat tak, že vždy „přeindexujeme“ tu komponentu, která má méně vrcholů.
Díky tomu se každý přeindexovaný vrchol objeví v komponentě alespoň dvojnásobné velikosti oproti té původní, a protože vrcholů je jen N, přeindexuje se tak každý vrchol maximálně O(log N)-krát, což vede spolu s třízením hran na časovou složitost předvýpočtu O(N log N + M log M), tedy celkově na stejně rychlé řešení, jako je to vzorové.