2. Rekreačný cyklista Kubko vzorové riešenie

Zadanie

Novinka: táto úloha je rozdelená na niekoľko na seba nadväzujúcich sád, za ktoré viete dokopy získať 100 bodov. Zatiaľ máte k dispozícii iba zadania prvej sady. Na získanie zadaní ďalšej sady je potrebné odovzdať riešenia tej predchádzajúcej.

Hocikedy v priebehu kola môžete odovzdať vaše aktuálne riešenie. My vám ho v priebehu pár dní opravíme a pošleme späť aj s komentármi. Ak sa vám podúlohy podarilo vyriešiť správne, dostanete ďalšie zadania. Ak vaše riešenie nebolo správne, nič sa nedeje. V komentári vám skúsime poradiť kde nastala chyba a vy ju môžete opraviť a poslať znova až kým nebudete úspešní.

Veríme, že takto sa vám podarí vyriešiť viac podúloh a teda sa aj viac naučíte. Nabojte sa nám teda poslať aj rozpracované riešenie, alebo také, ktorým si nie ste úplne istí. Nehrozí vám žiadna penalizácia a môžete dostať dobrú radu. Odporúčame však úlohu riešiť priebežne.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Miškovi na [email protected]

Kubko sa rád bicykluje. V jeho okolí je však len zopár cyklistických chodníkov znázornených na obrázku. Napriek tomu vždy keď má nejaký voľný čas, sadne na bicykel a trénuje. Včera napríklad začal v mieste D, pokračoval cez C do E, potom sa vrátil do D a nakoniec skončil v B. Takúto cestu by sme skrátene zapísali ako D-C-E-D-B a jej dĺžka je 4.

Zajtra by sa chcel ísť znovu bicyklovať, no potrebuje si nájsť novú trasu, lebo ísť dvakrát po tej istej je príliš nudné. Zaujíma ho preto, koľko rôznych ciest určitej dĺžky v okolí existuje.

Sada úloh 1 – Krátke cesty

Kubko je síce zdatný cyklista, no počítanie nie je jeho silnou stránkou. Preto spočítať vhodné cesty pre Kubka ostalo na vás. Ako zvyčajne, budete riešiť niekoľko podúloh zoradených podľa nami odhadovanej zložitosti. Okrem výsledku vždy napíšte, aspoň pár vetami, ako ste sa k danému riešeniu dostali. Odporúčame vám podúlohy riešiť postupne, keďže riešenie jednej môže pomôcť pri riešení ďalšej.

1. (8 bodov) Zistite, koľko je na obrázku rôznych ciest dĺžky \(3\) takých, že začínajú v A a končia v D. Dve cesty sú rôzne ak neprechádzajú tými istými miestami presne v rovnakom poradí. Teda napríklad cesty B-E-D-C a B-D-E-C sú dve rôzne cesty dĺžky \(3\).

2. (10 bodov) Pre každý začiatok a koniec zistite, koľko existuje ciest medzi nimi s dĺžkou práve \(3\). Napríklad počet ciest medzi A a D už poznáte z predošlej podúlohy, ostáva vám to určiť pre zvyšné začiatky a konce. Nezabudnite, že cesty môžu začínať a končiť v tom istom mieste.

3. (8 bodov) Zistite, koľko je takých ciest, ktoré začínajú aj končia v mieste A, majú dĺžku 6 a v strede, teda vo vzdialenosti \(3\), bude Kubko v mieste B. Jedna takáto cesta je napríklad cesta A-E-D-B-A-E-A.

4. (8 bodov) Zistite koľko je takých ciest, ktoré začínajú v A, končia v C a majú dĺžku 6.

Sada úloh 1 – Krátke cesty

Podúloha (a)

Táto podúloha sa dala vyriešiť pomerne jednnoducho a to tak, že sme začali v A a pozreli sa na všetkých susedov A. Potom sme sa pozreli na všetkých susedov týchto susedov. Z tých sme vybrali len tých, ktorý susedia s D. Takto sme prešli všetky možnosti ako vieme začať v A, a prejsť 3-krát. Preto sme určite našli všetky také cesty.

Existujú teda 3 také cesty a to: A-B-E-D, A-E-B-D a A-E-C-D.

Podúloha (b)

Túto podúlohu budeme riešiť pobodne ako predošlú. Pre každý začiatok sa zase pozrieme na všetkých susedov, potom na ich susedov, a potom na ich susedov, čo sú vlastne konce. Všetky cesty ktoré majú ako začiatok A sú:

Keďže všetkých ciest dĺžky 3 je pomerne veľa, môžeme si pomôcť a spočítať ich jednoduchým programom:

# pre jednoduchost oznacime miesta A az E cislami 0 az 4

# pre kazdu dvojicu zaciatku a konca pocet ciest medzi nimi, na zaciatku 0
cesty = [[0 for j in range(5)]for i in range(5)]

# pre kazde miesto zoznam jeho susedov
susedia = [
    [1, 4],
    [0, 3, 4],
    [3, 4],
    [1, 2, 4],
    [0, 1, 2, 3]
]

# pre kazdy zaciatok
for zaciatok in range(5):
    # pre kazdeho 1. suseda
    for sused1 in susedia[zaciatok]:
        # pre kazdeho 2. suseda
        for sused2 in susedia[sused1]:
            # je jeden koniec
            for koniec in susedia[sused2]:
                cesty[zaciatok][koniec] += 1


print(cesty)

Pre každý začiatok a koniec vieme nájsť počet ciest dĺžky 3 medzi nimi v tabuľke.

Podúloha (c)

Cestu dlhú 6, z A do A, ktorá má v strede B, môžeme rozdeliť na 2 cesty, a to A-B a B-A. Z predchádzajúcej podúlohy vieme, že počet ciest dĺžky 3 z A do B a aj z B do A je 5. Každú z ciest A-B môžeme spojiť s každou B-A a vytvoria jedinečnú cestu z A do A cez B. Preto je tento počet rovný súčinu počtu ciest A-B a B-A, teda \(5 \cdot 5 = 25\).

Podúloha (d)

Opäť máme cesty dlhé 6, no tentokrát bez medzizastávky. Keďže počty ciest dĺžky 3 poznáme, aj tu by sa nám hodilo rozdeliť si cestu na dve, s dĺžkou 3. Ako medzizastávku si teda postupne vyberieme každé miesto. Potom vieme vypočítať počet ciest A-C ako súčet ciest A-C s medzizastávkou A, a ciest s medzizastávkou B, C, D a E. Tento súčet teda je \(2 \cdot 3 + 5 \cdot 3 + 3 \cdot 2 + 3 \cdot 5 + 6 \cdot 6 = 78\).

Sada úloh 2 – Tabuľky

Podúloha (a)

Máme zistiť počet ciest z A do E s medzizastávkou v C. Počet ciest dĺžky 6 z A do C už poznáme z predošlej sady. Zvyšok cesty má dĺžku 9. Zo zadania teda poznáme aj počet takýchto ciest (C-E). Počet ciest A do E s medzizastávkou v C, vypočítame ako súčin týchto hodnôt, teda \(78 \cdot 3\,182 = 248\,196\).

Podúloha (b)

Tu použijeme podobný princíp ako v predošlej sade. Pre nejaké dve miesta, napr. A-B sa dá počet ciest medzi nimi dĺžky \(12\) vypočítať tak, že využijeme medzizastávku vo vzdialenosti \(9\). Počet ciest dĺžky \(9\) poznáme zo zadania, ostane nám druhá časť cesty s dĺžkou \(3\). Počty takýchto ciest sme už zistili v predošlej sade. Pre jednu medzizastávku vieme vypočítať počet ciest keď vynásobíme počet ciest dĺžky \(9\) z A po medzistávku a počet ciest dĺžky 3 z medzizastávky do B. Keď potom tieto počty sčítame, dostane počet všetkých ciest medzi dvoma miestami.

Opäť si môžeme pomôcť jednoduchým programom, ktorý to zráta za nás.

# pocet miest
n = 5

# Tabulka pre cesty dlzky 3
T3 = [
    [2, 5, 3, 3, 6],
    [5, 4, 3, 7, 7],
    [3, 3, 2, 5, 6],
    [3, 7, 5, 4, 7],
    [6, 7, 6, 7, 6]
]

# Tabulka pre cesty dlzky 9
T9 = [
    [1972, 2681, 1993, 2647, 3182],
    [2681, 3546, 2647, 3601, 4255],
    [1993, 2647, 1972, 2681, 3182],
    [2647, 3601, 2681, 3546, 4255],
    [3182, 4255, 3182, 4255, 5038]
]

# Tabulke pre cesty dlzky 12
# zatial same 0
T12 = [[0 for j in range(n)] for i in range(n)]

# pre kazdy zaciatok
for z in range(n):
    # pre kazdy koniec
    for k in range(n):
        # pre kazdu medzizastavku
        for m in range(n):
            T12[z][k] += T9[z][m] * T3[m][k]

print(T12)

Riešenie opäť zapíšeme do tabuľky:

Podúloha (c)

Tu iba kúsok zovšeobecníme postup s predchádzajúcej podúlohy. Najprv si spravíme tabuľku \(5 \times 5\), kde bude \(1\) ak medzi danými miestami je cesta, inak \(0\). Takáto tabuľka je totižto tabuľka počtov ciest dĺžky \(1\) pre každý začiatok a koniec. Ďalej využijeme medzizastávku, tentokrát už po prvom kroku. Tak vieme veľmi podobným algoritmom získať tabuľku pre cesty dĺžky \(k + 1\).

Podúloha (d)

Tentokrát ide zase o zovšeobecnenie, namiesto tabuľiek veľkosti \(5 \times 5\) budeme mať tabuľky \(n \times n\). Inak je postup rovnaký ako v predošlej podúlohe.

Časová zložitosť

Môžeme sa ešte zamyslieť ako dlho bude niečo takéto trvať. Skúsime teda spočítať akú bude mať takýto algoritmus časovú zložitosť. Ak ste o časovej zložitosti ešte nepočuli, môžete si o nej viac prečítať v kuchárke.

Aj z programu si môžeme všimnúť, že využívame 3 vnorené cykly, a v každom prechádzame cez všetky miesta (pre každý začiatok a pre každý koniec prejdeme každú medzizastávku). Časová zložitosť teda je \(O(n^3)\).

Matice

Takéto tabuľky s ktorými pracujeme môžeme pomenovať matice. Naše spájanie tabuliek je ekvivalnentné s násobením matíc. To sa okrem tohto nášho spôsobu používa na riešenie sústav rovníc, alebo pri zobrazovaní rôznych útvarov napr. v počítačových hrách. Viac si o tom môžete prečítať napríklad tu.

Sada úloh 3 – Spájanie tabuliek

Podúloha (a)

Opäť sa jedná o ďaľšie zovšeobecnenie predošlej podúlohy. Môžeme si všimnúť, že opať využijeme vpodstate rovnaký algoritmus. Tento krát na ceste dĺžky \(k + l\) spravíme medzizastávku po \(k\) krokoch.

Podúloha (b)

Najprv si spravíme tabuľku \(n \times n\) pre počty ciest dĺžky \(1\). Teda v tabuľke bude \(1\) ak dané dve miesta sú spojené cestou, inak tam bude \(0\).

Pomalé spájanie

Prvé riešenie, ktoré by nám mohlo napadnúť je, že môžeme postupne spojiť 100 takýchto tabuliek. Spojili by sme teda najprv túto tabuľku samú zo sebou, potom výslednú znovu s tou pôvodnou, … až kým by sme nedostali tabuľku pre cesty dĺžky 100. Potrebovali by sme na to 99 spojení.

Rýchlejšie spájanie

Veľmi ľahko si vieme všimnúť, že takéto spájanie nie je optimálne. Po prvom spojení získame tabuľku pre cesty dĺžky 2. Ak by sme ju spojili so sebou samou, dostali by sme tabuľku pre 4. K nej by sme opäť mohli pridať tabuľku 2 a dostali by sme tabuľku pre dĺžku 6. Po 49 by sme mali tabuľku pre dĺžku 100. Dokopy by sme použili 50 spojení, započítavajúc aj to úplne prvé. Je však jasné, že ani pri dĺžke 2 by sme sa nemuseli zastaviť.

Najrýchlejšie spájanie

Zamyslime sa nad otázkou, pre akú najväčšiu dĺžku vieme mať tabuľku po \(1, 2, ..., n\) spojeniach. Jedným spojením vieme dostať najväčšie dĺžku, ak spojíme tabuľky s čo najväčšou dĺžkou. Preto sa nám vždy oplatí spojiť tabuľku pre najväčšiu dĺžku samú zo sebou. Tým sa nám po jednom spojení najväčšia dĺžka zdvojnásobí, teda po prvom spojení bude 2, po druhom 4, po treťom 8, a vo všeobecnosti po \(n\) spojeniach bude \(2^n\). Vieme teda, že po \(n\) spojeniach určite nemôže mať tabuľku pre dĺžku väčšiu ako \(2^n\).

Spájanie pre dĺžku 100

Vieme, že budeme potrebovať viac ako 6 spojení, lebo \(2^6=64\). Keďže 100 nie je mocninou 2, budeme musieť spraviť nejaké “neoptimálne” spojenia.

Spôsob ako získať tabuľku pre dĺžku 100: Najprv spojíme tabuľku pre dĺžku 1 s tou istou tabuľkou, a tým dostaneme tabuľku pre dĺžky 2. Potom spojíme tabuľky s dĺžkami \(2\) a \(1\), a tak dostaneme tabuľku pre dĺžky \(3\). Potom spojíme tabuľky s dĺžkami \(2\) a \(3\), a dostaneme dĺžky \(5\). Spojíme tabuľku s dĺžkami \(5\) s tou istou tabuľkou a dostaneme tabuľku pre dĺžky \(10\). Tú potom spojíme s tabuľkou pre dĺžky \(5\) a dostane tabuľku pre dĺžky \(15\). Tú spojíme znovu s tabuľkou pre \(10\), a dostaneme tabuľku pre \(25\). Tú spojíme samú zo sebou a dostaneme tabuľku pre dĺžky \(50\). No a tú keď spojíme samú zo sebou dostaneme tabuľku pre dĺžky \(100\).

Použili sme dokopy iba \(8\) spojení tabuliek. Existuje viacero rôznych riešní, ktoré využívajú \(8\) spojení, ale neexistuje žiadne, ktoré ich využíva menej.

Podúloha (c)

Opäť začneme s tabuľkou pre dĺžky \(1\). Budeme pokračovať ako v poslednej podúlohe, a vždy spojíme tabuľku pre najväčšiu dĺžku samú so sebou. Dostaneme teda tabuľky pre dĺžky ktoré sú mocninami čísla \(2\). Prestaneme, ak by sme mali dostať tabuľku väčšiu ako je \(d\). Taká tabuľka nám určite nepomôže.

Každé číslo sa dá zapísať ako súčet nejakých mocnín \(2\), s tým že sa nebudú opakovať. Tento zápis nám reprezentuje zápis daného čísla v dvojkovej sústave. Stačí nám teda pospájať zodpovedajúce tabuľky, a získame tabuľku pre cesty dĺžky presne \(d\).

Pre hodnotu \(d=100\) by to boli nasledovné tabuľky: 64, 32, 4.

Logaritmus

Toto slovo nie je nejaké zaklínadlo, ale je to názov matematickej funkcie. Táto funkcia je inverznou (opačnou) k umocňovaniu. Každý logaritmus má nejaký základ, my budeme tak, ako sa často v informatike používa používať ten so základom 2. Logaritmus nejakého čísla nám hovorí akou mocninou základu (v našom prípade 2) je dané číslo. Teda \(\log(2^x) = x\).

Koľko spojení použije takéto riešenie?

Najprv sme spravili najviac \(\log d\) spojení aby sme si predrátali tabuľky pre dĺžky mocnín 2. Potom pri spájaní sme každú spojili najviac raz, teda sme spravili najviac \(\log d\) spojení. Celkovo teda takýto program využíva \(O(\log d)\) spojení.