Používáme servery, viz seznam níže, se kterými se pracuje víceméně jednotným způsobem. Každý server obsahuje množství úloh z různých oblastí a s různým stupněm obtížnosti. Zadání každé úlohy specifikuje přesně, co se má spočítat, jaký je formát vstupních a výstupních dat.
Uživatel sestaví u sebe na svém stroji kód řešení a ten odevzdává na server k příslušné uloze.
Všechny požadavky úlohy je nutno přesně dodržet.
Programovací jazyk řešení může být vždy libovlný z poskytované množiny toho kterého serveru, všude mají C/Cpp, Javu, Python a někdy mnoho dalších.
Vyhodnocovací aparát na serveru se pochopitelně snaží najít nedostatky v logice nebo v kódu nebo v rychlosti odevzdaného řešení a spouští proto řešení na účelově připravených datech, která kontrolují, zda jsou správně ošetřeny všechny okrajové/mezní případy.
Vyhodnocení a chybová hlášení serverů jsou velmi lakonická (Accepted, Wrong Answer, Runtime Error, Time Limit Exceeded apod, bez dalších parametrů), je nutno se obrnit trpělivostí, svůj kód psát co nejchytřeji (nikoli nesrozumitelně!) a uvážlivě ladit.
Server: ACM - ICPC Live Archive,
Ukázková úloha:
Levý sloupeček: Browse problems –> Regionals 2013 –> Europe –> Central –> 6591-Bus
Nebo rovnou: Regionals 2013 Europe - Central, 6591 - Bus
Malé ukázkové řešení v Javě:
import java.util.Scanner; public class Main { // ACM ICPC Archive 6591 public static void main(String[] args) { // precompute results int[] results = new int[31]; results[1] = 1; for (int i = 2; i <= 30; i++) results[i] = 2 * results[i - 1] + 1; // produce output int N, k; Scanner input = new Scanner(System.in); N = input.nextInt(); for (int i = 0; i < N; i++) { k = input.nextInt(); System.out.println(results[k]); } } }
Server: UVA Online Judge
Server: Sphere Online Judge,
Server: Codeforces Online Judge,
1. Čti pozorně zadání. Když ti program později nebude fungovat, ujisti se vždy nejprve, že zadání rozumíš zcela přesně.
2. Z uvedené maximální velikosti dat odhadni, jakou asymptotickou/časovou/paměťovou složitost řešení zadavatel předpokládá, a podle toho vymýšlej a posuzuj svůj aloritmus řešení. “Brute force” přístup nefunguje zdaleka pokaždé.
3. Dávej pozor na “okrajové”, “degenerované” případy velmi malých dat (velikosti 0, 1 apod.), někdy se chovají jinak než “regulérní” a musí se zvlášť obsloužit.
4. Svoje potíže v řešení diskutuj s co největším počtem lidí. Rozhovor tě nutí uspořádat si myšlenky a srozumitelně je formulovat, leckdy si uvědomíš svou chybu nebo potřebné souvislosti, ještě než tvůj protějšek odpoví. Proto se doporučuje mluvit i na benevolentní členy rodiny a přátele, kteří nejsou “z oboru”.
Celé řešení se běžně vejde do jednoho souboru, nerozděluj kód do více import/include souborů.
Všechny vstupy je nutno číst ze standardního vstupu a všechny výstupy je nutno vypisovat na standardní výstup. Při ladění u sebe lze samozřejmě používat vlastní disk, ale pokus přístup k disku na serveru skončí běhovou chybou.
Přečti si na UVA Submission specification a Verdict information, řeknou ti, co a jak odevzdat a co si systém myslí o tvém kódu. Podobná pravidla platí také na dalších serverech.
Při ladění na UVA používej uDebug, odkaz je u každého zadání, ověříš si snadno svoje řešení.
Neověřuj, jestli formát dat, která načítáš, odpovídá skutečně zadání, můžeš se spolehnout, že odpovídá, autoři úlohy tomu věnují velkou pozornost.
Omez a nespoléhej na objektový přístup. Prodlužuje kód mírně a čas běhu programu někdy drasticky.
Neztrácej čas lokálními pseuodoptimalizacemi (x+=1 vs. x=x+1, apod.), ty nezachraňují koncepčně pomalý kód.
Měj představu o rychlosti nejběžnějších metod. Např. knihovní metody typu x.contains(y), z.remove(w) bývají záludné svou pomalostí.
Nauč se efektivně ladit: Používej trasovací výpisy, debugger je někdy na nic. Najdi první výskyt problému a ten vyřeš, teprve pak řeš další výskyt a další, nechtěj uhodnout najednou “proč mi to nefunguje”. Laď na různých datech, vymysli si svoje malá ladící data.
Ptej se online: google, stackoverflow, většinou ví, jak na to.
I/O - Nepiš vlastní superchytré procedury načítání/tisku. Najdi na síti základní ukázky, přizpůsob si je, pokud chceš, a používej pořád. S 2-3 variantami většinou pohodlně vystačíš. V Javě nepoužívej Scanner ani string.split(), jsou příliš pomalé.
Problémy s I/O a s formátem vstupu/výstupu nelaď ve svém GUI, neumí většinou správně emulovat systémové I/O prostředí. Používej příkazový řádek pro překlad a spouštění programu, zejména pro textový I/O a potíže s “neviditelnými” znaky (EOL, EOF, TAB apod.).
SPOJ - čti komentáře řešitelů pod zadáním úlohy, mohou napovědět.
Specificky na každém Online Judge:
Runtime Error s časovou známkou 0.000 indikuje, že asi zlobí načítání dat. S časem větším než 0.000 je načítání asi dobře a zlobí něco dál v kódu.
Při Runtime Error postupně zakomentuj více a více svého kódu a stále odevzdávej, dokud nedostaneš Wrong Answer. Tak odhalíš, která část kódu program shodí.