První série jedenáctého ročníku KSP

Řešení úloh

11-1-1 Cypherština (Zadání)

Řešitelé této úlohy se rozdělili vesměs na 2 skupiny. První skupina řešitelů si uvědomila, že ze získaných vztahů mezi písmeny si mohou postavit graf a problém uspořádání písmen se změní na problém topologického třídění grafu či hledání nejdelší cesty v grafu. Většina řešitelů v této skupině měla také úlohu víceméně správně. Řešitelé z druhé skupiny zpravidla získali vztahy mezi jednotlivými písmeny (nebo mezi skupinami písmen) a poté se pokoušeli nějak tyto informace spojovat, aby získali výslednou abecedu. V této skupině se úspěšných řešitelů vyskytlo skutečně pomálu. Jinak obecným nešvarem mnoha řešení byl nedostatečný popis algoritmu (z popisu algoritmu má být už jasné, jak program funguje bez nutnosti studia zdrojového textu), chybějící odhad časové a paměťové složitosti či nepřítomnost zdůvodnění správnosti algoritmu.

Teď už tedy ke správnému algoritmu. Je celkem zřejmé (z definice lexikografického uspořádání), že ze dvou sousedních slov získáme informaci maximálně o pořadí dvou písmen (pokud bude první slovo začátek druhého – třeba jako auto, autobus – nezjistíme nic). Budou to první odlišná písmena na stejné pozici (např. ze slov list, limonáda zjistíme, že s < m). Tyto zjištěné nerovnosti si budeme v orientovaném grafu (písmena jsou vrcholy) representovaném maticí sousednosti zaznamenávat jako hrany z menšího písmene do většího. Po projití celého slovníku tedy budeme mít v tomto grafu všechny získatelné nerovnosti. Mimoto si také budeme pamatovat, která písmena se už v textu vyskytla, abychom mohli poznat, zda je slovník úplný. V dalším textu už vrcholy písmen, která se v textu nevyskytla nebudeme uvažovat. Také si u každého vrcholu budeme pamatovat, kolik do něj vede hran.

Teď nastává druhá fáze – samotné vytváření abecedy. Nalezneme všechny vrcholy, do kterých nevede hrana. Budou to tedy ta písmena, pro která neexistuje menší písmeno. Pokud je takové písmeno právě jedno, je zřejmě nejmenší a přidáme ho tedy jako další písmeno do abecedy (na počátku je abeceda prázdná). Pokud není takové písmeno žádné, neexistuje zjevně nejmenší písmeno a ve slovníku je chyba (Tuto alternativu jste ve svých řešeních nemuseli uvažovat, protože byla zaručena bezespornost slovníku.). Pokud je takových písmen více, nemáme možnost, jak písmena mezi sebou srovnat (nevedou mezi nimy žádné hrany), a proto neexistuje jednoznačné řešení. Pokud se nám podařilo úspěšně přidat do abecedy písmeno, odebereme odpovídající vrchol z grafu a hrany z něho vycházející. Tím se nám bez vstupních hran ocitne vrchol zastupující následující písmeno. Můžeme tedy zase zopakovat druhou fázi, čímž získáme druhé písmeno abecedy, pak třetí, čtvrté a tak dále. Nakonec budeme mít takto seřazenu celou abecedu.

Algoritmus bude mít časovou složitost O(N + A2), kde N je velikost slovníku a A je počet písmen v abecedě. Potřebujeme totiž postupně přečíst celý slovník – O(N) – pro každé písmeno výsledné abecedy najít vrchol bez vstupních hran – O(A) (díky tomu, že si pamatujeme, kolik hran do vrcholu vede) – a vyřadit všechny hrany z tohoto vrcholu (těch bude maximálně A). Dohromady tedy O(A2). Paměťová složitost bude O(A2). Potřebujeme si totiž pamatovat matici sousednosti grafu. Správnost algoritmu byla zdůvodněna již v popisu.

Program je přímou implementací algoritmu, a proto není myslím třeba zvláštního popisu.

Program

Jan Kára

11-1-2 Quad rant (Zadání)

Zopakujme si pravidla kódování obrázku: je-li na vstupu 0 nebo 1, pak obrázek je celý černý nebo bílý, je-li tam 2, pak následují čtyři po sobě jdoucí kódy čtvrtin původního obrázku v pořadí levá horní, pravá horní, levá dolní a pravá dolní čtvrtina. Tyto čtvrtiny jsou popsány stejným kódem.

Našim úkolem je takto zadaný obrázek převést na obrázek otočený o 90° proti směru hodinových ručiček (tj. vypsat kód takto otočeného obrázku). Je zřejmé, že pokud je obrázek daný kódem 0 nebo 1 (jednolitý obrázek) je výsledkem po otočení také kód 0 nebo 1. V opačném případě je tvořen čtyřmi čtvrtinami a my je přesuneme o 90° proti směru hodinových ručiček. Tím se sice čtvrtiny dostanou na své místo, ale ouha jsou otočené o 90 stupňů po směru hodinových ručiček. Nezbývá nám než, otočit je o 90° proti směru, což provedeme zase použitím výše popsaného algoritmu.

Algoritmus je sice jednoduchý, ale lze ho implementovat více způsoby – efektivně a méně efektivně. Hlavní chybou, které se mnozí řešitelé dopouštěli, bylo, že orotovaný kód sestavovali z řetězců vrácených z rekurzivního volání funkce na jednotlivé čtvrtiny, přičemž spojování řetězců neprobíhalo v konstantním čase, ale v čase úměrným délce jednotlivých spojovaných řetězců. To vedlo na algoritmy s časovou složitostí O(n· log n) až O(n2), kde n je délka kódu k orotování.

Tomu se dalo vyhnout sestavením stromu popisujícího obrázek. Uzel stromu, který byl listem, měl hodnotu buď 0 nebo 1 (jednolitý čtvereček). Uzel, ve kterém se strom větvil, měl hodnotu 2 a obsahoval 4 ukazatele na uzly popisující jednotlivé čtvrtiny obrázku v daném pořadí. Vypsaní orotovaného kódu se pak dá provést projitím tohoto stromu, kde v místě větvení probíráme větve v takovém pořadí, v jakém mají být vypsány přerovnané čtvrtiny obrázku.

Časová složitost tohoto algoritmu je lineární O(n), v lineárním čase strom zkonstruujeme, v lineárním ho projdeme, protože všech uzlů je stejně jako znaků kódu, tedy n. Paměťová složitost je také lineární O(n), tj. počet uzlů stromu. Lépe to už nejde, protože každý znak musíme alespoň jednou vypsat, což způsobí, že časová složitost libovolného algoritmu řešícího tuto úlohu je alespoň lineární. Správnost a konečnost algoritmu je evidentní.

Program

Aleš Přívětivý

11-1-3 Magiášův Tfujtajxl (Zadání)

Správných řešení této úlohy se nám sešlo pomálu – většina programů totiž nevyhledávala správně požadované slovo TFUJTAJXL. Když je v zadání uveden požadavek na minimální datovou paměť, neznamená to žádné omezení na délku programu. Téměř všichni jste načítali Magiášův text ze souboru a potřebovali jste pro to proměnnou pro přístup k souboru a proměnné pro načtená písmena či slova. Načítat data ze souboru se dá, aniž by jste přistupovali k souboru takto: V programu používejte příkazy pro načítání ze standartního vstupu, tj. klávesnice a po přeložení programu spusťte program příkazem tfujtajxl.exe <vstup.txt, který zařídí přesměrování standartního vstupu programu na soubor vstup.txt, v němž jste si napsali testovací věty. Tento systém přesměrování standartního vstupu (obdobně s > přesměrování std. výstupu) se dá použít snad na všech běžných operačních systémech (MS-DOS, Unix, …). Nikdo po vás nechtěl výpisy čísel řádků, které splňovaly 3 zadaná kritéria. Stačilo pouze např. vypsat nalezeno a skončit program. Algoritmus, který jste většinou použili, používal pole, do něhož jste načetli řádek, a pole s hledaným řetězcem TFUJTAJXL. Délka řádku však nebyla omezena, a tak načítání celého řádku nebylo možné. Vaší nejčastější chybou bylo nenalezení řádků obsahujících slova jako TFTFUJTAJXL či TFUJTFUJTAJXL. Nemůžete nikdy hledat řetězce tak, že testujete po jednotlivých písmenech vstup a první písmeno hledaného řetězce a poté, co se písmena shodují testovat na shodu druhé hledané písmeno a v případě neshody začínat znovu od prvního hledaného písmena.

Správné řešení úlohy je zkonstruovat tzv. vyhledávací stavový automat. To je (zjednodušeně) program, který obsahuje proměnnou stav, která spolu s právě načteným znakem vstupu určuje další chování programu a změnu obsahu proměnné stav. Proměnná stav může nabývat hodnot 0,T,F,U,J,T1,A,J1,X,L,XX. Soustřeďme se teď pouze na první kritérium, tj. vyhledat řádek s textem TFUJTAJXL. Musíme nadefinovat tzv. přechodovou funkci automatu, neboli nadefinovat pro každou možnou hodnotu proměnné stav a každý možný načtený znak, jak se má změnit proměnná stav.

Algoritmus automatu prohledávajícího jeden vstupní řádek pak vypadá takto:

K1: stav:=0;
K2: načti(znak);
K3: case stav of
     0: case znak of
          't': stav:=t;
          end of line: stav:=XX;
          else stav:=0;
     t: case znak of
          'f': stav:=f;
          't': stav:=t; { ...TTfujtajxl }
          end of line: stav:=XX;
          else stav:=0;
     f: case znak of
          'u': stav:=u;
          't': stav:=t; { ...TFTfujtajxl }
          end of line: stav:=XX;
          else stav:=0;
     u: case znak of 
          'j': stav:=j;
          't': stav:=t; { ...TFUTfujtajxl }
          end of line: stav:=XX;
          else stav:=0;
     j: case znak of 
          't': stav:=t;
          end of line: stav:=XX;
          else stav:=0;
    t1: case znak of 
          'a': stav:=a;
          'f': stav:=f; { ...TFUJTFujtajxl }
          't': stav:=t; { ...TFUJTTfujtajxl }
          end of line: stav:=XX;
          else stav:=0;
     a: case znak of 
          'j': stav:=j;
          't': stav:=t; { ...TFUJTATfujtajxl }
          end of line: stav:=XX;
          else stav:=0;
    ...
    end;
K4: goto K2;

Stavy j1 a x jsou analogické např. stavu a; stav l je tzv. koncový stav, kdy automat např. vypíše hlášku o nalezení řetězce a přejde např. do stavu 0 nebo jeho činnost skončí. Stav XX je taktéž koncový stav automatu, kdy vypíšeme např. hlášku o nenalezení řetězce a skončíme.

Toto byl automat pro hledání řetězce TFUJTAJXL na jednom řádku. Chceme ho teď rozšířit na celý soubor řádek. To učiníme snadno přepsáním všech přechodů při načtení znaku end of line místo XX do stavu 0 a dopsáním přechodu ve všech stavech, které nejsou koncové (l, XX), při načtení znaku konec souboru do stavu XX. Chceme-li nyní rozšířit automat pro 2. kritérium, tj. řádek nesmí obsahovat slovo začínající znakem Q, musíme doplnit do automatu ve všech nekoncových stavech přechod do stavu M při načtení mezery a dále doplnit stavy M a YY:

 M: case znak of
      end of line: stav:=0;
      end of file: stav:=XX;
      ' ': stav:=M;
      'q': stav:=YY;
      else stav:=0;
YY: case znak of
      end of line: stav:=0;
      end of file: stav:=XX;
      else stav:=YY;

Ve stavu YY čteme znaky až do konce řádky, neboť na řádce se slovem začínajícím Q určitě zaklínadlo není. Ještě musíme ošetřit, že za řetězcem TFUJTAJXL nebude na téže řádce slovo na Q, tedy dopíšeme ošetření do koncového stavu l takto:

 l: case znak of
      end of line: stav:=TRUE;
      end of file: stav:=TRUE;
      mezera: stav:=TM;
      else stav:=l;
TM: case znak of
      end of line stav:=TRUE;
      end of file stav:=TRUE;
      ' ': stav:=Tmezera;
      'q': stav:=YY;
      else stav:=l;

Zbývá ošetřit první znak na řádce. Tomu nemůže předcházet mezera a může to být začátek slova na Q. Toto ošetření provedeme např. doplněním dalšího stavu, který prohlásíme za počáteční:

First: case znak of
      end of line: stav:=0;
      end of file: stav:=XX;
      Q: stav:=YY;
      t: stav:=t;
      else stav:=0;

Posledním kritériem, které musel splňovat nalezený řádek byl počet znaků na řádku dělitelný třemi. Pokud by nám nezáleželo na počtu proměnných, tak bychom to jednoduše zařídili tak, že bychom při každém načtení znaku zvýšili počitadlo znaků o 1. Ve stavu First bychom ho nulovali a ve stavu TRUE bychom otestovali, zda je toto číslo dělitelné třemi. Toto řešení ale vyžaduje další velikou proměnnou, neboť nevíme, jak dlouhé řádky jsou na vstupu. Abychom ušetřili datovou paměť, stačí nám pouze vědět, jaký je zbytek po dělení počtu znaků na řádce třema, tedy hodnoty 0, 1, 2. Nechceme-li zavádět další proměnnou, zařídíme to zvětšením počtu stavů na skoro trojnásobek: hodnotu si budeme pamatovat stavem. Stavy, v nichž ještě můžeme na řádce nalézt zaklínadlo, rozepíšeme podle následujícího příkladu pro stav t:

t_0: case znak of
      f: stav:=f_1;
      t: stav:=t_1;
      end of line: stav:= XX;
      else stav:=0_1;
t_1: case znak of
      f: stav:=f_2;
      t: stav:=t_2;
      end of line: stav:= XX;
      else stav:=0_2;
t_2: case znak of
      f: stav:=f_0;
      t: stav:=t_0;
      end of line: stav:= XX;
      else stav:=0_0;

Nyní už máme automat, který se zastaví ve stavu TRUE, pokud ve vstupním textu existuje řádka splňující všechna 3 kritéria. Vidíme, že jeho triviální implementace v Pascalu zabírá 2 proměnné: znak a stav. Proměnná stav není potřeba, neboť místo cyklu s příkazem case, můžeme použít příkazů goto, kterými skočíme přímo do cílového stavu, tedy každý příkaz stav:=A nahradíme goto A. V programu nám tedy zbyde poslední proměnná na načtení znaku ze vstupu. Když bychom chtěli a programovací jazyk nám to umožnil, v programu bychom se i této poslední proměnné zbavili nahrazením načtení znaku do proměnné a následných podmínek jedním složeným podmíněným příkazem, např v jazyce C by to byl switch(getchar()).

Popis programu: Vzhledem k tomu, ze jazyk Pascal nemá podporu maker, je program napsán v jazyce C, kde využíváme preprocesoru k výraznému zkrácení zdrojového kódu. Většina stavů, vyskytujících se v programu kvůli dělitelnosti třemi po trojicích, se pak napíše jedním makrem. Na ostatní přechody jsou použita makra G a G1, která se liší jen načítáním vstupu do proměnné c. Chytré hlavy si jistě poradí s přepsáním programu tak, aby se proměnná c nepoužila.

Časová a paměťová složitost: Každý znak vstupu čteme jednou a přejdeme do jiného stavu po vyhodnocení maximálně čtyř podmínek, výsledná složitost je tedy O(n). Spotřeba paměti je 1 znak (byte), bez níž se obecně neobejdeme, neboť musíme někam načíst vstup.

Program

Martin `Mafi' Bělocký

11-1-4 Sibylla 98 (Zadání)

Řešení podúlohy a) je velice jednoduché: stačí si od věštírny pro každý předmět nechat nadiktovat, zda se má do batohu umístit či nikoliv a nakonec otestovat, jestli to dalo požadovanou hmotnost. To přesně činí tento program:

   #include <stdio.h>
   #include <oracle.h>
 
   int main(void)
   {
     int n,k,i;
     scanf("%d%d", &n, &k);
     while (n--)
       {
         scanf("%d", &i);
         k -= i * oracle(1);
       }
     return !k;
   }

Důkaz správnosti: Posloupnosti odpovědí věštírny v tomto programu přesně odpovídají možnostem, jak předměty vybrat a akceptování této posloupnosti programem přesně odpovídá tomu, že předměty batoh zcela zaplní. Proto program odpoví ano (1) ⇔ (podle definice Sibylly) existuje akceptovaná posloupnost odpovědí orákula ⇔ (jak již víme) existuje množina předmětů, které batoh zaplní.

Časová složitost algoritmu je O(n), jelikož každý prvek vstupu zpracujeme právě jednou. Paměťová složitost je konstantní, tedy O(1).

S úlohou b) je to poněkud složitější. Většinu z vás sice napadlo, že stačí generovat všechny možnosti, jak mohlo orákulum odpovědět, a testovat, jestli je některá z nich správná, ale často jste přehlédli několik drobností:

A jak na to tedy půjdeme? Inu, nejdříve si původní nedeterministický program N(x) (x je posloupnost čísel na vstupu) krapet upravíme:

  1. Z původního orákula uděláme orákulum binární, které vždy odpovídá buďto nulou nebo jedničkou. To lze, protože každé číslo si můžeme nechat poradit po bitech a v případě, že vyjde více než daná horní mez, prostě příslušnou větev výpočtu zrušit s výsledkem 0. A jak určíme počet bitů, které nám má orákulum prozradit? Třeba tak, že se za každým bitem ještě orákula zeptáme, zda máme pokračovat či nikoliv.
  2. Do programu doplníme počítadlo příkazů a přidáme parametr T, který bude udávat, kolik příkazů smíme nejvýše provést. Pokud tento počet překročíme, vrátíme nulu.
  3. Každý orákulový dotaz nahradíme prostým přečtením jednoho bitu z čísla R.

Tímto postupem program N(x) upravíme na program N'(x,R,T) a tvrdíme, že N(x)=1 právě tehdy, když existují nezáporná čísla R a T taková, že N'(x,R,T)=1. Důkaz: První úprava evidentně správnost programu nemění. Je-li N(x)=1, pak podle definice nedeterministického výpočtu existuje větev výpočtu (to jest posloupnost odpovědí orákula, námi zakódovaná v čísle R), která vrátí jedničku. Tato větev ovšem také musí skončit, a to za nějakých T kroků, což však přesně odpovídá tomu, že N'(x,R,T)=1.

Nyní již zbývá jenom napsat program, který bude postupně procházet všechna T počínaje nulou, pro každé z nich vygeneruje všechna možná R (0 ≤ R < 2T, jelikož počet volání orákula je maximálně roven počtu kroků programu N') a otestuje, zda N'(x,R,T) je nenulové. Jestliže taková R, T nalezneme, pak dle předchozího tvrzení je i N(x)=1. Opačně, pokud N(x)=1, pak taková R, T existují, a proto je nalezneme (zkoušíme všechny možnosti a každou z nich zpracujeme v čase O(T)).

Tím jsme dokázali, že deterministickými algoritmy lze spočítat totéž, co nedeterministickými (odhlédneme-li ovšem od poločasu rozpadu našeho počítače).

[Jiná možnost je dívat se na jednotlivé stavy programu (to jest pozice v programu plus obsah všech proměnných) jako na vrcholy nějakého grafu, na přechody mezi stavy jako na hrany tohoto grafu a na možné průběhy výpočtu jako na cesty začínající v nějakém pevném počátečním vrcholu. Deterministickému výpočtu odpovídá, že z každého vrcholu vychází maximálně jedna hrana, v případě nedeterministických algoritmů jich může být i více. Ptáme se tedy, zda pro daný graf existuje cesta, která vede do vrcholu, v němž se vrací výsledek rovný jedné. Jenže tento graf může být nekonečný, takže nám nezbývá, než jej prohledávat do šířky a vrcholy i hrany generovat tak, jak jsou během prohledávání navštěvovány. Správnost plyne z těchže úvah jako správnost předchozího převodu.]

Martin Mareš