Algorytmika średniozaawansowana

Aby móc wysyłać zgłoszenia należy zarejestrować się do contestu


Kółka odwołane aż do powrotu funkcjonowania szkoły

Zważywszy na to, że panująca sytuacja nie wygląda jakby miała zamiar się szybko skończyć to jeżeli ktoś nie umie czegoś rozwiązać i chciałby zapytać o wskazówkę/rozwiązanie/"wskazanie buga w kodzie" to zachęcam do kontaktu ze mną lub z resztą kadry. W zależności od tego jaki sposób preferujecie można albo zadać pytanie tutaj na sio, napisać na messengerze (Michał Kardaś, zdjęcie z patyczakiem), mailowo (mkmkl93@gmail.com) a jeżeli ktoś preferuje jeszcze inną opcję to wystarczy zadać tutaj pytanie.


Tematem będą Tekstówki II: Manacher, tablica pref (algorytm Z).


Erraty do kółka z zasady włączeń i wyłączeń

Strasznie mi się pomyliły wzorki do funkcji phi Eulera dlatego wstawiam linka, z którego polecam brać w przyszłości wzorki. W praktyce ważniejsze od pamiętania wzorków, bo ich się używa głównie do wyliczania wartości tej funkcji a dopiero na bardziej zaawansowanym poziomie człowiek zaczyna się z nimi bawić, jest pamiętanie definicji tej funkcji, czyli liczba mniejszych liczb względnie pierwszych z nią
Funkcja phi Eulera Wikipedia
Kod na sito z funkcją phi
Zadanie na zasadę włączeń i wyłączeń

Jaki jest początkowy poziom kółka? Taki że trzeba mieć dobrze opanowanie następujące zagadnienia:

  • Różne sortowania, operatory do sorta
  • Wyszukiwanie binarne (zwykłe i to "po wyniku" (to to samo))
  • DFS, BFS
  • Dijkstra
  • Gąsienica
  • STL (mapy, sety, iteratory, kolejki, sort, etc.)
  • Najprostsze dynamiki i zachłany
  • Drzewa przedziałowe typu punkt-przedział i przedział-punkt
  • Podstawowe wskaźniki
  • Sumy prefiksowe (1D i 2D)

Kody z kółek będą w miarę możliwości wstawiane tutaj


Informacje o kółkach:

  1. 01.10.2019 | godz. 16:00 | Kółko organizacyjne, wyszukiwanie binarne po wyniku, drzewa przedziałowe
  2. 08.10.2019 | godz. 16:15 | Drzewa przedziałowe I: przedział-przedział, zamiatanie
  3. 15.10.2019 | godz. 16:15 | Grafy I: Grafy warstwowe, drzewa przedziałowe na drzewach, [pre | in | post]order
  4. 22.10.2019 | godz. 16:15 | Dynamiki I: najdłuższe wspólne podsłowo, najdłuższy podciąg rosnący, podtablica o największej sumie,
  5. 29.10.2019 | godz. 16:15 | Dynamiki II: problem plecakowy, dynamiki na drzewach
  6. 05.11.2019 | godz. 16:15 | Tekstówki I.1: Hasze
  7. 12.11.2019 | godz. 16:15 | Tekstówki I.2: KMP
  8. 19.11.2019 | godz. 16:15 | Grafy II: FU i MST
  9. 26.11.2019 | godz. 16:15 | Grafy III: toposort i SCC
  10. 03.12.2019 | godz. 16:15 | Grafy IV: LCA
  11. 10.12.2019 | godz. 16:15 | Grafy V: Bellman-Ford i Floyd-Warshall
  12. 07.01.2020 | godz. 16:15 | Teoria liczb i szybkie potęgowanie
  13. 14.01.2020 | godz. 16:15 | Geometria I: iloczyn wektorowy/skalarny, otoczka wypukła, para najdalszych punktów, przecinanie się odcinków, pole wielokąta
  14. 28.01.2020 | godz. 16:15 | Maski bitowe, zasada włączeń i wyłączeń
  15. 04.02.2020 | godz. 16:00 | Pierwiastki
  16. 03.03.2020 | godz. 16:15 | Macierze
  17. 10.03.2020 | godz. 16:15 | Grafy VI: Funkcja low, grafy dwuspójne
  18. 17.03.2020 | godz. 16:15 | Tekstówki II: Manacher, tablica pref (algorytm Z)
  19. 24.03.2020 | godz. 16:15 | Tekstówki III: KMR, tablica sufiksowa w O(nlogn), LCP
  20. 31.03.2020 | godz. 16:15 | Teoria gier
  21. 07.04.2020 | godz. 16:15 | Zachłany
  22. 21.04.2020 | godz. 16:15 | Geometria II: najbliższa para punktów, punkty wewnątrz wielokątów, może coś jeszcze
  23. 28.04.2020 | godz. 16:15 | Dynamiki III: ciekawe wariacje problemu plecakowego
  24. 12.04.2020 | godz. 16:15 | Grafy VII: skojarzenia w grafach dwudzielnych
  25. 19.05.2020 | godz. 16:15 | Algorytm Mo
  26. 26.05.2020 | godz. 16:15 | 2-SAT
  27. 02.06.2020 | godz. 16:15 | Tekstówki IV: TRIE, Aho-Corasick
  28. 09.06.2020 | godz. 16:15 | Dynamiki IV: zaawansowane dynamiki, Convex Hull Trick
  29. 16.06.2020 | godz. 16:15 | Grafy VIII: przepływy (Ford-Fulkerson, Edmonds-Karp, Dinic)
  30. 16.06.2020 | godz. 16:15 | Ostatnie kółko, różne ciekawe zadanka

Questions and news

Author Date Category Topic
Janek Partyka 2020-02-04 13:28:00 General UWAGA!!! WYJĄTKOWA ZMIANA SALI
Janek Partyka 2019-10-09 23:52:00 General Kody z kółek
Janek Partyka 2019-10-01 19:36:00 General Wysyłanie zgłoszeń