\gdef\mujnazevCS{Recenze knihy: Competitive Programming 4}
\gdef\mujnazevEN{Book Review: Competitive Programming 4}
\gdef\mujnazevPR{\mujnazevCS}
\gdef\mujnazevDR{\mujnazevEN}
\gdef\mujauthor{Pavel Stříž}

\bonushyper

\nazev{\mujnazevCS}

\nazev{\mujnazevEN}

\author{\mujauthor}

\Email{pavel@striz.cz}
\bigskip

\def\kapitola#1{\textbf{#1}}
\def\podkapitola#1{\textit{#1}}
\fboxrule=0pt \fboxsep=0pt

\noindent
Steven Halim, Felix Halim, Suhendry Effendy: Competitive Programming 4, Book 1 (xxx + 1--299 pp., tedy 329 stran PDF), Book 2 (viii + 273--616 pp., tedy 352 stran PDF). 
%\vspace{3cm}
%obrázek úvodních stran + možná ještě něco, nebo nic
\smallskip

\hfill Motto knihy, repeat for a~lifetime:\par\noindent
\hfill \textit{Study; Practice; Rehearse; Dress Rehearse; Perform.}%
\smallskip


%How to tackle this problem?
%Soutěžní programování není tenis ani šachy, jeden na jednoho, nebo fotbal či bridž, kde hrají týmy proti sobě. Pro mne to byly vždy programátorské výzvy kladené na jednotlivce a úvod do algoritmů, tedy bájný svět kuchařek.

Knih k~soutěžnímu programování najdeme řadu, všechny hezké (souhrn viz str.\,50 první knihy), zde zmíněná kniha patří k~nejnovějším. Nepoužívá pseudo-algoritmy, až na výjimky, ale ukazuje přímá řešení. Obsahuje komentované příklady, neřešené příklady s~řešením na konci kapitol a~také těžší příklady bez řešení, uváděné s~hvězdičkou. 

Cílem knihy je připravit na dva typy soutěží, IOI (The International Olympiad in Informatics, \url{https://ioinformatics.org}), to je spíš náplní první knihy a~ICPC (The International Collegiate Programming Contest, \url{https://icpc.global}), to je rozšiřující náplní druhé knihy. První soutěž je do 18 let, pro jednotlivce, druhá soutěž je pro týmy vysokoškoláků. Co mě zaujalo, že na IOI opouští Pascal, ale i~C. To mi u~C přijde divné.

Kniha se odkazuje na zadání na serverech UVa (nově Online Judge; \url{https://uhunt.onlinejudge.org/}) a~Kattis (\url{https://open.kattis.com}). Příkla\-dy obsahují \textsl{Entry level}, tedy doporučený první příklad kategorie; \mbox{\textsl{Must try *}}, tedy takové, které by si čtenář měl zkusit a~pak ostatní doporučené příklady, řekněme bonusové. Autoři dohromady vyřešili 3458 úloh z~těchto serverů, a~tipy, jak je vyřešit, zveřejnili na \url{https://cpbook.net/methodstosolve}.

Řešené příklady, častokrát pro 4 programovací jazyky, lze nalézt na Git\-Hubu jednoho z~autorů (\url{https://github.com/stevenhalim/cpbook-code}), jazyky jsou C++, Python, Java a~OCaml. Co mě tolik nepřekvapilo je, že na soutěžích ubývá příkladů s~velkými čísly.

Podpůrné stránky knih jsou \url{https://cpbook.net} a~na vizualizaci algoritmů připravili server \url{https://visualgo.net}.
\smallskip

Velmi stručně představím jednotlivé kapitoly.

\kapitola{Kapitola 1:}
\podkapitola{Introduction.}
Obsahuje tipy a~základní praktiky soutěžního programování, které se liší od běžného programování, např. načtení všech STL knihoven C++ místo vybraných (\texttt{bits/stdc++.h}), užívání zkratek a~konstant a~též \texttt{using namespace std;}.

\kapitola{Kapitola 2:}
\podkapitola{Data Structures and Libraries.}
Kapitola představuje lineární a~nelineární datové struktury. Velká část kapitoly se věnuje binárním rozhodovacím stromům -- Self-balancing Binary Search Tree (AVL, RB). U~C++ se zde poprvé setkáváme s~načtením struktur mimo základní STL (\texttt{bits/extc++.h}). Co mě trochu zaskočilo, že podrobně komentují vlastní datové struktury v~tak brzké fázi knihy.

\kapitola{Kapitola 3:}
\podkapitola{Problem Solving Paradigms.}
Tato kapitola uvádí základní strategie řešení úloh: Complete Search, Divide and Conquer, Greedy approach a~Dynamic Programming.

\kapitola{Kapitola 4:}
\podkapitola{Graph.}
Kapitola je úvod do teorie grafů, byť tedy rozsáhlá. Zaujalo mě užití upravené verze Dijkstrova algoritmu a~převedení úlohy mincí (Coin-Change) na hledání nejkratších cest v~orientovaném acyklickém grafu (zkr. DAG), viz str.\,253 a~254. Zde je grafická ukázka.

\noindent
\fbox{\includegraphics[page=283, trim=5.7cm 9.6cm 4.5cm 15cm, clip, width=\textwidth]{cp4-1.pdf}}%

V~poznámce pod čarou je odkaz na článek jednoho z~autorů, kde pracoval s~velkými grafy se 411 milióny vrcholů a~31 miliardami hran.

\kapitola{Kapitola 5:}
\podkapitola{Mathematics.}
Tato kapitola se hlouběji zabývá úlohami matematiky (teorie čísel, práce s~maticemi), kombinatoriky a~pravděpodobnosti. Jsou zde zmíněné odkazy na \url{https://projecteuler.net} a~\url{https://brilliant.org}, které obsahují nespočet úloh se zaměřením na matematiku. Speciálně na první projekt je stále častěji odkazováno v~souvislosti se zajímavými úlohami.

\kapitola{Kapitola 6:}
\podkapitola{String Processing.}
Práce s~textovými řetězci je náplní této kapitoly. Na str.\,364 zmiňují algoritmy, které v~knize nemají, ale považují je za důležité.

\kapitola{Kapitola 7:}
\podkapitola{(Computational) Geometry.}
Kapitola se zaměřuje na geometrii 0D až 3D, s~tím, že pro 3D je úloh nejméně, jak na soutěžích nebývají typické. Autoři zmiňují, že adaptovali algoritmy ze serveru \url{https://shygypsy.com/tools/}.

\kapitola{Kapitola 8:}
\podkapitola{More Advanced Topics.}
Kapitola zmiňuje těžké úlohy dynamického programování, průtoky sítí, ale také úlohy kategorie NP-úplné. Poslední podkapitola se věnuje rozložení těžkých úloh na menší, z~pohledu algoritmů na samostatně řešitelné.

\kapitola{Kapitola 9:}
\podkapitola{Rare Topics.}
Vůči dřívějším vydáním této knihy zbrusu nová kapitola. Zmiňuje atypické a~speciální úlohy. Došlo i~na Billa Gatese, neb jeho jediný odborný článek spadá k~úloze Pancake Sorting, viz str.\,551--553. Zaujala mě kapitola 9.30, tedy konstrukční úlohy: vytvoření magického čtverce pro velké $n$, podobně jako úloha rozmístění $N$ královen na šachovnici. Za zvláštní pozornost stojí úlohy interaktivní s~elektronickým systémem (kapitola 9.31), setkal jsem se s~tím u~úloh na bioinformatických soutěžích. 

Za velmi důležitou kapitolu považuji na str.\,590 tu poslední (9.34 Chapter Notes), tedy co autoři chtěli v~knize mít, ale nestihli to. To lze považovat za inspiraci k~dalšímu studiu nad rámec této knihy. 

Ze zajímavých knižních projektů, vhodné jako studijní pokračování pro adepty soutěžního programování, bych rád zmínil:

%{\small
\begin{itemize}
\itemsep=-1pt
\item Antti Laaksonen: \textit{Guide to Competitive Programming,} Springer, 2017. \\Web: TODO
\item Jörg Arndt: \textit{Matters Computational. Ideas, Algorithms, Source Code} (alias fxtbook), 2010. Web:  TODO
\item Joseph O'Rourke: \textit{Computational Geometry in C,} Cambridge University Press, 2nd edition, 1998.\\ Web: existuje? TODO
\end{itemize}
%}

Každá z~knih obsahuje seznam zdrojů, rejstřík i~medailónky tvůrců algoritmů. Je vysázena v~\TeX u. Kniha se nedá číst jako román, ale neměla by chybět v~(e-)knihovničce programátora jako užitečná referenční příručka.

Našince určitě potěší zmínění Vojtěcha Jarníka (byť tedy \uv{ě} je špatně vysázené jako \uv{\^e}) v~první knize na str.\,217 a~222, a~na Michala Foriška, viz zdroje [16] a~[17] na str.\,274 první knihy a~[15] na str.\,591 druhé knihy. Václav Chvátal nesměl chybět, viz druhá kniha, str.\,282, Art Gallery Problem. Kdysi jsem mu psal email kolem jeho příručky k~\LaTeX u, krásná vzpomínka. Na počest Vojtěcha Jarníka zmiňuji ukázku animace ze str.\,218 první knihy.\medskip

\noindent
\fbox{\includegraphics[page=248, trim=3.2cm 21.6cm 4.8cm 2.2cm, clip, width=\textwidth]{cp4-1.pdf}}%



