===== Online Judges =====
===== Přehled =====
Používáme servery, viz [[https://cw.fel.cvut.cz/wiki/courses/laso2019/onlinejudges#servery|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.
===== Všeobecný postup =====
* Příjdu na vybraný server.
* Přihlásím se nebo, pokud ho ještě nemám, zřídím si tam konto (cca 1-2 min. času).
* Najdu odkaz "Problems" nebo "Browse problems" nebo "Practice" apod. a vyberu si úlohu nebo ji mám zadanou, tak jdu na ní rovnou.
* Řeším úlohu u sebe lokálně, napíšu kompletní kód řešení.
* V zadání zmáčknu tlačítko "Submit", vložím svůj kód a odešlu.
* Server buď rovnou ukáže výsledek nebo jdu do odkazu "My submissions" apod., kde je výsledek vidět.
* Pokud se nedaří, buď dále ladím a odevzdávám nebo vyberu jinou úlohu.
* Níže je odkaz na konkrétní úlohu (6591-Bus) s připraveným kódem řešení. Zájemci si vyzkouší ho odevzat, aby se seznámili s typickým provozem serveru. Tento kód lze cvičně odevzdat i pozměněný a koukat na hybová hlášení serveru.
----
===== Servery =====
**Server:** [[https://icpcarchive.ecs.baylor.edu/index.php | ACM - ICPC Live Archive]],
Ukázková úloha:
Levý sloupeček: //Browse problems --> Regionals 2013 --> Europe --> Central --> 6591-Bus//
Nebo rovnou: [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=610&page=show_problem&problem=4602|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:** [[http://uva.onlinejudge.org/| UVA Online Judge]]
-----
**Server:** [[http://www.spoj.com/ | Sphere Online Judge]],
-----
**Server:** [[http://codeforces.com/ | Codeforces Online Judge]],
===== Jak na řešení =====
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".
===== Jak na kódování =====
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 [[https://uva.onlinejudge.org/index.php?option=com_content&task=view&id=15&Itemid=30|Submission specification]] a [[https://uva.onlinejudge.org/index.php?option=com_content&task=view&id=16&Itemid=31|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 [[https://www.udebug.com/|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: [[https://www.google.com/advanced_search?hl=en|google]], [[http://stackoverflow.com/|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í.