Domácí kolo

H: Nejvyšší dort

Řešení (Zadání úlohy)

Jestli jste se dostali až sem, pak asi už víte něco o grafech a jejich užitečnosti v informatice.

Všimněte si, že problém nám působí to, že nemůžeme postavit dva stejně široké díly na sebe – kdybychom mohli, stačilo by vzít všechny díly, otočit je delší stranou na výšku a pak je na sebe skládat od nejšiřšího po nejužší.

Každou šířku však můžeme použít nejvýše jednou. Jinými slovy, chceme každému kusu dortu přiřadit jednu ze dvou možných šířek tak, aby žádné dva kusy neměly stejnou šířku a součet všech výšek byl co největší. To je to samé, jako požadovat, aby součet šířek byl co nejmenší, protože každý z rozměrů přispěje buď k součtu šířek, nebo výšek.

Lehká verze

Pro lehkou verzi jde použít převod na problém zvaný přiřazovací problém který dostane bipartitní graf s ohodnocenými hranami a vrátí množinu hran takovou, aby každý vrchol sousedil s právě jednou hranou v množině a součet cen vybraných hran byl co nejmenší. (Bipartitní graf je takový graf, jehož vrcholy můžeme rozdělit do dvou množin (partit) A a B takových, že vedou hrany jen mezi A a B.)

V našem případě vytvoříme vrchol za každý díl dortu a za každý rozměr a pak spojíme každý díl s (nejvýše dvěma) vrcholy odpovídajícími jeho rozměrům.

Algoritmů pro řešení takového problému je více a žádný z nich není zcela triviální, za zmínku stojí například Hungarian algorithm popsaný na anglické Wikipedii. Časová složitost tohoto algoritmu je v nejhorším případě O(N3) (i když v praxi může být algoritmus rychlejší), což na vyřešení těžší varianty nestačí.

Těžká verze

Abychom vyřešili těžkou verzi, musíme být o něco chytřejší.

Převedeme problém na neorientovaný multigraf, kde vrcholy budou všechny unikátní zadané délky a hrany budou jednotlivé formy. Všimneme si, že hledanou orientaci formy můžeme zakódovat jako směr hrany.

Orientace všech forem dává validní dort, když žádná délka není použita jako šířka více než jednou, což znamená, že všechny vrcholy mají outdegree (tj. počet hran vycházejících z vrcholu) nejvýše 1.

Řešíme tedy následující problém:

Dostaneme neorientovaný graf a chceme orientovat hrany tak, aby každý vrchol měl nejvýše jednu hranu z něj vycházející (tedy outdegree ≤ 1). Zároveň chceme maximalizovat výšku dortu neboli minimalizovat součet šířek dílků, který odpovídá součtu přes všechny vrcholy v z value(v) × outdegree(v), kde outdegree(v) odpovídá počtu forem, které mají délku odpovídající vrcholu v jako šířku, a value(v) je délka formy odpovídající vrcholu v.

Máme-li komponentu souvislosti s n vrcholy a m (orientovanými) hranami, pak průměrný outdegree je m/n, jelikož součet všech outdegree je m (každá hrana přispěje jedničkou). Chceme outdegree ≤ 1, tedy mn.

Když m < n, pak je taková komponenta stromem (přesněji bude platit, že m = n - 1), s méně hranami by komponenta nebyla souvislá. Jeden vrchol bude mít outdegree 0, zbytek outdegree 1. Necháme vrchol s největší hodnotou/délkou mít outdegree 0, abychom minimalizovali součet šířek výsledného dortu.

Když m = n, pak je taková komponenta stromem s jednou hranou navíc. Každý vrchol musí mít outdegree právě 1, takže bez ohledu na to, jak hrany zorientujeme, součet šířek bude vždy stejný.

Z takového rozdělení rovnou vychází poměrně jednoduchý algoritmus: Projdeme do hloubky každou komponentu, budeme počítat zmíněný součet value(v) × outdegree(v) = value(v) a poznamenávat si počet hran a vrcholů, které jsme prošli, abychom určili, jakého typu je komponenta, načež je-li to pouhý strom, tak od součtu odečteme největší value(v).

Na konci ještě spočítáme součet všech rozměrů všech forem a odečteme spočítaný součet šířek, čímž dostaneme součet všech výšek, neboli výšku dortu.

Takový algoritmus běží v čase O(N), tedy lineárním vzhledem k velikosti problému.

Ukázkový program (Python)

from collections import defaultdict

# Pomocná funkce pro načtení vstupu
def parse_input():
    # Počet forem
    N = int(input())

    # Slovník, který předpokládá, že když v něm nějaký klíč není,
    # tak má jako výchozí hodnotu prázdný seznam.
    G = defaultdict(list)
    
    for _ in range(N):
        # Načteme šířku a výšku formy
        x, y = [int(x) for x in input().split()]

        # Do výsledného grafu dáme hranu mezi šířkou a výškou (obousměrně).
        G[x].append(y)
        G[y].append(x)

    # Vrátíme předpřipravený graf
    return G

def solve():
    # Načteme vstup do grafu G
    G = parse_input()

    # Výsledná výška dortu
    result = 0
    
    # Množina již použitých/spatřených vrcholů pro DFS
    seen = set()

    for start in G.keys():
        # Pro každou komponentu začínající v start
        if start in seen:
            continue
        seen.add(start)
        stack = [start]

        # Počet spatřených vrcholů respektive hran v komponentě
        seen_vertices, seen_edges = 0, 0

        # Celková výška a maximální délka
        total, max_value = 0, 0

        # Projdeme graf do hloubky (DFS)
        while stack:
            value = stack.pop()

            # Počet sousedů v grafu,
            # neboli počet forem, které mají tuto hodnotu jako jednu z délek
            degree = len(G[value])
            
            # Zvýšíme počet spatřených hran a vrcholů v komponentě
            # Pozor, že každou hranu počítáme dvakrát!
            seen_edges += degree
            seen_vertices += 1
            
            # Za každou výšku přičítáme (počet sousedů - 1) * hodnota
            total += (degree - 1) * value

            # Uložíme si maximální doposud viděnou hodnotu
            max_value = max(max_value, value)

            # Projdeme všechny sousedy (pokračování DFS)
            for neighbour in G[value]:
                if neighbour in seen:
                    continue
                stack.append(neighbour)
                seen.add(neighbour)

        # Očekáváme, že jsme viděli každou hranu dvakrát
        assert seen_edges % 2 == 0
        # Zjistíme "opravdový" počet hran, které jsme viděli
        real_seen_edges = seen_edges // 2

        # Očekáváme, že jsme viděli více vrcholů než hran
        assert real_seen_edges <= seen_vertices

        # Komponenta je strom - musíme přidat k celkové hodnotě ještě nejvyšší výšku
        if seen_vertices > real_seen_edges:
            assert seen_vertices == real_seen_edges + 1
            total += max_value
        # Je-li komponenta strom + 1 hrana navíc, nemusíme dělat nic
        else:
            assert seen_vertices == real_seen_edges

        # Do výsledku přičteme celkovou výšku komponenty
        result += total

    # Vypíšeme výsledek
    print(result)

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        solve()

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)