Trénink na ACM ICPC contest

Thus spake the Master Programmer:
"After three days without programming, life becomes meaningless."

Toto jsou stránky tréninku na soutěž ACM ICPC. Na předmětu se podílejí David Bernhauer, Vašek Blažej, Pepa Malík, Morass, Ondra Suchý a Tomáš Valla.

Cíl předmětu je jasný: řešit a na místě programovat skutečné soutěžní úlohy, trénovat algoritmické myšlení i rychlé kódění, a to vše v týmu.

Každý, kdo má byť jen malinký zájem se pocvičit, je vřele vítán! V případě zájmu se stavte nebo napište mail.

Technicky se zápis na opakovaný trénink (každý semestr) řeší tak, že jsou vypsány předměty BI-ACMx, kde x je nějaké číslo, a člověk si zapíše to číslo, které ještě nemá vychozené. Číslo rozhodně neznamená, že by mezi jednotlivými předměty byla nějaká návaznost nebo prerekvizita.

Několik technických informací k předmětu

Užitečné odkazy

Desatero dovedností úspěšného soutěžícího

  1. Rychle přečíst a pochopit velké množství zadání v angličtině
  2. Rychle sestavit "matematický model" problému, tedy zahodit balast a definovat jádro věci
  3. Rychle identifikovat, v čem spočívá obtížnost úloh
  4. Umět se rychle rozhodnout, kterým úlohám se věnovat, a které jsou "neřešitelné" (neboli si vypěstovat intuici, co bude lehké a co těžké)
  5. Vypěstovat si intuici, který problém vede na jaké řešení a jakým zhruba asi algoritmem
  6. Umět tu intuici dotáhnout do správného algoritmu
  7. Umět rychle a bezchybně algoritmus nakódit
  8. Umět ten kód zdebugovat, ale nikoli u kompu, nýbrž vytištěný na papíře
  9. Umět si povídat v týmu a úlohy řešit týmově (ve fázi vymýšlení to HODNĚ pomáhá, ale i ve fázi kódění a debugování), velmi důležitá dovednost
  10. Zvládat praktickou psychologii soutěže (dlouhé soustředění, deprese z postupu ostatních týmů, časový stres, apod.)

Seznam užitečných algoritmů

Tato sekce je (a nejspíš navždy bude) ve výrobě

Jakkoli je důležité umět vymýšlet algoritmu vlastní, často se pro řešení některých úloh může hodit použít nějaký existující algoritmus či datovou strukturu, který se jenom více či méně přiohne. Následující seznam algoritmů doporučujeme si předprogramovat a vzít ho na soutěž vytištěný. Dejte si záležet, ať je napsaný úsporně a přehledně, nebudete mít čas přepisovat kilometry zdrojáku. Velmi důležité je, ať je kód napsaný vlastnoručně, budete ho typicky modifikovat, tak ať se v něm vyznáte.

Seznam je mírně roztříděný do kategorií, pokud něco postrádáte, dejte vědět.

Základní datové struktury

Takové ty ultrajednoduché jako spojáky, zásobníky, fronty apod. snad ani nemusím psát.

Vyhledávání a třídění

Základní grafové algoritmy

Je určitě třeba mít přehled i v teorii, jaké skutečnosti například platí pro rovinné grafy, stromy, apod.

Pokročilejší grafy

Stringové algoritmy

Aritmetika a teorie čísel

Geometrie

Velmi zákeřné úlohy na to neudělat v kódění chybu, spousta speciálních případů, apod. V podstatě, pokud nemáte tyto algoritmy předkóděné, spíše vůbec nedoporučuji dotyčnou úlohu řešit (riziko chyby je příliš velké). Důležité je také co nejvíce oddálit a minimalizovat výpočty v doublech.

Dynamické programování

Zde je asi podstatně důležitější praxe, ale následující problémy jsou poměrně typické a spousta dynamik je jim podobná.

Speciality