PALMA junior
Úloha o charitatívnom behu

Autorské riešenie
[stiahni beh_pre_reklamu.py]

• Počet riešiteľov: 8 / 8 = 100 %

• Úspešnosť riešenia: 5 / 7 = 71 %

Pri riešení tejto úlohy musíme zistiť, koľko krát bežci prebehnú jednotlivými úsekmi okruhu. Zo zadania môžeme predpokladať, že dĺžka okruhu je celočíselná, jednotlivé časti okruhu sa číslujú od nuly a všetci bežci bežia v jednom smere. Ukážme si postupne niekoľko riešení. Predpokladajme situáciu uvedenú v zadaní, dĺžku okruhu 5 km a registrované behy [[3, 4], [4, 6]].

Riešenie 1

Riešenie, ktoré nám pravdepodobne napadne ako prvé, je simulovať každý registrovaný beh a priebežne aktualizovať počty bežcov na jednotlivých okruhoch.

Samotný program môže vyzerať nasledovne: 

def pocet_bezcov_1(dlzka_okruhu, registracie):
    pocty = [0] * dlzka_okruhu

    for beh in registracie:
        od_km = beh[0]
        pocet_km = beh[1]
        do_km = od_km + pocet_km
        for km in range(od_km, do_km):
            pocty[km % dlzka_okruhu] += 1

    return pocty 

Na začiatku nastavíme všetkým úsekom okruhu hodnotu 0. Potom postupne simulujeme každý registrovaný beh. Tu si musíme dať pozor na dve veci.

• Ak bežec prebehne posledným kilometrom okruhu (presnejšie je to úsek s najvyšším číslom) a pokračuje ďalej, dostane sa na úsek 0.

• Keďže bežci bežia po okruhu, môžu nejakými úsekmi prebehnúť viackrát.

Preto kilometer okruhu, ktorým bežec beží, počítame vždy ako zvyšok kilometra po delení dĺžkou okruhu (pocty[km % dlzka_okruhu] += 1) .

Riešenie 2

Ak sa kritickejšie pozrieme na riešenie 1 tak zistíme, že by sme ho vedeli vylepšiť. Ak bežec zabehne niekoľko celých okruhov, môžeme tieto okruhy započítať naraz. Simulujme teda len tú časť behu, ktorá sa realizuje nad celé okruhy.

Toto vylepšené riešenie môže vyzerať nasledovne: 

def pocet_bezcov(dlzka_okruhu, registracie):
    pocty = [0] * dlzka_okruhu
    pocet_celych_okruhov = 0

    for beh in registracie:
        od_km = beh[0]
        pocet_km = beh[1]
        pocet_celych_okruhov += pocet_km // dlzka_okruhu
        do_km = od_km + pocet_km % dlzka_okruhu
        for km in range(od_km, do_km):
            pocty[km % dlzka_okruhu] += 1

    for km in range(dlzka_okruhu):
        pocty[km] += pocet_celych_okruhov

    return pocty

Všimnime si zmeny oproti predchádzajúcemu riešeniu.

V premennej pocet_celych_okruhov si budeme postupne počítať počty celých okruhov, ktoré bežci zabehnú. Počet kilometrov každého bežca upravíme tak, že započítame len kilometre nad celé okruhy (pocet_km % dlzka_okruhu). Celé okruhy bežca následne pripočítame k celkovému počtu celých okruhov. Nakoniec počet celých okruhov započítame ku každému úseku okruhu.

Riešenie 3

Predchádzajúce riešenie je šikovnejšie v tom, že nemusíme násobne "krúžiť" po okruhu, ale môžeme počet celých okruhov bežca priamo vypočítať a započítať naraz. Aj toto riešenie je však možné ešte vylepšiť.

Nemusíme simulovať beh bežca a priebežne aktualizovať počty bežcov na jednotlivých úsekoch okruhu. Registrujme si len zmeny počtu bežcov na jednotlivých úsekoch. Ak to spravíme pre každý beh bežca, budeme vedieť nakoniec priamo vypočítať, koľko bežcov každým úsekom okruhu beží.

K tomu samozrejme potrebuje vedieť, koľko bežcov na úsek dobieha z predchádzajúce úseku a pokračuje ďalej. Otázka je, kde začať, keďže ide o okruh a bežci môžu začínať a končiť kdekoľvek. Celkom prirodzene si môžeme za začiatok zvoliť úsek 0 a priebežne si počítať, koľko bežcov prebieha úsekom 0. V úseku 0 nás teda nebudú zaujímať bežci, ktorí v ňom končia, ale len tí, ktorý tam začínajú alebo ním prebiehajú.

Výsledné riešenie môže vyzerať nasledovne:  

def pocet_bezcov_3(dlzka_okruhu, registracie):
    pocty = [0] * dlzka_okruhu
    pocet_celych_okruhov = 0
    bezia_cez_0 = 0

    for beh in registracie:
        od_km = beh[0]
        pocet_km = beh[1]
        pocet_celych_okruhov += pocet_km // dlzka_okruhu
        do_km = (od_km + pocet_km) % dlzka_okruhu
        if 0 != od_km > do_km != 0:
            bezia_cez_0 += 1
        if od_km != do_km:
            pocty[od_km] += 1
            if do_km != 0:
                pocty[do_km] -= 1

    aktualny_pocet = bezia_cez_0
    for km in range(dlzka_okruhu):
        pocty[km] += aktualny_pocet
        aktualny_pocet = pocty[km]

    for km in range(dlzka_okruhu):
        pocty[km] += pocet_celych_okruhov

    return pocty 

Zamerajme sa na zmeny oproti predchádzajúcemu riešeniu.

Ak bežec začína na väčšom kilometri ako končí a zároveň žiaden z týchto kilometrov nie je 0 (0 != od_km > do_km != 0), vieme že kilometrom 0 prebieha. Aktualizujeme počet prebehnutí cez úsek 0.

Ak začínajúci a končiaci kilometer sú rôzne (od_km != do_km) vieme, že okrem celých okruhov bežec beží aj nejakú časť navyše. Aktualizujeme zmeny v jednotlivých úsekoch okruhu (okrem prípadu, že končí v kilometri 0).

Následne môžeme počty bežcov v jednotlivých kilometroch okruhu aktualizovať. Začneme na úseku 0. Tu sme si priebežne počítali koľko bežcov týmto úsekom prebieha. O túto hodnotu aktualizujeme počet bežcov v tomto úseku. Toto je zároveň počet bežcov, ktorí dobehnú do nasledujúceho úseku. Obdobnú aktualizáciu vykonáme pre všetky nasledovné úseky okruhu.

Nakoniec k úsekom pripočítame celé okruhy.

Záver

Vytvorili sme celkom tri riešenia, pričom každé nasledujúce by malo byť lepšie. Pozrime sa na to, či tomu naozaj tak je.

Predpokladajme modelovú situáciu:

• dĺžka okruhu je 20 kilometrov,

• počet bežcov je 1000,

• každý zabehne niečo málo nad 100 km (100 + x, pričom x < 20 = dĺžka okruhu).

V prvom riešení pre každého bežca simulujeme každý kilometer jeho behu. Celkovo teda spravíme 1000 * (100 + x) úprav úsekov. Rádovo je to pocet bežcov * dlzka behu.

V druhom riešení celé úseky započítavame naraz. Celkovo teda spravíme 1000 * x + 20 úprav úsekov. Rádovo je to pocet bežcov * dĺžka okruhu.

V treťom riešení tiež započítavame celé úseky naraz a zároveň registrujeme len zmeny na úsekoch. Celkovo teda spravíme  1000 * 2 + 20 + 20 zmien úsekov. Rádovo je to pocet bežcov + dĺžka okruhu.

Samozrejme by sme vedeli vytvoriť modelové situácie, kde by vylepšenia neboli až také výrazné. Pre porovnanie je vhodné zobrať všeobecný alebo najhorší prípad. 

Vaše zaujímavé riešenia a najčastejšie chyby

Vyriešiť úlohu sa podarilo takmer každému tímu. Niektorí z vás efektívne vyriešili celé okruhy bežcov a započítali ich priamo bez simulácie. Len dvom tímom, csongorpatka guru a file-open guru, sa však úlohu podarilo vyriešiť efektívne (podobne ako v riešení 3).