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).