Python

Input/Output

Nie je hádam nič horšie než striedať input() a print(). Každý input() flushne print() a všetko bufferovanie ide do kanála. Ak máme úlohu s veľa sadami (napríklad milíon), oplatí sa nám výsledky uložiť do poľa a vypísať až na koniec.

Podobne, aj v úlohách kde máme veľa riadkov vstupu (a nie nutne veľa riadkov výstupu) sa nám môže oplatiť nevolať milíon krát input. Radšej si načítame celý vstup naraz a potom už si riadkovanie robíme sami.

import sys
lines = sys.stdin.read().split("\n")

Vstavané funkcie

Oheň vie byť sluha i pán. Tak isto vstavané funkcie nám vedia pomôcť i uškodiť. Ak chceme zistiť maximum poľa, nenájdeme lepší prístup než funkciu max(). Ak chceme zistiť maximum dvoch prvkov, nenájdeme horší prístup než funkciu max().

V programovaní sa často snažíme nájsť najlepší výsledok, či už pri hľadaní najkratšej cesty alebo dynamike. Často sa teda v kóde vyskytne výraz best = max(best, aktual). Python je v takomto prípade hlupáčik a tento jeden riadok je v niektorých dynamikách najpomalšia časť celého kódu. Nahradíme ho vlastným if aktual > best: best = aktual a získame niekedy 2x rýchlejší kód.

Snažme sa používať čo najviac vstavaných funkcií, pretože nám uľahčujú život a skrášlujú kód, až na prípady kedy nie.

Ďalej upozornime, že existujú vstavané funkcie a štruktúry bisect.bisect_left, collections.Counter, collections.deque a heapq. Neodporúčame používať modul queue.

Globálny skôp

Zober svoj kód. Daj ho do def solve():. Zavolaj solve(). Python je znova hlúpučký a global kód vie byť triviálne 3x pomalší než ten istý kód s týmito dvoma riadkami navyše.

https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function

PyPy

Väčšina týchto optimalizácii je zbytočná ak jednoducho použijeme PyPy. :/

Najväčí trik

Čo je najväčší trik? Optimalizovať keď treba. Urob si odhad časovej zložitosti. Zakomentuj časti kódu. Zamysli sa nad worst case prípadom. Ak netreba optimalizovať, tak netreba!

Úloha na grafe, program TLEie. Možno pomôže ak sem dám if podmienka: break. Problém je, že táto podmienka sa nikdy nespustí na grafe tvaru cesta a na ňom to tiež dáva TLE. Tento if je potom iba zbytočný kód, v ktorom môže byť chyba, ktorý musím potom už navždy zvažovať či mi kód vlastne nespomaluje, či mi nespôsobí WA, ...

Počul som že max() je pomalé tak všade používam if. Ten max by sa ale počas behu programu zavolal sto krát a iná časť kódu, ktorú si neoptimalizoval/a sa vykoná sto milíonov krát. Gratulujem, máš neprehľadný rozvetvený kód ktorý nie je o nič rýchlejší.

Venujte svoju pozornosť tam kam treba a keď treba. A často aj keď si myslíte, že treba, tak netreba a problém je celkom iný než by sa zdalo.

C++

Rýchle IO

Stačí cin.tie(0)->sync_with_stdio(0);. Nič viac. cout.tie(0) je zbytočné.

Vstavané funkcie

Používajte begin(x), end(x), size(x) namiesto x.begin(), ... Funguje to aj na C polia.

Užitočné funkcie ktoré už dúfam poznáte: all_of, find, count, swap, fill, unique, reverse, sort, lower_bound, max_element, next_permutation. Povinne pozrieť https://en.cppreference.com/w/cpp/algorithm (ale lepšie je to vidno na https://cplusplus.com/reference/algorithm/)

Príklad použitia:

sort(begin(pole), end(pole));
pole.resize(unique(begin(pole), end(pole)) - begin(pole));

alebo

set<int> set_pole(begin(pole), end(pole));
vector<int> unique_pole(begin(set_pole), end(set_pole));

auto maxi = *max_element(begin(pole), end(pole));

Vypisovanie štruktúr

Stačia dva operator<< overaloady na vypisovanie všetkého:

// vypisovanie ľubovolného iterovateľného kontajnéru
// bez kolízie voči string a const char* vďaka basic_ostream<A, B> namiesto ostream
template <typename A, typename B, typename C>
basic_ostream<A, B>& operator<<(basic_ostream<A, B>& os, const C& cont) {
    for (auto it = begin(cont); it != end(cont); ++it)
        os << (it == begin(cont) ? "" : " ") << *it;
    return os;
}

// plus vypisovanie pairov a mame aj associatívne kontajnery
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    return os << '(' << p.first << ", " << p.second << ')';
}

https://codeforces.com/blog/entry/68920

Polia

Skúšali ste niekedy robiť dynamiku? Otrava že. Ale menej ak použijeme C-čkové polia. Ach jaj C++...

int D[100][100][100] = {0};
// ak chceme niečo iné ako 0, pozor, memset nefunguje lebo to robí po bajtoch
fill((int*)begin(a), (int*)end(a), 1e9);

C++ má svoj std::array<T, N>. Celkom nifty štruktúra, lepšie array<int, 3> než tuple<int, int, int>. Nájdite si miesta kde vám to pomôže.