PALMA junior
Úloha o stabilných akváriách

Autorské riešenie
[stiahni pavilon.py]

• Počet riešiteľov: 41 / 46 = 89 %

• Úspešnosť riešenia: 1,76 / 7 = 25 %

V tejto úlohe potrebujeme pre zadaný objem akvária nájsť jeho rozmery, pričom musíme dodržať niekoľko podmienok:

• objem akvária je zadávaný v celých litroch,

• rozmery akvária očakávame v celých decimetroch (dm),

• výška musí byť minimálne 10 dm,

• podstava musí byť štvorcová,

• z možných rozmerov vyberáme tie, pre ktorý bude akvárium najstabilnejšie, t. j. rozmery s najväčšou plochou podstavy alebo aj inak povedané, s najdlhšou stranou podstavy.

Túto úlohu môžeme riešiť niekoľkými spôsobmi. Ukážme si niektoré z nich a porovnajme ich efektívnosť. Požiadavka na efektívnosť bola súčasťou samotného zadania.

Riešenie 1

Rozmery akvária musia byť delitele jeho objemu. Hľadajme postupne delitele objemu, kde je podstava štvorcová a výška je aspoň 10 dm. Zo všetkých nájdených riešení vyberme to riešenie, kde je podstava najväčšia. Toto prvoplánové riešenie môže vyzerať nasledovne: 

def najdi_rozmery_1(objem):
    sirka, dlzka, vyska = 1, 1, objem
    for akt_sirka in range(1, objem + 1):
        if objem % akt_sirka == 0:
            zostatok = objem // akt_sirka
            if zostatok % akt_sirka == 0:
                akt_dlzka = akt_sirka
                akt_vyska = zostatok // akt_dlzka
                if akt_vyska >= 10:
                    sirka, dlzka, vyska = akt_sirka, akt_dlzka, akt_vyska
    return sirka, dlzka, vyska

Postupne hľadáme delitele objemu (akt_sirka) a overujeme, či aj druhá strana podstavy môže mať rovnakú dĺžku. Ak áno, overíme ešte či výsledná výška má aspoň 10 dm a ak áno, máme lepšie riešenie ako to predchádzajúce.  Keďže v cykle postupne šírku zväčšujeme, tak každé ďalšie riešenie predstavuje stabilnejšie akvárium. Posledné nájdené riešenie bude teda to najlepšie.

Riešenie 2

Riešenie 1 je síce správne riešenie, ale nie je veľmi efektívne, Tie najvhodnejšie rozmery nájdeme ako posledné. Čo keby sme začali hľadať z opačnej strany. Potom by prvé nájdené riešenie bolo tým najlepším a ďalšie hľadanie by sme už nepotrebovali realizovať. 

def najdi_rozmery_2(objem):
    for akt_sirka in range(objem, 0, -1):
        if objem % akt_sirka == 0:
            zostatok = objem // akt_sirka
            if zostatok % akt_sirka == 0:
                akt_dlzka = akt_sirka
                akt_vyska = zostatok // akt_dlzka
                if akt_vyska >= 10:
                    return akt_sirka, akt_dlzka, akt_vyska

Prehľadávame rovnaké hodnoty ako v riešení 1, ale v opačnom poradí (range v cykle for generuje hodnoty zostupne). Prvá trojica deliteľov ktorá vyhovuje je riešením. Každá ďalšia trojica totiž predstavuje akvárium s menšou stranou podstavy.

Riešenie 3

Pozrime sa, či by sa aj riešenie 2 nedalo ešte vylepšiť. Skúsme ho upraviť tak, aby sme neprehľadávali zbytočne veľa možností. 

Zamyslime sa nad týmto problém lepšie a uvedomme si, čo hľadáme.

Pre zadaný objem hľadáme tri celé čísla, pre ktoré platí: objem = a * b * c, pričom a = b a c >= 10.

V podstate teda hľadáme len dve čísla, pre ktoré platí: objem = a * a * c, pričom c >= 10.

Keďže c >= 10 musí platiť, že a*a <= objem /10 a teda a <= odmocnina(objem / 10). Začnime teda hľadať rozmery podstavy od odmocnina(objem / 10). Toto riešenie môže vyzerať nasledovne:

def najdi_rozmery_3(objem):
    for strana in range(int((objem / 10) ** 0.5), 0, -1):
        if objem % (strana * strana) == 0:
            return strana, strana, objem // (strana * strana)

Toto riešenie potvrdzuje fakt, že o čo neskôr začneme písať program (pretože sme sa venoval analýze problému) o to skôr program napíšeme (pretože riešenie už máme vopred premyslené). Výsledná funkcia je kratšia (aj keď to nebolo primárne našim cieľom) a výsledok počíta efektívnejšie.

Vyhodnotenie riešení

Postupne sme našli tri riešenia, pričom "tušíme" že sú postupne lepšie - rýchlejšie. Pozrime sa, či je tomu tak a ako sa zmenila rýchlosť výpočtu.

Zrealizovali sme malý test, kde sme porovnali časovú náročnosť jednotlivých riešení.

Testovali sme čas výpočtu rozmerov pre objemy: 48 l, 160 l,  36922057 l, 264196483 l. Posledné objemy sme získali ako súčin troch prvočísiel: 331 * 331 * 337 a 641 * 641 * 643. Vieme teda, aké výsledky očakávať.

Otestovali sme aj priemerný čas výpočtu pre 200 náhodných objemov z intervalu 10000 .. 10000000. Tento test sme zopakovali 10 krát pre každé riešenie a výsledky sme spriemerovali

Čas behu (v ns) jednotlivých riešení uvádzame v tabuľke:

Pri malých objemoch prakticky neexistuje rozdiel v časoch behu všetkých troch verzií. Pri väčších objemoch sa ukazuje neefektívnosť prvých dvoch riešení. V riešení 2 sme očakávali zlepšenie. Stalo sa tak, ale len v malej, prakticky nevýznamnej miere. Riešenie 3 sa ukazuje ako významne najlepšie.

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

Táto úloha vám zrejme dala zabrať. Pomerne veľa z vás úlohy nepochopilo celkom správne.

 Najčastejšou chybou bolo, že ste sa snažili rozmery akvária vypočítať tak, aby sa tvar akvária čo najviac priblížil kocke. To nebolo potrebné. Úlohou bolo maximalizovať plochu štvorcovej podstavy.

Ďalšou častou chybou bolo, že výšku akvária ste určili na 10. To však bola len minimálna hodnota výšky.

Ďalšia skupina z vás mala síce správne riešenie, ale nie veľmi efektívne. Ak nevyužijeme správne fakt, že rozmer podstavy nebude väčší ako odmocnina z objemu, pre veľké objemy sa výsledku prakticky nedočkáme.

Zaujímavý nápad mal tím file-open. Z prvočíselného rozkladu objemu sa snažili vypočítať dĺžky strán. Keďže použili Eratostenovo sito, riešenie nebolo veľmi efektívne, lebo spotrebovalo veľa pamäte.

Elegantné riešenia predviedli tímy oliverseman a sigma guru. Ich riešena sú takmer ako autorské riešenie 3.