codebook.tex

\documentclass[a4paper,oneside,12pt]{article}
\usepackage[slovene]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{url}
\usepackage{graphicx}
\usepackage[usenames]{color}
\usepackage[reqno]{amsmath}
\usepackage{amssymb,amsthm,mathabx}
\usepackage{enumerate}
\usepackage{array}
\usepackage[bookmarks, bookmarksopen, bookmarksdepth=3, colorlinks=true,
  linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black,
  menucolor=black, runcolor=black, urlcolor=black, pdfencoding=unicode
]{hyperref}
\usepackage[
  paper=a4paper,
  top=2.5cm,
  bottom=2.5cm,
  textwidth=15cm,
]{geometry}

\usepackage{icomma}
\usepackage{units}
\usepackage{minted}
\usepackage{nameref}

\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\C{\mathbb{C}}
\def\Q{\mathbb{Q}}

\newenvironment{itemize*}%
{
\vspace{-6pt}
\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parskip}{2pt}
}
{\end{itemize}}

\newenvironment{description*}%
{
\begin{description}
\setlength{\itemsep}{0pt}
\setlength{\parskip}{2pt}
}
{\end{description}}

\newcommand{\mytitle}{Codebook}
\title{\mytitle}
\author{Jure Slak}
\date{\today}
\hypersetup{pdftitle={\mytitle}}
\hypersetup{pdfauthor={Jure Slak}}
\hypersetup{pdfsubject={}}

\newmintedfile[cppsource]{c++}{linenos=true, mathescape, xleftmargin=0.7cm,
                               fontsize=\scriptsize,baselinestretch=0.9,firstline=3}
\newmintedfile[cppheadersource]{c++}{linenos=true, mathescape, xleftmargin=0.7cm,
                                     fontsize=\scriptsize,baselinestretch=0.9,firstline=6}
\newmintedfile[pysource]{python}{linenos=true, mathescape, xleftmargin=0.7cm,
                                 fontsize=\scriptsize,baselinestretch=0.9}

\newcommand{\cpp}[1]{\cppsource{implementacija/#1}}
\newcommand{\hpp}[1]{\cppheadersource{implementacija/#1}}
\newcommand{\ull}{\texttt{unsigned long long}}
\newcommand{\lslice}[2]{\ensuremath{#1[:\! #2]}}
\newcommand{\rslice}[2]{\ensuremath{#1[#2 \!:]}}
\newcommand{\slice}[3]{\ensuremath{#1[#2 \!:\! #3]}}

\begin{document}

\thispagestyle{empty}

\vspace*{\fill}
\begin{center}
  \scalebox{6}{\texttt{Codebook}}\\[3ex]
  za ekipo \\[3ex]
  \scalebox{2}{Pitoni\textbf{++}}\\[4ex]
  Žiga Gosar, Maks Kolman, Jure Slak
  \vfill
  \parbox{0.75\textwidth}{
  \begin{itemize*}
    \item podrobno in pozorno preberi navodila
    \item pazi na \texttt{double} in \ull
    \item počisti podatke med testnimi primeri
    \item uporabi \texttt{vector.assign} ne \texttt{vector.resize} med primeri
    \item uporabi \texttt{cin.sync\_with\_stdio(false);}\\
      \texttt{cin.tie(nullptr);} in nikoli \texttt{endl} za hitrejši IO
    \item uporabi \texttt{numeric\_limits<tip>::max()} \\ ali \texttt{infinity()},
      \texttt{min()} za robne vrednosti
    \item uporabi \texttt{g++ -std=c++11 -Wall -pedantic -Wextra}
    \item v template dodaj
      algorithm,
      array,
      complex,
      cmath,
      functional,
      iostream,
      iomanip,
      limits,
      map,
      queue,
      set,
      stack,
      string,
      tuple,
      utility,
      vector,
      namespace std in cin zadeve.
      \item za izpis na fiksno število decimalk uporabi  \\ \texttt{cout
          \mbox{<}< fixed \mbox{<}< setprecision(6);}
      \item za lažji debug: \\
        \texttt{\#define~prn(x)~(cout~\mbox{<}<~\#x~\mbox{<}<~"~=~"~\mbox{<}<~(x)~\mbox{<}<~"\textbackslash
        n";)}
  \end{itemize*}}
  \vfill
  Avtor: Jure Slak, verzija: \today
\end{center}

\newpage

\tableofcontents

\newpage

\section{Grafi}
\label{sec:grafi}

\subsection{Topološko sortiranje}
\begin{description*}
  \item[Vhod:] Usmerjen graf $G$ brez ciklov. $G$ ne sme imeti zank, če pa jih ima, se
    jih lahko brez škode odstrani.
  \item[Izhod:] Topološka ureditev usmerjenega grafa $G$, to je seznam vozlišč v takem
    vrstnem redu, da nobena povezava ne kaže nazaj. Če je vrnjeni seznam krajši
    od $n$, potem ima $G$ cikle.
  \item[Časovna zahtevnost:] $O(V + E)$
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:] UVa 10305
\end{description*}
\cpp{grafi/topological_sort.cpp}

\subsection{Najdaljša pot v DAGu}
\begin{description*}
  \item[Vhod:] Usmerjen utežen graf $G$ brez ciklov in vozlišči $s$ in $t$. $G$ ne sme imeti zank, če pa jih ima, se
    jih lahko brez škode odstrani.
  \item[Izhod:] Dolžino najdaljše poti med $s$ in $t$, oz.\ $-1$, če ta pot ne
    obstaja. Z lahkoto najdemo tudi dejansko pot (shranjujemo predhodnika) ali
    najkrajšo pot (max $\to$ min).
  \item[Časovna zahtevnost:] $O(V + E)$
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:] UVa 103
\end{description*}
\cpp{grafi/longest_path_in_a_dag.cpp}

\subsection{Mostovi in prerezna vozlišča grafa}
\label{sec:bridge}
\begin{description*}
  \item[Vhod:] Število vozlišč $n$ in število povezav $m$ ter seznam povezav $E$
    oblike $u \to v$ dolžine $m$. Neusmerjen graf $G$ je tako sestavljen iz vozlišč z oznakami
    0 do $n-1$ in povezavami iz $E$.
  \item[Izhod:] Seznam prereznih vozlišč: točk, pri katerih, če jih
    odstranimo, graf razpade na dve komponenti in seznam mostov grafa $G$: povezav, pri
    katerih, če jih odstranimo, graf razpade na dve komponenti.
  \item[Časovna zahtevnost:] $O(V + E)$
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:] UVa 315
\end{description*}
\cpp{grafi/articulation_points_and_bridges.cpp}

\subsection{Močno povezane komponente}
\label{sec:scc}
\begin{description*}
  \item[Vhod:] Seznam sosednosti s težami povezav.
  \item[Izhod:] Seznam povezanih komponent grafa v obratni topološki ureditvi in
    kvocientni graf, to je DAG, ki ga dobimo iz grafa, če njegove komponente
    stisnemo v točke. Morebitnih več povezav med dvema komponentama seštejemo.
  \item[Časovna zahtevnost:] $O(V + E)$
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2012/2012_3kolo/zakladi}
\end{description*}
\cpp{grafi/strongly_connected_components.cpp}

\subsection{Najkrajša pot v grafu}

\subsubsection{Dijkstra}
\label{sec:dijkstra}
\begin{description*}
  \item[Vhod:] Seznam sosednosti s težami povezav in dve točki grafa. Povezave
    morajo biti pozitivne.
  \item[Izhod:] Dolžina najkrajša poti od prve do druge točke. Z lahkoto vrne
    tudi pot, glej kvadratično verzijo za implementacijo.
  \item[Časovna zahtevnost:] $O(E\log(E))$
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2013/2013_1kolo/wolowitz}
\end{description*}
\cpp{grafi/dijkstra.cpp}

\subsubsection{Dijkstra (kvadratičen)}
\label{sec:dijkstra-square}
\begin{description*}
  \item[Vhod:] Seznam sosednosti s težami povezav in dve točki grafa. Povezave
    morajo biti pozitivne.
  \item[Izhod:] Najkrajša pot med danima točkama, dana kot seznam vmesnih
    vozlišč skupaj z obema krajiščema.
  \item[Časovna zahtevnost:] $O(V^2)$, to je lahko bolje kot $O(E\log(E))$.
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2013/2013_1kolo/wolowitz}
\end{description*}
\cpp{grafi/dijkstra_square.cpp}

\subsubsection{Bellman-Ford}
\label{sec:bellman-ford}
\begin{description*}
  \item[Vhod:] Seznam sosednosti s težami povezav in točka grafa. Povezave
    ne smejo imeti negativnega cikla (duh).
  \item[Izhod:] Vrne razdaljo od dane točke do vseh drugih. Ni nič ceneje če
    iščemo samo do določene točke.
  \item[Časovna zahtevnost:] $O(EV)$
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2013/2013_1kolo/wolowitz}
\end{description*}
\cpp{grafi/bellman_ford.cpp}

\subsubsection{Floyd-Warhsall}
\label{sec:floyd-warshall}
\begin{description*}
  \item[Vhod:] Število vozlišč, število povezav in seznam povezav. Povezave
    ne smejo imeti negativnega cikla (duh).
  \item[Izhod:] Vrne matriko razdalj med vsemi točkami, $d[i][j]$ je razdalja
    od $i$-te do $j$-te točke. Če je katerikoli diagonalen element negativen,
    ima graf negativen cikel. Rekonstrukcija poti je možna s pomočjo dodatne
    tabele, kjer hranimo naslednika.
  \item[Časovna zahtevnost:] $O(V^3)$, dober za goste grafe.
  \item[Prostorska zahtevnost:] $O(V^2)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2013/2013_1kolo/wolowitz}
\end{description*}
\cpp{grafi/floyd_warshall.cpp}

\subsection{Minimalno vpeto drevo}
\label{sec:mst}

\subsubsection{Prim}
\label{sec:mst-prim}
\begin{description*}
  \item[Vhod:] Neusmerjen povezan graf s poljubnimi cenami povezav.
  \item[Izhod:] Vrne ceno najmanjšega vpetega drevesa. Z lahkoto to zamenjamo z
    maksimalnim (ali katerokoli podobno operacijo) drevesom.
  \item[Časovna zahtevnost:] $O(E\log(E))$, dober za goste grafe.
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:] UVa 11631
\end{description*}
\cpp{grafi/prim_minimal_spanning_tree.cpp}

\subsubsection{Kruskal}
\label{sec:mst-kruskal}
\begin{description*}
  \item[Vhod:] Neusmerjen povezan graf s poljubnimi cenami povezav.
  \item[Izhod:] Vrne ceno najmanjšega vpetega drevesa. Z lahkoto to zamenjamo z
    maksimalnim (ali katerokoli podobno operacijo) drevesom.
  \item[Časovna zahtevnost:] $O(E\log(E))$, dober za redke grafe. Če so povezave
    že sortirane, samo $O(E \alpha(V))$.
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:] UVa 11631
\end{description*}
\cpp{grafi/kruskal_minimal_spanning_tree.cpp}

\subsection{Najnižji skupni prednik}
\label{sec:lca}
\begin{description*}
  \item[Vhod:] Drevo, podano s tabelo staršev. Vozlišče je koren, če je starš
    samemu sebi. Za queryje najprej potrebuješ pomožno tabelo skokov na višja
    vozlišča in tabelo nivojev.
  \item[Izhod:] Za dani vozlišči $u$ in $v$, vrne njunega najnižjega skupnega
    prednika, to je tako vozlišče $p$, da je $p$ leži na poti od $u$ do korena
    in od $v$ do korena, ter je najdlje stran od korena drevesa.
  \item[Časovna zahtevnost:] $O(\log n)$ na query, z $O(n\log n)$
    predprocesiranja.
  \item[Prostorska zahtevnost:] $O(n\log n)$
  \item[Testiranje na terenu:] \url{http://www.spoj.com/problems/LCA/}
\end{description*}
\cpp{grafi/lowest_common_ancestor.cpp}

\subsection{Najširša pot med med vsemi pari vozlišč}
\label{sec:all-pairs-widest-path}
\begin{description*}
  \item[Vhod:] Utežen usmerjen graf $G$ z $n$ vozlišči.
  \item[Izhod:] $n\times n$ matrika, ki za vsak par vozlišč pove, koliko je
    širok najožji del najširše poti med tema vozliščema; ie. za vsak par vozlišč
    pove, kako širok je bottleneck med njima.
  \item[Časovna zahtevnost:] $O(EV)$
  \item[Prostorska zahtevnost:] $O(V+E)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2016/2016_1kolo/bottleneck}
\end{description*}
\cpp{grafi/all_pairs_widest_path.cpp}

\subsection{Največji pretok in najmanjši prerez}
\label{sec:maxflow}

Če imamo omrežje s dopustnimi kapacitetami na povezavah, potem max flow pove,
koliko največ lahko teže skozi od sourca $s$ do sinka $t$. Min cut je najmanjša
vsota tež povezav, ki jih moramo odstraniti, da se $s$ in $t$ popolnoma ločita.
Ti dve vrednosti sta enaki.

\subsubsection{Ford-Fulkerson}
\label{sec:maxflow-ff}
\begin{description*}
  \item[Vhod:] Matrika kapacitet dimenzij $n\times n$ (tj.~matrika sosednosti
    grafa z $n$ vozlišči, kjer so vrednosti dopustni pretoki povezav). Vse
    kapacitete morajo biti nenegativne. Hitrejša (in dajlša) verzija tega
    algoritma je Edmonds-Karpov algoritem.
  \item[Izhod:] Vrne maksimalen pretok od $s$ do $t$, ki je po vrednosti enak
    minimalnemu prerezu. Konstruira tudi matriko pretoka. Če pot od $s$ do $t$
    sploh ne obstaja vrne 0.
  \item[Časovna zahtevnost:] $O(Ef)$
  \item[Prostorska zahtevnost:] $O(V^2)$
  \item[Testiranje na terenu:]
    \href{http://putka.upm.si/tasks/2016/2016_3kolo/deske}{UPM 2016, 3.~kolo deske}
\end{description*}
\cpp{grafi/ford_fulkerson_maximal_flow.cpp}

\subsubsection{Edmonds-Karp}
\label{sec:maxflow-edmonds-karp}
\begin{description*}
  \item[Vhod:] Matrika kapacitet dimenzij $n\times n$ (tj.~matrika sosednosti
    grafa z $n$ vozlišči, kjer so vrednosti dopustni pretoki povezav). Graf je
    lahko (in ponavadi tudi je) usmerjen. Vse kapacitete morajo biti
    nenegativne.
  \item[Izhod:] Vrne maksimalen pretok od $s$ do $t$.
    Konstruira tudi matriko pretoka. Če pot od $s$ do $t$
    sploh ne obstaja vrne 0.
  \item[Časovna zahtevnost:] $O(V E^2)$
  \item[Prostorska zahtevnost:] $O(V^2)$
  \item[Testiranje na terenu:] UVa 820,
    \href{http://putka.upm.si/tasks/2016/2016_3kolo/deske}{UPM 2016, 3.~kolo deske}
\end{description*}
\cpp{grafi/edmonds_karp_maximal_flow.cpp}

\subsection{Največje prirejanje in najmanjše pokritje}

\subsubsection{Največje prirejanje v neuteženih dvodelnih grafih}
\label{sec:mbm}
V angleščini: \emph{maximum cardinality bipartite matching} (če bi dodali še
kakšno povezavo bi se dve stikali) in \emph{minimum vertex cover} (če bi vzeli
še kakšno točko stran, bi bila neka povezava brez pobarvane točke na obeh
koncih).
\begin{description*}
  \item[Vhod:] Dvodelen neutežen graf, dan s seznamom sosedov. Prvih \texttt{left} vozlišč je na
    levi strani.
  \item[Izhod:] Število povezav v $MCBM$ = število točk v $MVC$, pri $MVC$ vrne tudi neko minimalno
    pokritje. Velja tudi $MIS = V - MCBM$, $MIS$ pomeni \emph{maximum
    independent set}.
  \item[Časovna zahtevnost:] $O(VE)$
  \item[Prostorska zahtevnost:] $O(V + E)$
  \item[Testiranje na terenu:] UVa 11138
\end{description*}
\cpp{grafi/bipartite_matching.cpp}

\section{Podatkovne strukture}
\label{sec:ps}

\subsection{Statično binarno iskalno drevo}
\label{sec:bst}
\begin{description*}
  \item[Operacije:] Klasično uravnoteženo binarno iskalno drevo.
    \begin{itemize*}
      \item vstavi: doda +1 k countu na mestu \texttt{idx}
      \item briši: vrne \verb|true|/\verb|false| glede na to ali element
        obstaja in če, zmanjša njegov count za 1
      \item najdi $k$-tega: vrne indeks $k$-tega elementa. Zero based.
    \end{itemize*}
  \item[Časovna zahtevnost:] $O(\log(n))$ na operacijo
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2011/2011_finale/kitajci}
\end{description*}
\hpp{ps/static_binary_search_tree.h}

\subsection{Statično drevo segmentov}
\label{sec:static-segment-tree}
    Stuktura za delat poizvedbe o neki statistiki na podseznamih nekega seznama.
    Spodaj je implementacija za minimum, toda \texttt{min} in \texttt{inf} se
    lahko zamenjata s poljubno asociativno operacijo. Implementacija je
    iterativna in zato hitrejša kot tista spodaj.
\begin{description*}
  \item[Operacije:]
    \begin{itemize*}
      \item zgradi: naredi strukturo iz seznama
      \item spremeni: nastavi element na indeksu $i$ na vrednost $v$
      \item išči: vrne statistiko podseznama $[a, b)$. Pozor, polodprto!
    \end{itemize*}
  \item[Časovna zahtevnost:] $O(\log(n))$ na operacijo
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2016/2016_3kolo/maxer}
\end{description*}
\hpp{ps/static_segment_tree.h}

\subsection{Drevo segmentov}
\label{sec:segment-tree}
\begin{description*}
  \item[Operacije:] Segment tree deljen po fiksnih točkah z dinamično alokacijo
    node-ov. Ob ustvarjanju roota povemo razpon vstavljanja, končne točke so
    postavljene po celih številih.

    Za remove, ki ne zagotavlja nujno, da obstajajo stvari, ki jih
    brišemo, se je treba malo bolj potruditi. Najprej odstranimo vse na
    trenutnem levelu, kolikor lahko, nato pa se v vsakem primeru pokličemo
    dalje (če je še kaj za odstranit in node-i obstajajo). Prav tako lahko
    vrnemo število izbrisanih stvari.
    \begin{itemize*}
      \item vstavi neko vrednost na intervalu $[a, b]$
      \item briši na intervalu $[a, b]$
      \item dobi vrednost na intervalu $[a, b]$
      \item najdi $k$-tega
    \end{itemize*}
  \item[Časovna zahtevnost:] $O(\log(n))$ na operacijo
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:] \url{http://putka.upm.si/competitions/upm2014-finale/izstevanka}
\end{description*}
\hpp{ps/segment_tree.h}

\subsection{Avl drevo}
\label{sec:avl}
\begin{description*}
  \item[Operacije:] Klasično uravnoteženo binarno iskalno drevo.
    \begin{itemize*}
      \item vstavi: doda +1 k countu, če obstaja
      \item najdi: vrne pointer na node ali \verb|nullptr|, če ne obstaja
      \item briši: vrne \verb|true|/\verb|false| glede na to ali element
        obstaja in samo zmanjša njegov count (memory overhead, ampak who cares)
      \item najdi $n$-tega, vrne \verb|nullptr| če ne obstaja
    \end{itemize*}
  \item[Časovna zahtevnost:] $O(\log(n))$ na operacijo
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na
    terenu:]\url{http://putka.upm.si/competitions/upm2014-finale/izstevanka}
  \item[Opombe:] To je lepa implementacija. V praksi ne rabimo vsega public
    interface-a je dovolj samo imeti nekje globalen root in private metode.
\end{description*}
\hpp{ps/avl_tree.h}

\subsection{Fenwickovo drevo}
\label{sec:fenwick}
\begin{description*}
  \item[Operacije:] Imamo tabelo z indeksi $1 \leq x \leq 2^k$ v kateri
    hranimo števila. Želimo hitro posodabljati elemente in odgovarjati na queryje
    po vsoti podseznamov.
    \begin{itemize*}
      \item preberi vsoto do indeksa $x$ (za poljuben podseznam, $read(b) - read(a)$)
      \item posodobi število na indeksu $x$
      \item preberi število na indeksu $x$.
    \end{itemize*}
  \item[Časovna zahtevnost:] $O(k)$ na operacijo
  \item[Prostorska zahtevnost:] $O(2^k)$
  \item[Testiranje na terenu:]\url{http://putka.upm.si/competitions/upm2013-finale/safety}
\end{description*}
\cpp{ps/fenwick_tree.cpp}

\subsection{Fenwickovo drevo (\textit{n}-dim)}
\label{sec:fenwick-nd}
\begin{description*}
  \item[Operacije:] Imamo $n$-dim tabelo dimenzij $d_1 \times d_2 \times
    \dots \times d_n$ z
    zero-based indeksi v kateri hranimo števila.
    Želimo hitro posodabljati elemente in odgovarjati na queryje
    po vsoti podkvadrov.
    \begin{itemize*}
      \item preberi vsoto do vključno indeksa $\underline{x}$
      \item posodobi število na indeksu $\underline{x}$
      \item preberi vsoto na podkvadru (pravilo vključitev in izključitev)
    \end{itemize*}
    Funkcije so napisane za 3D, samo dodaj ali odstrani for zanke za višje /
    nižje dimenzije in spremeni $n$ za ne kockasto tabelo.
  \item[Časovna zahtevnost:] kumulativna vsota in update $O(\log(d_1 + \dots +
    d_n))$, za vsoto podkvadra $O(2^d\log(d_1+\dots+d_n))$.
  \item[Prostorska zahtevnost:] $O(d_1\cdots d_n)$
  \item[Testiranje na terenu:]\url{http://putka.upm.si/tasks/2010/2010_3kolo/stanovanja}
\end{description*}
\cpp{ps/fenwick_tree_nd.cpp}

\subsection{Trie}
\label{sec:trie}
\begin{description*}
  \item[Operacije:] Prefix tree, hranimo besede, črko po črko na nivoju, ćrke so
    iz neke končne abecede $\Sigma$, pri implementaciji $\Sigma = \{a, \dots,
    z\}$.
    \begin{itemize*}
      \item vstavi besedo
      \item največji skupen prefix z dano besedo
      \item največji skupen prefix med besedami v drevesu (vrne ena preveč)
    \end{itemize*}
  \item[Časovna zahtevnost:] $O(\ell)$ za \verb|add| in \verb|common_prefix|, ki
    tju uporabimo na besedi dolžine $\ell$ ter
    $O(|T|)$ za najdaljši prefix med vsemi besedami, kjer je $|T|$ število
    vozlišč v drevesu.
  \item[Prostorska zahtevnost:] $O(|T|) = O(n |\Sigma|)$, kjer je $n$ število besed, v praksi
    manj, ker se prekrivajo.
  \item[Testiranje na terenu:] \url{http://www.spoj.com/problems/PRHYME/} TODO
\end{description*}
\hpp{ps/trie.h}

\section{Algoritmi}
\label{sec:algo}

\subsection{Najdaljše skupno podzaporedje}
\label{sec:lcs}
\begin{description*}
  \item[Vhod:] Dve zaporedji $a$ in $b$ dolžin $n$ in $m$.
  \item[Izhod:] Najdaljše skupno podzaporedje (ne nujno strnjeno) $LCS$. Lahko dobimo
    tudi samo njegovo dolžino. Problem je povezan z najkrajšim skupnim nadzaporedjem
    ($SCS$). Velja $SCS + LCS = n + m$.
  \item[Časovna zahtevnost:] $O(nm)$
  \item[Prostorska zahtevnost:] $O(nm)$ za podzaporedje, $O(m)$ za dolžino.
  \item[Testiranje na terenu:] UVa 10405
\end{description*}
\cpp{algo/longest_common_subsequence.cpp}

\subsection{Najdaljše naraščajoče podzaporedje}
\label{sec:lis}
\begin{description*}
  \item[Vhod:] Zaporedje elementov na katerih imamo linearno urejenost.
  \item[Izhod:] Najdaljše naraščajoče podzaporedje.
  \item[Časovna zahtevnost:] $O(n \log(n))$ in $O(n^2)$
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:] UVa 103
  \item[Opomba:] Za hitro verzijo je zaradi bisekcije potrebna linearna
    urejenost elementov. Pri $n^2$ verziji je dovolj delna urejenost. V tem primeru je
    elemente morda treba urediti, tako da je potem potrebno za urejanje izbrati
    neko linearno razširitev dane delne urejenosti. Pri obeh verzijah elementi
    niso omejeni na števila, vendar pri prvi ne moremo samo zamenjati tipa, ki
    ga funkcija vrača, lažje je spremeniti, da vrača indekse elementov namesto
    dejanskega zaporedja.
\end{description*}
\cpp{algo/longest_increasing_subsequence.cpp}

\subsection{Najdaljši strnjen palindrom}
\label{sec:max-palindrome}
\begin{description*}
  \item[Vhod:] Niz $s$ dolžine $n$.
  \item[Izhod:] Števili $f$ in $t$, tako da je niz $s[f:t]$ palindrom največje
    dolžine, ki ga je možno najti v $s$. No nujno edini, niti prvi. Uporablja
    Mancherjev algoritem.
  \item[Časovna zahtevnost:] $O(n)$
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:] \url{http://www.spoj.com/problems/LPS/}
\end{description*}
\cpp{algo/longest_palindrome.cpp}

\subsection{Podseznam z največjo vsoto}
\label{sec:max-subarray}
\begin{description*}
  \item[Vhod:] Zaporedje elementov $a_i$ dolžine $n$.
  \item[Izhod:] Največja možna vsota strnjenega podzaporedja $a$ (lahko je tudi
    prazno). Alternativna verzija tudi vrne iskano zaporedje (najkrajše tako).
    Tretja verzija poišče $k$-to največjo vsoto.
  \item[Časovna zahtevnost:] $O(n)$, $O(n\log(n)+nk)$
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:] \url{http://www.codechef.com/problems/KSUBSUM}
\end{description*}
\cpp{algo/maximum_subarray.cpp}

\subsection{Leksikografsko minimalna rotacija}
\label{sec:min-rotation}
\begin{description*}
  \item[Vhod:] Niz znakov $s$ dolžine $n$.
  \item[Izhod:] Indeks $i$, tako da je string $\rslice{s}{i} + \lslice{s}{i}$ leksikografsko
    najmanjši, izmed vseh možnih rotacij $s$.
  \item[Časovna zahtevnost:] $O(n)$
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:] UVa 719
  \item[Opomba:] Če smo res na tesnem s prostorom, lahko funkcija sprejme
    dejanski string in ga ne podvoji, ter dela vse indekse po modulu $n$.
\end{description*}
\cpp{algo/minimal_rotation.cpp}

\subsection{BigInt in Karatsuba}
\label{sec:bigint}
Class za računanje z velikimi števili, v poljubni bazi. IO deluje samo v
desetiški.
\begin{description*}
  \item[Operacije:] Seštevanje, odštevanje, množenje, primerjanje.
    \begin{itemize*}
      \item seštevanje: samostojno, za negativne rabi $-$ in $<$.
      \item odštevanje: samostojno, če bo razlika pozitivna. Za negativne
        prevedi na seštevanje $a + (-b)$.
      \item množenje: rabi $+$, $\ll$ in $*$ s števko. Za negativne samo malo
        manipulacije predznakov. Lahko uporabiš tudi karatsubo.
      \item primerjanje: samostojno, za negativne samo malo manipulacije
        predznakov.
    \end{itemize*}
  Jasno ni treba implementirati vsega. $+$ in $*$ nista tako zelo počasna, tako
  da verzije $+=$ ipd. niso nujno potrebne.
  \item[Časovna zahtevnost:] $O(n)$ za $+$, $-$, $*$ stevka, $O(n^2)$ za $*$,
    $O(n^{1.585})$ za karatsubo.
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/test_okolja/odstevanje} in
    \url{http://putka.upm.si/tasks/test_okolja/sestevanje}
\end{description*}
\hpp{algo/bigint.h}

\subsection{Hitro množenje s hitro Fourierofo transformacijo}
Vse je hitro!
\begin{description*}
  \item[Vhod:] Dve dolgi števili ali polinoma zapisana v seznamu. Števila in polinomi so
    zapisani v svoji bazi obrnjeni okrog, tj.
    \begin{align*}
      23681 &= [1, 8, 6, 3, 2] \\
      2x^3 + 5x + 1 &= [1, 5, 0, 2]
    \end{align*}
  \item[Izhod:] Produkt zapisan v enaki obliki brez vodilnih ničel. Za zelo dolge sezname je lahko
    algoritem nenatančen.
  \item[Časovna zahtevnost:] $O(n \log n)$
  \item[Prostorska zahtevnost:] $O(n\log n)$
  \item[Testiranje na terenu:] TODO
\end{description*}
\cpp{algo/fast_fourier_transform.cpp}

\subsection{2-SAT}
\label{sec:2sat}
\begin{description*}
  \item[Vhod:] Formula $\varphi(x_1, \ldots, x_n)$ v 2-CNF obliki, torej
    \[ \varphi = S_1 \land \cdots \land S_n, \quad S_i = L_{i1} \lor L_{i2},
      \quad L_{ij} \in \{x_1, \ldots, x_n, \neg x_1, \ldots, \neg x_n\}. \]
      Za naše namene je predstavljena kot seznam parov števil od $\pm1$ do $\pm
      n$, kjer pozitivna število $i$ pomeni literal $x_i$, negativno število
      $-i$ pa literal $\neg x_i$. Na primer, \[ [(-2, 3), (4, 5), (-3, -1)] \] predstavlja
      formulo \[ (\neg x_2 \lor x_3) \land (x_4 \lor x_5) \land (\neg x_3 \lor
      \neg x_1). \]
  \item[Izhod:] Nabor $n$ vrednosti za $x_i$, pri katerih je formula resnična.
    Če tak nabor ne obstaja, vrne $(-1, \ldots, -1)$.
  \item[Časovna zahtevnost:] $O(V+E)$
  \item[Prostorska zahtevnost:] $O(V+E)$
  \item[Testiranje na terenu:] Uva 11294
\end{description*}
\cpp{algo/2sat.cpp}

\subsection{Knuth-Morris-Pratt}
\label{sec:kmp}
\begin{description*}
  \item[Vhod:] Niz znakov $s$ dolžine $n$ in niz znakov $p$ dolžine $m$. Posebej
    lahko izračunamo tudi failure function ali podamo indeks, da išče po nizu
    samo od nekje naprej.
  \item[Izhod:] Najmanjši indeks $0 \leq i < n$, tako da se v $s$ na mestih
    $\slice{s}{i}{i+m}$ nahaja $p$. Če tak indeks ne obstaja vrne $-1$. Program torej
    najde prvo pojavitev $p$ v $s$. Hkrati izračuna tudi
    \emph{failure\_function} \texttt{ff}, ki pove nekaj o samopodobnosti niza.
    Vrednost $\texttt{ff}[i-1]$ pove indeks naslednje črke, ki jo moramo
    preveriti, če vemo, da smo na $i$-tem znaku ravno failali match podniza.
    Drugače, to je dolžina največjega pravega podniza $\lslice{p}{i+1}$,
    ki je hkrati prefix in suffix za niz $\lslice{p}{i+1}$. Primer:
    \begin{center}
    \begin{tabular}[h]{|c||*{7}{c|}} \hline
      $p$ & A & B & C & D & A & B & D \\ \hline
      $i$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline
      \texttt{ff} & 0 & 0 & 0 & 0 & 1 & 2 & 0 \\ \hline
    \end{tabular}
    \end{center}
  \item[Časovna zahtevnost:] $O(n+m)$
  \item[Prostorska zahtevnost:] $O(m)$
  \item[Testiranje na terenu:] \url{http://www.spoj.com/problems/NHAY/}
\end{description*}
\cpp{algo/knuth_morris_pratt.cpp}

\subsection{\textit{z}-funkcija}
\label{sec:zf}
\begin{description*}
  \item[Vhod:] Niz znakov $s$ dolžine $n$.
  \item[Izhod:] $z$-funkcija niza. Vrednost $z[i]$ pove največji skupni prefix
    med $s$ in $\rslice{s}{i}$. \\ Primer: za $s = ``aaaaa$`` je $z = [0,4,3,2,1]$, za $s
    = ``aaabaab$'' je $z = [0,2,1,0,2,1,0]$, za $s = ``abacaba$'' je $z =
    [0,0,1,0,3,0,1]$.
  \item[Časovna zahtevnost:] $O(n)$
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:] TODO
\end{description*}
\cpp{algo/z_function.cpp}

\subsection{Minimalna perioda niza}
\label{sec:minperiod}
\begin{description*}
  \item[Vhod:] Niz znakov $s$ dolžine $n$.
  \item[Izhod:] Dolžina minimalne periode $s$, tj.~tak $k$, da je
  $(\lslice{s}{k})^{\frac{n}{k}} = s$. \\ Primer: minimalna perioda $s =
  ``abcabcabc$'' je ``$abc$'', dolžine 3.
  \item[Časovna zahtevnost:] $O(n)$
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:] TODO
  \item[Implementacija:] Glej \nameref{sec:zf}, str.~\pageref{sec:zf} ali
    \nameref{sec:kmp}, str.~\pageref{sec:kmp}.
\end{description*}

\subsection{Minimalni element v podseznamu}
Po angleško RMQ ali Range Minimum Query. Želimo odgovarjati na poizvedbe v
seznam dolžine $n$ oblike: ``Koliko je minimum med $a$ in $b$.''
Če se elementi seznama spreminjajo, potem je najboljša uporaba statičnega
drevesa segmentov~\ref{sec:static-segment-tree}. Če pa imamo dan seznam vnaprej,
potem si lahko zgradimo strukturo, kjer za vsak indeks $i$ vemo odgovor na
vprašanje ``Koliko je minimum na intervalu $[i, i+2^j]$ za vse $j$, da je
interval še v seznamu. Tako lahko query $[a, b]$ odgovorimo v konstantnem času
tako, da najdemo največji $r$, da je $a+2^r \leq b$ in primerjamo minimuma na
$[a, a+2^r]$, $[b-2^r, b]$, ki sta oba poračunana vnaprej.

\section{Numerika}
\label{sec:numerika}
\subsection{Gaussova eliminacija}
\begin{description*}
  \item[Vhod:] Matrika $A' = [A\ |\ b]$, ki predstavlja $m\times n$ sistem $Ax = b$.
  \item[Izhod:] Vektor $x$ (dolg $n$), ki reši sistem. Poleg tega vrne tudi $-1$,
    če rešitev ne obstaja, 0, če je enolična, sicer pa dimenzionalnost prostora
    rešitev (tj.~število splošnih konstant). Enačbo rešimo z $LU$ razcepom z delnim
    pivotiranjem. Druga funkcija izračuna determinanto matrike, prav tako z
    uporabo delnega pivotiranja. Obe se da uporabiti z ulomki namesto z
    decimalnimi števili ali pa po modulu $p$, kjer je potrebno deljenja
    zamenjati z inverzi.
  \item[Časovna zahtevnost:] $O(\min\{n, m\}nm)$
  \item[Prostorska zahtevnost:] $O(nm)$
\end{description*}
\cpp{num/gauss.cpp}

\subsection{Tangentna metoda}
\begin{description*}
  \item[Vhod:] Funkciji $f$ in $f'$ ter približek za ničlo $x_0$.
  \item[Izhod:] Približek $x_n$ po $n$ korakih metode $x_{i+1} = x_i -
    \frac{f(x_i)}{f'(x_i)}$ ali ko je zaporedni premik manjši od $\varepsilon$.
  \item[Časovna zahtevnost:] Konvergenca je kvadratična, torej
    $O(\log\frac{1}{\sqrt{\varepsilon}})$.
  \item[Prostorska zahtevnost:] $O(1)$
\end{description*}
\cpp{num/tangent_method.cpp}

\subsection{Bisekcija}
\begin{description*}
  \item[Vhod:] Funkcija $f$ in krajišči intervala $[a, b]$ na katerem leži
    ničla in ima funkcija v krajiščih različen predznak.
  \item[Izhod:] Približek za ničlo, ko je širina intervala enaka $\varepsilon|b-a|$ ali
    približek po $n$ korakih.
  \item[Časovna zahtevnost:] Konvergenca je linearna, torej
    $O(\log\frac{1}{\varepsilon})$.
  \item[Prostorska zahtevnost:] $O(1)$
\end{description*}
\cpp{num/bisection.cpp}

\section{Teorija števil}
\label{sec:ts}

\subsection{Evklidov algoritem}
\label{sec:ts:evk}
\begin{description*}
  \item[Vhod:] $a, b \in \Z$
  \item[Izhod:] Največji skupni delitelj $a$ in $b$. Za pozitivna števila je
    pozitiven, če je eno število 0, je rezultat drugo število, pri negativnih je
    predznak odvisen od števila iteracij.
  \item[Časovna zahtevnost:] $O(\log(a) + \log(b))$
  \item[Prostorska zahtevnost:] $O(1)$
\end{description*}
\cpp{ts/gcd.cpp}

\subsection{Razširjen Evklidov algoritem}
\label{sec:ts:extevk}
\begin{description*}
  \item[Vhod:] $a, b \in \Z$. Števili $retx$, $rety$ sta parametra samo za vračanje vrednosti.
  \item[Izhod:] Števila $x, y, d$, pri čemer $d = \gcd(a, b)$, ki rešijo
    Diofantsko enačbo $ax + by = d$. V posebnem primeru, da je $b$ tuj $a$, je
    $x$ inverz števila $a$ v multiplikativni grupi $Z_b^\ast$.
  \item[Časovna zahtevnost:] $O(\log(a) + \log(b))$
  \item[Prostorska zahtevnost:] $O(1)$
  \item[Testiranje na terenu:] UVa 756
\end{description*}
\cpp{ts/extended_gcd.cpp}

\subsection{Kitajski izrek o ostankih}
\label{sec:ts:chinese}
\begin{description*}
  \item[Vhod:] Sistem $n$ kongruenc $x \equiv a_i \pmod{m_i}$, $m_i$ so paroma tuji.
  \item[Izhod:] Število $x$, ki reši ta sistem dobimo po formuli
    \[ x =
      \left[\sum_{i=1}^na_i\frac{M}{m_i}\left[\left(\frac{M}{mi}\right)^{-1}\right]_{m_i}\right]_M,
      \qquad M = \prod_{i=1}^nm_i,
    \]
    kjer $[x^{-1}]_m$ označuje inverz $x$ po modulu $m$. Vrnjeni $x$ je med 0 in $M$.
  \item[Časovna zahtevnost:] $O(n \log(\max\{m_i, a_i\}))$
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Potrebuje:] \nameref{sec:ts:evk} (str.~\pageref{sec:ts:evk})
  \item[Testiranje na terenu:] UVa 756
  \item[Opomba:] Pogosto potrebujemo \ull{} namesto \texttt{int}.
\end{description*}
\cpp{ts/chinese_reminder_theorem.cpp}

\subsection{Hitro potenciranje}
\label{sec:fastpow}
\begin{description*}
  \item[Vhod:] Število $g$ iz splošne grupe in $n \in \N_0$.
  \item[Izhod:] Število $g^n$.
  \item[Časovna zahtevnost:] $O(\log(n))$
  \item[Prostorska zahtevnost:] $O(1)$
  \item[Testiranje na terenu:] \url{http://putka.upm.si/tasks/2010/2010_3kolo/nicle}
\end{description*}
\cpp{ts/fast_power.cpp}

\subsection{Številski sestavi}
\label{sec:sestavi}
\begin{description*}
  \item[Vhod:] Število $n \in \N_0$ ali $\frac{p}{q} \in Q$ ter $b \in [2,
      \infty) \cap \N.$
  \item[Izhod:] Število $n$ ali $\frac{p}{q}$ predstavljeno v izbranem sestavu
    z izbranimi števkami in označeno periodo.
  \item[Časovna zahtevnost:] $O(\log(n))$ ali $O(q\log(q))$
  \item[Prostorska zahtevnost:] $O(n)$ ali $O(q)$
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2010/2010_finale/ulomki}
  \item[Opomba:] Zgornja meja za bazo $b$ je dolžina niza
    \verb|STEVILSKI_SESTAVI_ZNAKI|.
\end{description*}
\cpp{ts/stevilski_sestavi.cpp}

\subsection{Eulerjeva funkcija $\phi$}
\label{sec:phi}
\begin{description*}
  \item[Vhod:] Število $n \in \N$.
  \item[Izhod:] Število $\phi(n)$, to je število števil manjših ali enakih $n$ in tujih $n$.
    Direktna formula:
    \[ \phi(n) = n\cdot \prod_{p \divides n}(1-\frac{1}{p}) \]
  \item[Časovna zahtevnost:] $O(\sqrt{n})$
  \item[Prostorska zahtevnost:] $O(1)$
  \item[Testiranje na terenu:]
    \url{https://projecteuler.net/problem=69}
\end{description*}
\cpp{ts/euler_phi.cpp}

\subsection{Eratostenovo rešeto}
\label{sec:primes}
\begin{description*}
  \item[Vhod:] Število $n \in \N$.
  \item[Izhod:] Seznam praštevil manjših od $n$ in seznam, kjer je za vsako
    število manjše od $n$ notri njegov najmanjši praštevilski delitelj. To se
    lahko uporablja za faktorizacijo števil in testiranje praštevilskosti.
  \item[Časovna zahtevnost:] $O(n\log(n))$
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:] UVa 10394
\end{description*}
\cpp{ts/eratosthenes_sieve.cpp}

\subsection{Število deliteljev}
\label{sec:tau}
\begin{description*}
  \item[Vhod:] Število $n \in \N$.
  \item[Izhod:] Število pozitivnih deliteljev $n$, $\tau(n)$. Velja, da je za $n =
    p_1^{\alpha_1}\cdots p_k^{\alpha_k}$, \[ \tau(n) = (\alpha_1 + 1) \cdots
    (\alpha_k + 1). \]
  \item[Časovna zahtevnost:] $O(\sqrt{n})$
  \item[Prostorska zahtevnost:] $O(1)$
  \item[Testiranje na terenu:] \url{https://projecteuler.net/problem=12}
\end{description*}
\cpp{ts/number_of_divisors.cpp}

\subsection{Binomski koeficienti}
\label{sec:binom}
\begin{description*}
  \item[Vhod:] Števili $n, k \in \Z$.
  \item[Izhod:] Binomski koeficient $\binom{n}{k} =
    \begin{cases}
      \frac{n!}{k!(n-k)!} & n, k \geq 0 \\
      0 & \text{ sicer}
    \end{cases}$ \\
    Za velike vrednosti lahko izračunamo aproksimacijo s pomočjo logaritma gama
    funkcije. Če rabiš isto vrednost $\binom{n}{k}$ več kot enkrat, se morda
    splača shraniti cel Pascalov trikotnik.
  \item[Časovna zahtevnost:] $O(\min\{k, n-k\})$ za enega, $O(n^2)$ za Pascalov
    trikotnik.
  \item[Prostorska zahtevnost:] $O(1)$ za enega, $O(n^2)$ za Pascalov trikotnik
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2015/2015_3kolo/minsko_polje}
\end{description*}
\cpp{ts/binomial.cpp}

\subsection{Binomski koeficienti po modulu}
\label{sec:binommod}
\begin{description*}
  \item[Vhod:] Števili $n, k \in \Z$ in $p \in \mathbb{P}$. Lahko posplošimo na
    poljubno število, ki v praštevilskem razcepu nima potenc praštevil.
  \item[Izhod:] Ostanek pri deljenju binomskega koeficienta $\binom{n}{k}$ s
    $p$. Če je $p$ praštevilo, lahko uporabiš \verb|binomial_modp|, sicer pa
    \verb|binomial_mod|. Pri deljenju s praštevilom uporabimo Lucasov izrek:
    \[ \binom{n}{k} \equiv
      \binom{n_r}{k_r}\binom{n_{r-1}}{k_{r-1}}\cdots\binom{n_1}{k_1}\binom{n_0}{k_0},
    \] kjer sta $n = n_r\ldots n_0$ in $k = k_r\ldots k_0$ zapisa števil $n$ in
    $k$ v $p$-jiškem sistemu.

    Sicer število razcepimo na tuja si števila
    (prafaktorje) in uporabimo skupaj za vsako praštevilo posebej zgornji
    postopek, nato pa združimo s kitajskim izrekom o ostankih.
  \item[Časovna zahtevnost:]: $O(p \cdot (\log_p(n) + \log_p(k)))$ za praštevilo $p$.
  \item[Prostorska zahtevnost:] $O(1)$
  \item[Potrebuje:] \nameref{sec:ts:chinese}
    (str.~\pageref{sec:ts:chinese})
  \item[Testiranje na terenu:]
    \url{http://putka.upm.si/tasks/2015/2015_3kolo/minsko_polje}
\end{description*}
\cpp{ts/binomial_mod.cpp}

\section{Geometrija}
\label{sec:geom}
Zaenkrat obravnavamo samo ravninsko geometrijo.
Točke predstavimo kot kompleksna števila. Daljice predstavimo z začetno in
končno točko. Premice s koeficienti v enačbi $ax + by = c$. Premico lahko
konstruiramo iz dveh točk in po želji hranimo točko in smerni vektor.
Pravokotnike predstavimo z spodnjim levim in zgornjim desnim ogliščem.
Večkotnike predstavimo s seznamom točk, kot si sledijo, prve točke ne
ponavljamo. Tip \texttt{ITYPE} predstavlja različne vrste presečišč ali
vsebovanosti: \texttt{OK} pomeni, da se lepo seka oz.\ je točka v notranjosti.
\texttt{NO} pomeni, da se ne seka oz.\ da točna ni vsebovana, \texttt{EQ} pa
pomeni, da se premici prekrivata, daljici sekata v krajišču ali se pokrivata,
oz.\ da je točka na robu.

\subsection{Osnove}
\label{sec:basic}
Funkcije:
\begin{itemize*}
  \item skalarni in vektorski produkt
  \item pravokotni vektor in polarni kot
  \item ploščina trikotnika in enostavnega mnogokotnika
  \item razred za premice
  \item razdalja do premice, daljice, po sferi
  \item vsebovanost v trikotniku, pravokotniku, enostavnem mnogokotniku
  \item presek dveh premic, premice in daljice in dveh daljic
  \item konstrukcije krogov iz treh točk, iz dveh točk in radija
\end{itemize*}
\begin{description*}
  \item[Vhod:] Pri argumentih funkcij.
  \item[Izhod:] Pri argumentih funkcij.
  \item[Časovna zahtevnost:] $O(\text{št.\ točk})$
  \item[Prostorska zahtevnost:] $O(\text{št.\ točk})$
  \item[Testiranje na terenu:] Bolj tako, ima pa obsežne unit teste\dots
\end{description*}
\hpp{geom/basics.h}
\cpp{geom/basics.cpp}

\subsection{Konveksna ovojnica}
\label{sec:convex-hull}
\begin{description*}
  \item[Vhod:] Seznam $n$ točk.
  \item[Izhod:] Najkrajši seznam $h$ točk, ki napenjajo konveksno ovojnico,
    urejen naraščajoče po kotu glede na spodnjo levo točko.
  \item[Časovna zahtevnost:] $O(n\log n)$, zaradi sortiranja
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Potrebuje:] Vektorski produkt, str.~\pageref{sec:basic}.
  \item[Testiranje na terenu:] UVa 681
\end{description*}
\cpp{geom/convex_hull.cpp}

\subsection{Ploščina unije pravokotnikov}
\begin{description*}
  \item[Vhod:] Seznam $n$ pravokotnikov $P_i$ danih s spodnjo levo in zgornjo desno
    točko.
  \item[Izhod:] Ploščina unije danih pravokotnikov.
  \item[Časovna zahtevnost:] $O(n\log n)$
  \item[Prostorska zahtevnost:] $O(n)$
  \item[Testiranje na terenu:] \url{http://putka.upm.si/competitions/upm2013-2/kolaz}
\end{description*}
\cpp{geom/rectangle_union_area.cpp}

\subsection{Najbližji par točk v ravnini}
\begin{description*}
  \item[Vhod:] Seznam $n \geq 2$ točk v ravnini.
  \item[Izhod:] Kvadrat razdalje med najbližjima točkama. Z lahkoto se
    prilagodi, da vrne tudi točki.
  \item[Časovna zahtevnost:] $O(n\log n)$, nisem sure\dots
  :\item[Prostorska zahtevnost:] $O(n \log n)$
  \item[Testiranje na terenu:] UVa 10245
\end{description*}
\cpp{geom/closest_pair_of_points.cpp}

\section{Matematika}
\small
\begin{description*}
  \item[Vrste:] \vspace{-1ex}
    \begin{gather*}
      \sum_{i=1}^n i = \frac{n(n+1)}{2} \quad \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} \quad
      \sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4} \\
      \sum_{i=1}^n q^i = q \frac{q^n - 1}{q - 1} \quad \sum_{i=1}^n i q^i = \frac{n
        q^{n+2} - (n+1)q^{n+1} + q}{(q-1)^2}
    \end{gather*}
  \item[Geometrija:] \mbox{} \\
    Trikotnik (stranice $a, b, c$, oglišča $A, B, C$ s koordinatami $(x_i, y_i)$, ploščina $p$, polobseg $s$, $r$
    radij včrtanega in $R$ očrtanega kroga): \\
    \begin{align*}
    p &=
    \mathrm{abs}\left(\frac12 \det\left(
    \begin{matrix}
      x_2 - x_1 & y_2 - y_1 \\ x_3 - x_1 & y_3 - y_1
    \end{matrix}\right)\right) = \frac{(B-A)\times (B-C)}{2} = \frac{c \cdot v_c}{2} = \frac{a \cdot b \cdot
    \sin\gamma}{2} = \\
      &=\sqrt{s(s-a)(s-b)(s-c)} = rs = \frac{abc}{4R}
    \end{align*}
    Pravilni mnogokotnik (stranica $a$, obseg $o$, ploščina $p$, $\varphi = \frac{2\pi}{n}$
    središčni kot, $r$ radij včrtanega in $R$ očrtanega kroga): \\
    \[ p = \frac{nar}{2} = \frac{n R^2 \sin\varphi}{2} =
    \frac{na^2}{4\tan\frac{\varphi}{2}} = n r^2 \tan\frac{\varphi}{2} \]

  \item[Linearna algebra:]
    Dano imamo rekurzivno zvezo
    $z_{n+2} = a z_{n+1} + b z_n$ in pogoja $z_0 = c_0$ in $z_1 = c_1$.
    Tako zvezo lahko napišemo v matriko (dodamo trivialne enakosti, če je
    potrebno):
    \[
      \begin{bmatrix}
        z_{n+2} \\ z_{n+1}
      \end{bmatrix} =
      \begin{bmatrix}
        a & b \\ 0 & 1
      \end{bmatrix}
      \begin{bmatrix}
        z_{n+1} \\ z_{n}
    \end{bmatrix} \]
    Krajše zapisano dobimo $\vec{x}_{n+1} = A\vec{x}_n$, kar odvijemo do
    $\vec{x}_{n+1} = A^{n+1}\vec{x}_0$, kjer so vse količine znane. S hitrim
    potenciranjem lahko izračunamo $\vec{x}_{n+1}$ v $O(\log n)$ časa.

  \item[Kombinatorika:]
    \begin{gather*}
      \binom{n}{k} = \frac{n!}{k!(n-k)!} = \prod_{i=0}^{k-1} \frac{n-i}{i+1} = \binom{n-1}{k} + \binom{n-1}{k-1} \\
      C_n = \frac{1}{n+1}\binom{2n}{n} = \sum_{i=0}^{n-1}C_iC_{n-1-i} = \prod_{i=2}^n\frac{n+i}{i} = \frac{2(2n-1)}{n+1}C_{n-1} \\
      F_n = F_{n-1} + F_{n-2} = \begin{pmatrix} 1 & 1 \\ 0 & 1
      \end{pmatrix}^{n-1}_{11}\quad F_mF_n + F_{m-1}F_{n-1}  = F_{m+n-1} \quad
      F_mF_{n+1} + F_{m-1}F_n = F_{m+n}
    \end{gather*}

    \textbf{Izbori $k$ elementov iz $n$ množice:} \\[6pt]
    \begin{tabular}[h]{|c|c|c|c|c|}
      \hline
      urejeni/ponavljanje & DA/DA & DA/NE & NE/DA & NE/NE \\ \hline
      število & $n^k$ & $n^{\underline{k}}$ & $\binom{n+k-1}{k}$ & $\binom{n}{k}$ \\ \hline
    \end{tabular}

    \textbf{Binomska in multinomska števila:} \\
    Velja: $(a+b)^n = \sum_{k=0}^n\binom{n}{k}a^{n-k}b^k \qquad \sum_{k=0}^n\binom{n}{k} =
    2^n \qquad \sum_{k=0}^n\binom{n}{k}^2 = \binom{2n}{n}$ \\

    \textbf{Pravilo vključitev in izključitev:} $|A_1 \cup \cdots \cup A_n| = \alpha_1 - \alpha_2 + \dots +
    (-1)^{n+1}\alpha_n$ \\
    $\alpha_i = \text{vsota moči vseh možnih presekov po $i$ množic}$. \\
    V posebnem, če so vsi preseki po $i$ množic enako močni:
    $\lvert\bigcup_{i=1}^nA_i\rvert = \sum_{i=1}^n (-1)^{i+1}\binom{n}{i}\lvert\bigcap_{j=1}^iA_j\rvert$
    Če je problem lep, je to možno implementirati v $O(n^2)$ časa.

    % \textbf{Trdnjavski polinomi:}
    % $T(D, x) = \sum_{k=1}^{|D|}t_k(D)x^k$ je trdnjavski polinom deske $D$. Število $t_k(D)$ je
    % število možnih različnih postavitev $k$ trdnjav na desko $D$.\\
    % Če je $D$ polna deska: $t_k(D_{m, n}) = \binom{m}{k}\binom{n}{k}k!$ \\
    % Če $D=D_1\oplus D_2$ ($D_1$ in $D_2$ nimata niti skupnih vrstic niti stolpcev (se pa ne
    % držijo nujno skupaj)), potem velja $T(D, x) = T(D_1, x)T(D_2, x)$. \\
    % V splošnem drži naslednja rekurzija: $T(D, x) = T(D\setminus a, x) + x\cdot T(D/a, x), a$
    % polje na $D$. \\
    % Prehod na komplementarno desko: $t_k(D) =
    % \sum_{j=0}^n(-1)^j\binom{m-j}{k-j}\binom{n-j}{k-j}(k-j)!t_j(\overline{D})$ \\
    % Število deranžmajev: $\# = n!(\frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n\frac{1}{n!})$

    \textbf{Stirlingova števila 2. vrste:} \\
    $S(n, k)$ je število možnih razbitij $n$-množice na $k$ nepraznih kosov. \\
    Definiramo $S(0, 0)=1$ in $S(n, 0)= 0$ za $n\geq1$. \\
    Rekurzivna zveza: $S(n, k) = S(n-1, k-1) + k\cdot S(n-1, k)$ \\
    Velja: $x^n = \sum_{k=1}^nS(n, k)x^{\underline{k}} \qquad S(n+1, m+1) =
    \sum_{k=1}^n\binom{n}{k}S(k, m)$  \\
    Število surjekcij: $k!S(n, k) = \sum_{i=1}^n(-1)^i\binom{k}{i}(k-i)^n$

    \textbf{Lahova števila:} \\
    $L(n, k)$ je število možnih razbitij $n$-množice na $k$ linearno urejenih nepraznih kosov. \\
    Definiramo $L(0, 0)=1$ in $L(n, 0)= 0$ za $n\geq1$. \\
    Rekurzivna zveza: $L(n, k) = L(n-1, k-1) + (n+k-1)\cdot L(n-1, k)$ \\
    Eksplicitna formula: $L(n, k) = \frac{n!}{k!}\binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)!}\binom{n}{k}$. \\
    Velja: $x^{\bar{n}} = \sum_{k=1}^nL(n, k)x^{\underline{k}}$

    \textbf{Stirlingova števila 1. vrste:} \\
    $s(n, k)$ je število permutacij $n$ množice, ki se zapišejo kot produkt $k$ disjunktnih
    ciklov. \\
    Definiramo $s(0, 0)=1$ in $s(n, 0)= 0$ za $n\geq1$. \\
    Rekurzivna zveza: $s(n, k) = s(n-1, k-1) + (n-1)\cdot s(n-1, k)$ \\
    Velja: $x^{\overline{n}} = \sum_{k=1}^ns(n, k)x^k$

    \textbf{Bellova števila:}\\
    $B(n)$ je število vseh možnih razbitij $n$ množice.
    Očitno velja: $\sum_{k=0}^nS(n, k) = B(n)$. \\
    Rekurzivna zveza: $B(n+1) = \sum_{k=0}^n\binom{n}{k}B(k)$

    \textbf{Particije števila:}\\
    Particija števila $n$ je zapis $n = \lambda_1 + \dots + \lambda_k$, kjer velja $0 <
    \lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_k$. $\lambda_i$ so kosi.\\
    Rekurzivna zveza: $p(n; k) = p(n-1; k-1) + p(n-k; k)$, št. particij $n$ na $k$ kosov. \\
    $p(n; k) = p(n-k; \leq k) = \sum_{i=1}^{n-k}p(n-k; i)$

    \textbf{Dvanajstera pot:}\\
    Razporejamo $n$ predmetov v $r$ predalov. Ali ločimo elemente,
    dopuščamo prazne predale, dopuščamo več kot en predmet v predalu?  Glejmo
    $f\colon[n] \to [r]$.

    \begin{tabular}{|c|c|c|c|}
      \hline
      predmeti/predali \textbackslash\ $f$ & poljubna & injektivna & surjektivna \\ \hline
      DA/DA & $r^n$ & $r^{\underline{n}}$ & $r!S(n, r)$ \\ \hline
      NE/DA & $\binom{r+n-1}{n}$ & $\binom{r}{n}$ & $\binom{n-1}{r-1}$ \\ \hline
      DA/NE & $\sum_{k=1}^rS(n, k)$ & $n \leq r$ & $S(n, r)$ \\ \hline
      NE/NE & $\sum_{k=1}^rp(n; k)$ & $n \leq r$ & $p(n; r)$ \\ \hline
    \end{tabular}

    \newpage

    {\scriptsize

    \vspace*{-30px}

    \textbf{Binomska števila:} $\binom{n}{k}$ \\
    \begin{tabular}{|*{16}{c|}}
      \hline
      $n \backslash k$ & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\ \hline
      0 & 1 &  &  &  &  &  &  &  &  &  &  &  &  &  & \\ \hline
      1 & 1 & 1 &  &  &  &  &  &  &  &  &  &  &  &  & \\ \hline
      2 & 1 & 2 & 1 &  &  &  &  &  &  &  &  &  &  &  & \\ \hline
      3 & 1 & 3 & 3 & 1 &  &  &  &  &  &  &  &  &  &  & \\ \hline
      4 & 1 & 4 & 6 & 4 & 1 &  &  &  &  &  &  &  &  &  & \\ \hline
      5 & 1 & 5 & 10 & 10 & 5 & 1 &  &  &  &  &  &  &  &  & \\ \hline
      6 & 1 & 6 & 15 & 20 & 15 & 6 & 1 &  &  &  &  &  &  &  & \\ \hline
      7 & 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 &  &  &  &  &  &  & \\ \hline
      8 & 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 &  &  &  &  &  & \\ \hline
      9 & 1 & 9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1 &  &  &  &  & \\ \hline
      10 & 1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1 &  &  &  & \\ \hline
      11 & 1 & 11 & 55 & 165 & 330 & 462 & 462 & 330 & 165 & 55 & 11 & 1 &  &  & \\ \hline
      12 & 1 & 12 & 66 & 220 & 495 & 792 & 924 & 792 & 495 & 220 & 66 & 12 & 1 &  & \\ \hline
      13 & 1 & 13 & 78 & 286 & 715 & 1287 & 1716 & 1716 & 1287 & 715 & 286 & 78 & 13 & 1 & \\ \hline
      14 & 1 & 14 & 91 & 364 & 1001 & 2002 & 3003 & 3432 & 3003 & 2002 & 1001 & 364 & 91 & 14 & 1\\ \hline
    \end{tabular}

    \textbf{Stirlingova števila 2. vrste:} $S(n, k)$ in \textbf{Bellova števila} $B(n)$\\
    \begin{tabular}{|*{12}{c|}}
      \hline
      $n \backslash k$ & 1&2&3&4&5&6&7&8&9&10&$B(n)$ \\ \hline
      1 & 1 &  &  &  &  &  &  &  &  & & 1 \\ \hline
      2 & 1 & 1 &  &  &  &  &  &  &  & & 2 \\ \hline
      3 & 1 & 3 & 1 &  &  &  &  &  &  & & 5 \\ \hline
      4 & 1 & 7 & 6 & 1 &  &  &  &  &  & & 15 \\ \hline
      5 & 1 & 15 & 25 & 10 & 1 &  &  &  &  & & 52 \\ \hline
      6 & 1 & 31 & 90 & 65 & 15 & 1 &  &  &  & & 203\\ \hline
      7 & 1 & 63 & 301 & 350 & 140 & 21 & 1 &  &  & & 877 \\ \hline
      8 & 1 & 127 & 966 & 1701 & 1050 & 266 & 28 & 1 &  & & 4140 \\ \hline
      9 & 1 & 255 & 3025 & 7770 & 6951 & 2646 & 462 & 36 & 1 & & 21147 \\ \hline
      10 & 1 & 511 & 9330 & 34105 & 42525 & 22827 & 5880 & 750 & 45 & 1 & 115975 \\ \hline
    \end{tabular}

    \textbf{Stirlingova števila 1. vrste:} $s(n, k)$ \\
    \begin{tabular}{|*{11}{c|}}
      \hline
      $n \backslash k$ & 1&2&3&4&5&6&7&8&9&10 \\ \hline
      1 & 1 &  &  &  &  &  &  &  &  & \\ \hline
      2 & 1 & 1 &  &  &  &  &  &  &  & \\ \hline
      3 & 2 & 3 & 1 &  &  &  &  &  &  & \\ \hline
      4 & 6 & 11 & 6 & 1 &  &  &  &  &  & \\ \hline
      5 & 24 & 50 & 35 & 10 & 1 &  &  &  &  & \\ \hline
      6 & 120 & 274 & 225 & 85 & 15 & 1 &  &  &  & \\ \hline
      7 & 720 & 1764 & 1624 & 735 & 175 & 21 & 1 &  &  & \\ \hline
      8 & 5040 & 13068 & 13132 & 6769 & 1960 & 322 & 28 & 1 &  & \\ \hline
      9 & 40320 & 109584 & 118124 & 67284 & 22449 & 4536 & 546 & 36 & 1 & \\ \hline
      10 & 362880 & 1026576 & 1172700 & 723680 & 269325 & 63273 & 9450 & 870 & 45 & 1\\ \hline
    \end{tabular}

    \textbf{Lahova števila:} $L(n, k)$ \\
    \begin{tabular}{|*{11}{c|}}
      \hline
      $n \backslash k$ & 1&2&3&4&5&6&7&8&9&10 \\ \hline
      1 & 1 &  &  &  &  &  &  &  &  & \\ \hline
      2 & 1 & 1 &  &  &  &  &  &  &  & \\ \hline
      3 & 1 & 5 & 1 &  &  &  &  &  &  & \\ \hline
      4 & 1 & 26 & 11 & 1 &  &  &  &  &  & \\ \hline
      5 & 1 & 157 & 103 & 19 & 1 &  &  &  &  & \\ \hline
      6 & 1 & 1100 & 981 & 274 & 29 & 1 &  &  &  & \\ \hline
      7 & 1 & 8801 & 9929 & 3721 & 593 & 41 & 1 &  &  & \\ \hline
      8 & 1 & 79210 & 108091 & 50860 & 10837 & 1126 & 55 & 1 &  & \\ \hline
      9 & 1 & 792101 & 1268211 & 718411 & 191741 & 26601 & 1951 & 71 & 1 & \\ \hline
      10 & 1 & 8713112 & 16010633 & 10607554 & 3402785 & 590756 & 57817 & 3158 & 89 & 1\\ \hline
    \end{tabular}

    \textbf{Particije števila:} $p(n; k)$ \\
    \begin{tabular}{|*{16}{c|}}
      \hline
      $n \backslash k$ & 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15 \\ \hline
      1 & 1 &  &  &  &  &  &  &  &  &  &  &  &  &  & \\ \hline
      2 & 1 & 1 &  &  &  &  &  &  &  &  &  &  &  &  & \\ \hline
      3 & 1 & 1 & 1 &  &  &  &  &  &  &  &  &  &  &  & \\ \hline
      4 & 1 & 2 & 1 & 1 &  &  &  &  &  &  &  &  &  &  & \\ \hline
      5 & 1 & 2 & 2 & 1 & 1 &  &  &  &  &  &  &  &  &  & \\ \hline
      6 & 1 & 3 & 3 & 2 & 1 & 1 &  &  &  &  &  &  &  &  & \\ \hline
      7 & 1 & 3 & 4 & 3 & 2 & 1 & 1 &  &  &  &  &  &  &  & \\ \hline
      8 & 1 & 4 & 5 & 5 & 3 & 2 & 1 & 1 &  &  &  &  &  &  & \\ \hline
      9 & 1 & 4 & 7 & 6 & 5 & 3 & 2 & 1 & 1 &  &  &  &  &  & \\ \hline
      10 & 1 & 5 & 8 & 9 & 7 & 5 & 3 & 2 & 1 & 1 &  &  &  &  & \\ \hline
      11 & 1 & 5 & 10 & 11 & 10 & 7 & 5 & 3 & 2 & 1 & 1 &  &  &  & \\ \hline
      12 & 1 & 6 & 12 & 15 & 13 & 11 & 7 & 5 & 3 & 2 & 1 & 1 &  &  & \\ \hline
      13 & 1 & 6 & 14 & 18 & 18 & 14 & 11 & 7 & 5 & 3 & 2 & 1 & 1 &  & \\ \hline
      14 & 1 & 7 & 16 & 23 & 23 & 20 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1 & \\ \hline
      15 & 1 & 7 & 19 & 27 & 30 & 26 & 21 & 15 & 11 & 7 & 5 & 3 & 2 & 1 & 1\\ \hline
    \end{tabular}
    } % end footnotesize

    \newpage

  \item[Številske ocene:] \mbox{} \\[12pt]
    \hspace*{-20pt}
    \begin{tabular}[h]{|c|c|c|c|c|c|c|c|} \hline
      $i$ & $2^i$ & $\log_{10}(2^i)$ & i! & $\log_{10}(i!)$ & $10^i$ \texttt{int}-ov & $C_i$ & $F_i$ \\ \hline
        1 &             2 & 0,30 & 1        &  0,00 & \unit[40]{B}    & 1       & 1 \\
        2 &             4 & 0,60 & 2        &  0,30 & \unit[400]{B}   & 2       & 1 \\
        3 &             8 & 0,90 & 6        &  0,77 & \unit[3,9]{kiB} & 5       & 2 \\
        4 &            16 & 1,20 & 24       &  1,38 & \unit[39]{kiB}  & 14      & 3 \\
        5 &            32 & 1,50 & 120      &  2,07 & \unit[400]{kiB} & 42      & 5 \\
        6 &            64 & 1,80 & 720      &  2,85 & \unit[3,8]{MiB} & 132     & 8 \\
        7 &           128 & 2,10 & 5040     &  3,70 & \unit[38]{MiB}  & 429     & 13 \\
        8 &           256 & 2,40 & 40320    &  4,60 & \unit[380]{MiB} & 1430    & 21 \\
        9 &           512 & 2,70 & 362880   &  5,55 & \unit[3,7]{GiB} & 4862    & 34 \\
       10 &         1.024 & 3,01 & 3628800  &  6,55 & $\cdot$         & 16796   & 55 \\
       11 &         2.048 & 3,31 & 39916800 &  7,60 & $\cdot$         & 58786   & 89 \\
       12 &         4.096 & 3,61 & $\cdot$  &  8,68 & $\cdot$         & 208012  & 144 \\
       13 &         8.192 & 3,91 & $\cdot$  &  9,79 &                 & 742900  & 233 \\
       14 &        16.384 & 4,21 & $\cdot$  & 10,94 &                 & 2674440 & 377 \\
       15 &        32.768 & 4,51 &          & 12,11 &                 & 9694845 & 610 \\
       16 &        65.536 & 4,81 &          & 13,32 &                 & $\cdot$ & 987 \\
       17 &       131.072 & 5,11 &          & 14,55 &                 & $\cdot$ & 1597 \\
       18 &       262.144 & 5,41 &          & 15,80 &                 & $\cdot$ & 2584 \\
       19 &       524.288 & 5,71 &          & 17,08 &                 &         & 4181 \\
       20 &     1.048.576 & 6,02 &          & 18,38 &                 &         & 6765 \\
       21 &     2.097.152 & 6,32 &          & 19,70 &                 &         & 10946 \\
       22 &     4.194.304 & 6,62 &          & 21,05 &                 &         & 17711 \\
       23 &     8.388.608 & 6,92 &          & 22,41 &                 &         & 28657 \\
       24 &    16.777.216 & 7,22 &          & 23,79 &                 &         & 46368 \\
       25 &    33.554.432 & 7,52 &          & 25,19 &                 &         & 75025 \\
       26 &    67.108.864 & 7,82 &          & 26,60 &                 &         & 121393 \\
       27 &   134.217.728 & 8,12 &          & 28,03 &                 &         & 196418 \\
       28 &   268.435.456 & 8,42 &          & 29,48 &                 &         & 317811 \\
       29 &   536.870.912 & 8,72 &          & 30,94 &                 &         & 514229 \\
       30 & 1.073.741.824 & 9,03 &          & 32,42 &                 &         & 832040 \\
       31 & 2.147.483.648 & 9,33 &          & 33,91 &                 &         & 1346269 \\
       32 & 4.294.967.296 & 9,63 &          & 35,42 &                 &         & 2178309 \\
       64 &              & 19,26 &          & 89,10 & Google          &         &  \\ \hline
    \end{tabular} \\[12pt]

    \begin{align*}
    \pi &\approx 3.14159265358979323846264338327950288419716939937510582097494 \\
    e &\approx 2.71828182845904523536028747135266249775724709369995957496697
    \end{align*}

%
%   \item[Pascalov trikotnik:] \mbox{} \\[12pt]
%     \tabcolsep=0.03cm
%     \hspace*{-20pt}
%     \begin{tabular}{rccccccccccccccccccccccccccccccc}
%      0:~~&    &    &    &    &    &    &    &    &    &    &    &    &    &    &    &  1\\
%      1:~~&    &    &    &    &    &    &    &    &    &    &    &    &    &    &  1 &    &  1\\
%      2:~~&    &    &    &    &    &    &    &    &    &    &    &    &    &  1 &    &  2 &    &  1\\
%      3:~~&    &    &    &    &    &    &    &    &    &    &    &    &  1 &    &  3 &    &  3 &    &  1\\
%      4:~~&    &    &    &    &    &    &    &    &    &    &    &  1 &    &  4 &    &  6 &    &  4 &    &  1\\
%      5:~~&    &    &    &    &    &    &    &    &    &    &  1 &    &  5 &    & 10 &    & 10 &    &  5 &    &  1\\
%      6:~~&    &    &    &    &    &    &    &    &    &  1 &    &  6 &    & 15 &    & 20 &    & 15 &    &  6 &    &  1\\
%      7:~~&    &    &    &    &    &    &    &    &  1 &    &  7 &    & 21 &    & 35 &    & 35 &    & 21 &    &  7 &    &  1\\
%      8:~~&    &    &    &    &    &    &    &  1 &    &  8 &    & 28 &    & 56 &    & 70 &    & 56 &    & 28 &    &  8 &    &  1\\
%      9:~~&    &    &    &    &    &    &  1 &    &  9 &    & 36 &    & 84 &    & 126 &    & 126 &    & 84 &    & 36 &    &  9 &    &  1\\
%     10:~~&    &    &    &    &    &  1 &    & 10 &    & 45 &    & 120 &    & 210 &    & 252 &    & 210 &    & 120 &    & 45 &    & 10 &    &  1\\
%     11:~~&    &    &    &    &  1 &    & 11 &    & 55 &    & 165 &    & 330 &    & 462 &    & 462 &    & 330 &    & 165 &    & 55 &    & 11 &    &  1\\
%     12:~~&    &    &    &  1 &    & 12 &    & 66 &    & 220 &    & 495 &    & 792 &    & 924 &    & 792 &    & 495 &    & 220 &    & 66 &    & 12 &    &  1\\
%     13:~~&    &    &  1 &    & 13 &    & 78 &    & 286 &    & 715 &    & 1287 &    & 1716 &    & 1716 &    & 1287 &    & 715 &    & 286 &    & 78 &    & 13 &    &  1\\
%     \end{tabular}
\end{description*}

\end{document}
% vim: spell spelllang=sl
% vim: foldlevel=99