Moje rzeczy
Mój GitHub
Algorytmiczne rzeczy
(Wszystko w C++)
- KTL – skromnie nazwany Kubin Template Library zawiera implementacje różnych algorytmów i struktur danych, z tytułowymi szablonami w pakiecie, które mają ułatwić adaptację do problemu. Z tych fajniejszych:
- Wydumane drzewo przedziałowe, napisane tak, żeby było łatwo napisać prawie że dowolne operacje (na szablonach).
- Tabela potęgowa, czyli słownik podsłów bazowych
- Drzewo Fenwicka, razem z wersją wielowymiarową
- Test pierwszości Millera-Rabina oraz metoda faktoryzacji rho Pollarda. Ten pierwszy ma całkiem dobrych świadków ściągniętych z czeluści Internetu, dzięki czemu jest całkiem szybki.
- Aho-Corasick
- Hashe wielomianowe z szablonowanymi modulo (w tym szybkie modulo przez liczby Mersenne'a) oraz szablonem do wielokrotnego hashowania.
- Dużo mniej i bardziej dziwnej matmy, w tym: eliminacja Gaussa, logarytm dyskretny, pierwiastek dyskretny, szukanie generatora, sito liniowe, całkowanie numeryczne wzorem Simpsona, rozwiązywanie układów równań modularnych z CRT.
- Minty, czyli modularne inty. Przydają się jak chcemy adaptować algorytm bardziej ogólny do arytmetyki modularnej, np. eliminację Gaussa czy FFT (NTT). W skrócie implementują wszystkie operacje arytmetyczne, ale zawsze się modulują - poza tym udają zwykły typ całkowity.
- FFT i NTT
- Rozwiązywanie 2-SATa
- Ekscentryczne grafówki: Przepływy (Dinic), minimalna arborescencja (algorytm Edmondsa), dominatory w DAGu, Turbo matching (maksymalne skojarzenie w grafie dwudzielnym)
- Wavelet Tree
- Algorytm Duvala (minimalna leksykograficznie rotacja cykliczna w czasie liniowym)
- I parę bardziej ogólnych: lepszy sposób tworzenia wielowymiarowych wektorów, zszablonowane zaawansowane operacje bitowe z rozszerzeń g++, szybkie I/O (prawie na pewno działa!).
- Moje zadanka
- Zbiór zadanek zrobionych
Moje ulubione projekty
- Hörnchen [Python] – roguelike w Pythonie z losowym generowaniem mapy i całkiem fajnymi efektami. Pisany od zera w pygame. Niestety, nie dokończyłem go, i nie do końca jest jakiś cel gry, ale działa przyzwoicie.
- qTetris [Python] – Starszy projekt w którym jest Tetris, ale ze sztuczną inteligencją, która powstała drogą algorytmu genetycznego. Także pygame.
- io-mazegen [Python] – Generator losowych labiryntów z algorytmem mego autorstwa z wizualizatorem procesu generacji i szukaniem najkrótszej ścieżki algorytmem A*. Siedzi też w Hörnchen.
- Helix [Python] – modularny bot do Discorda, którego głównym zadaniem jest tworzenie wygodnych ankiet opierających się na reakcjach emoji. Obecnie działa na bardzo aktywnym Staszyc 02.
- iotapack [Python] – skrypcik do przygotowywania paczek na SIO2 (dzięki czemu nie trzeba ręcznie robić archiwum i przerzucać pliki, ani bawić się czasami nieintuicyjnym układem plików).
- siogo [Python] – command line interface do SIO2. Spytacie: czemu? To proste: okazuje się, że słabe i lekkie laptopy mają problemy z sensowną obsługą SIO2, dzięki czemu taka alternatywa okazuje się bardzo użyteczna. Polecam wypróbować do submitowania. Hasła są wczytywane za pomocą Pythonowego
getpass
, więc nie są wyświetlane podczas wpisywania (tak jak podczas wpisywania hasła dosudo
).