===== Online Judges ===== ===== Přehled ===== Používáme servery, viz [[https://cw.fel.cvut.cz/wiki/courses/laso2020/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í.