Často kladené dotazy

„U Elektrona Svatýho, co myslel tímhle?“

„A časovou složitost má kde?“

„Proč by tohle mělo fungovat?“

Takové a mnohé další dotazy si my, organizátoři KSP, klademe při opravování došlých řešení. Bohužel, někdy na ně odpovědi nenajdeme, a proto ze zvědavosti strhneme několik bodů. Sice se mnozí řešitelé časem naučí, co dělat mají a co ne, aby získali co nejvíce bodů, ale chvíli to trvá a některé při tom ztratíme.

Pro ulehčení nováčkům jsme tedy připravili tento návod. Představme si modelovou úložku. Úkolem je spočítat největšího společného dělitele dvou čísel (předstírejte na chvíli, že jste to ještě nikdy neřešili). Na ní si ukážeme postup, jak dojít ke správnému řešení, a také pár tipů, co nedělat.

Napřed je, samozřejmě, potřeba řešení vymyslet. První, co nás pravděpodobně napadne, je zkusit vydělit obě čísla tím menším z nich. Pokud po dělení je nějaký nenulový zbytek, pak to není největší společný dělitel a my zkusíme číslo o 1 menší. A tak dále, dokud nepotkáme takové, které beze zbytku dělí obě. To je samozřejmě společný dělitel a je první, kterého jsme potkali, takže je největší. Takový postup má mnohé výhody – je jednoduchý, zcela očividně vrátí správný výsledek, a navíc máme jistotu, že někdy skončí (zastavíme se určitě nejpozději u jedničky). Ale jde to i rychleji (co znamená „rychleji“, to si povíme za chvíli).

Zapomeneme na rozklad na prvočísla, který je na první pohled příliš komplikovaný, než aby měl šanci na úspěch. Vezmeme dvě zadaná čísla. Pokud se rovnají, pak jsou (obě) největším společným dělitelem. Pokud ne, to větší z nich zmenšíme o to menší a pokračujeme stejně. Navíc pokud bude jedno číslo obrovské a druhé maličké, budeme to maličké odečítat opakovaně, až získáme … zbytek po dělení většího menším. To by mohlo výpočet ještě zrychlit.

Dobrá, postup máme. Co teď? Nyní je vhodné napsat vlastní program v nějakém jazyce. My organizátoři ho sice nepožadujeme „povinně“, ale pomůže odhalit nedostatky (či nedomyšlené „zrady“) v algoritmu. Například na našem příkladě bychom zjistili, že zatímco odečítací metoda funguje, metoda zbytková se bude pokoušet dělit nulou (alespoň tak, jak jsme ji popsali). V nějakou chvíli již bude v menším čísle uložený výsledek. Při odčítání dojdeme postupně ke stejnému číslu – ale při dělení získáme zbytek 0 jedinou operací. V takovou chvíli je třeba skončit. Navíc nám program pomůže pochopit méně jasné části popisu.

Program by vypadal třeba takto (zapíšeme ho v Pascalu):

var x, y: integer;
begin
	read(x, y);
	while (x<>0) and (y<>0) do
		if x>y then x := x mod y
		else y := y mod x;
	writeln(x+y);
end.
(všimněte si malého triku: když je na konci jedno z čísel x, y nulové, tak x+y je rovno tomu nenulovému).

Nakonec je třeba vytvořit text řešení. Co by měl obsahovat? Určitě popis algoritmu, a to takový, aby kdokoliv, kdo umí jen trochu programovat, podle něho byl program schopný napsat. Musí z něho jít pochopit, co se děje. Při tomto popisu lze použít nějaký již existující algoritmus jako stavební kámen, například se odkázat na nějakou knížku nebo Programátorské kuchařky z webu KSPčka. Pokud tento popis bude nejasný nebo nejednoznačný, pokusíme se nějakou myšlenku vykoukat z přiloženého programu, avšak už za nedostatečný popis nejspíš pár bodů ztratíte.

Další částí by mělo být nějaké zdůvodnění, proč vlastně program počítá to, co se po něm chce. Určitě nám ještě nevěříte, že popsaná magie se zbytky funguje. My mnohým tvrzením, která nám dojdou, také ne (některému až tak moc, že si dáme práci ho vyvrátit). Co by bylo důkazem v tomto případě? Třeba následující textík (zapsaný opravdu důkladně, jako formální důkaz, obvykle však stačí myšlenka):

Tvrdíme, že v každém kroku algoritmu nahradíme větší z čísel x,y nějakým jiným, ale zachováme přitom všechny společné dělitele dvojice x,y, tím pádem samozřejmě i největšího společného dělitele. A jakmile se algoritmus zastaví (což zajisté učiní), držíme v ruce dvě čísla, z nichž jedno je nula (a ta je beze zbytku dělitelná čímkoliv), a tedy největší číslo, které dělí obě, je to druhé, nenulové.

Zbývá tedy dokázat, že jeden krok algoritmu zachovává všechny společné dělitele. Mějme nějakého společného dělitele d čísel x,y. Navíc předpokládejme, že x>y, takže x budeme nahrazovat číslem z=x mod y (kdyby x<y, tak jen prohodíme xy). Co z toho víme:

x = x'*d
y = y'*d
z = x - t*y

pro nějaká x', y', t. Číslo z tedy můžeme upravovat takto: z=x-ty=x'd - ty'd=(x'-ty')d. Takže z je také dělitelné číslem d.

Nechť naopak nějaké d dělí dvojici z,y. Pak víme:

z = z'*d
y = y'*d
x = z + t*y,

takže x = z'd + ty'd = (z'+ty')d je také dělitelné číslem d. Zjistili jsme tedy, že společní dělitelé dvojic x,y a z,y jsou titíž.

Nakonec je potřeba odhadnout, jak dobrý algoritmus jsme vymysleli. K tomu slouží odhady časové a paměťové složitosti. Co to je? Zajímá nás především, jakým způsobem rostou nároky na čas strávený algoritmem a paměť, kterou při běhu spotřebuje, v závislosti na velikosti vstupu. Například pokud chceme vybrat nejmenší ze zadaných čísel, pak při dvakrát větším vstupu to bude trvat déle, zatímco vypsat 3. číslo (dle pořadí, ne dle velikosti) vstupu nám bude trvat vždycky stejně dlouho – zbytek vstupu nepotřebujeme ani přečíst.

K tomuto používáme tzv. asymptotické odhady – najdeme funkci, která roste řádově alespoň tak rychle, jako naše nároky. Pro jednoduchost se zanedbají všechny konstanty a menší funkce. V případě výběru nejmenšího budeme psát, že čas je O(n) pro vstup velikosti n – roste tolikrát, kolikrát vyroste vstup, zatímco paměť bude vždy stejná – O(1), tj. konstantní (ano, mohli bychom psát třeba O(4), ale 1 je nejjednodušší konstantní funkce).

Do O se píše tzv. horní odhad, tedy „nikdy to nemůže být horší“ (ale když budeme mít štěstí, mohlo by být i menší). Existují i jiné, ale když se chceme chlubit kvalitou našeho řešení, těžko budeme chtít tvrdit: „určitě to nikdy nepoběží rychleji než n99“.

Paměťová složitost našeho algoritmu je zcela očividně konstantní – máme jen dvě proměnné na čísla, v nich provádíme veškeré operace.

Časová bude chtít trošku odhadovat. Jednak, co je velikostí vstupu? Tou bude třeba součet velikostí obou čísel, tedy n=x+y (délka výpočtu totiž nezávisí na počtu čísel na vstupu – tam je jich vždy stejně – ale na jejich hodnotách). V každém kroku se jedno z čísel sníží alespoň o 1 a nikdy se nedostaneme do záporných čísel. Takže bychom mohli klidně psát, že časová složitost je O(n) – určitě náš program nepoběží déle.

To je sice pravda, ale moc jsme se nevytáhli – stejnou časovou složitost měl i původní algoritmus se zkoušením všech potenciálních dělitelů. Tak co teď? Vymyslet lepší algoritmus? Ne, my na to půjdeme šalamounsky – vymyslíme lepší důkaz.

Opět předpokládejme, že přecházíme od dvojice x,y ke dvojici z,y, kde z=x mod y. Dokážeme, že z≤ x/2, takže každým krokem algoritmu se aspoň jedno z čísel zmenší aspoň dvakrát. Přitom kroků, kdy se dvakrát zmenšilo původní x, může být celkem nejvýš trunc(log2 x), a analogicky pro y. Proto je celková časová složitost O(log2 x + log2 y) = O(log n).

A proč je z≤ x/2? Rozebereme dvě možnosti: buďto je y≤ x/2, ale pak stačí využít toho, že zbytek po dělení je vždy menší než dělitel, tedy z < y ≤ x/2. A nebo je y>x/2, ale pak z = x-y ≤ x-x/2 = x/2.

Několik špatných pokusů

Minulá část obsahovala popis, jak vypadá správné řešení. Nyní zmíníme několik chyb, se kterými se celkem pravidelně při opravování setkáváme.

Jednou (a asi nejvážnější) z nich je, když nám přijde pouze zdrojový kód, který je občas (ale sporadicky) komentovaný a není k tomu žádný popis. Popis má být hlavní částí řešení, zdrojový kód pouze doplňkem.

Opačný extrém je příliš podrobné (a komplikované) vyprávění či slohová práce. Opravdu neplatí, že čím delší text, tím více bodů. Úlohy v KSP jsou dělané tak, aby se daly jednoduše popsat na stránku nebo dvě. Řešení o 20 stranách je tak dlouhé, že v něm prostě něco špatně být musí.

Další, celkem běžný, problém je špatně pochopitelný popis. Zkuste si text po sobě přečíst – s vědomím, že člověk, který ho bude číst, možná vaše řešení vůbec nezná a nic o něm neví. Nejlépe s odstupem několika hodin či dní. Do této oblasti patří i pravopis (někdy špatně umístěná (nebo chybějící) čárka ve větě může úplně změnit význam) a v případě psaní ručně i čitelnost rukopisu (za to, co nepřečteme, body nedáme).

A, samozřejmě, plný počet bodů nedáváme ani za řešení, které nefunguje.

Co dělat když…

Mnoho lidí KSP řešit nezačne, přestože by je třeba i bavilo. Většinou proto, že narazí na nějaký problém, který ale obvykle není tak neřešitelný, jak vypadá.

Pokud vám některá úloha přijde příliš těžká, nezoufejte. Snažíme se dávat i „šťavnaté“ úložky pro pokročilejší řešitele – ne však všechny, některé jsou lehké (od tohoto ročníku jsme zavedli značení, u některých je značka, že si myslíme, že by měla jít snadno vyřešit). Zkuste ty. Časem se vám úložky budou zdát lehčí.

A co v případě, když vás napadne jen pomalé řešení? Je na něm sice jasně vidět, že jsme při zadávání mysleli na něco rychlejšího, ale vy na to ne a ne přijít. Rozhodně napište alespoň to pomalé – zatímco za nefunkční řešení nedáváme skoro nic, za pomalejší řešení dáváme docela dost (tedy, podle toho, jak moc pomalejší je).

Nakonec malý tip. Zkuste začít řešit s předstihem. Velmi pomáhá, když je pár dní času na to, aby pěkné řešení „napadlo“.