Nazywam się Tomasz Idziaszek, a to jest miejsce, w którym gromadzę moje zapiski dotyczące algorytmów przydatnych w konkursach programistycznych. Zacząłem w marcu 2018 i planuję publikować nowy artykuł co około trzy miesiące. Z uwagi na to, by materiały na tej stronie mogły być przydatne jak najszerszej grupie czytelników, większość z nich jest w języku angielskim. Zachęcam również do sprawdzenia listy książek, których byłem redaktorem i autorem.
Notatki
Dynamic programming on trees with minimal memory
Szczegółowa analiza, jak rozwiązać klasyczne zadanie korzystające z metody programowania dynamicznego na drzewie, ale używając jak najmniej pamięci operacyjnej. Pokazuje nieefektywność standardowego podejścia (wektory, rekursja), opisuje różne reprezentacje drzew w pamięci (z pomysłowymi metodami kompresji, ale umożliwiającej obchodzenie drzewa) i parę trików optymalizujących obliczenia. EN
Opublikowane w marcu 2018
Survey of knapsack problems
Opis licznych wariantów problemu plecakowego rozwiązywanych przeważnie przy pomocy programowania dynamicznego. Zawiera wariant zero-jedynkowy, nieograniczony i ograniczony, jak również plecaki z elementami o różnych kosztach, o ograniczonym czasie życia, związane zależnościami itd. EN
Opublikowane w maju 2018 (prace w toku; dostępna pierwsza część)
Counting perfect matchings in grids and planar graphs
Opis algorytmów zliczających doskonałe skojarzenia w pewnych klasach grafów. Omawia trudność tego problemu dla grafów ogólnych związaną z obliczaniem permanentu i pokazuje dwa pomysłowe algorytmy, które sprowadzają ten problem dla krat i grafów planarnych do obliczenia wyznacznika sprytnie zmodyfikowanych macierzy. EN
Opublikowane we wrześniu 2018 (prace w toku; dostępna pierwsza część)
Increasing subsequences and related problems
Opis algorytmów dla różnych problemów związanych ze znajdowaniem podciągów rosnących w ciągu liczb. EN
Opublikowane w grudniu 2018 (prace w toku; dostępna pierwsza część)
Maximum-subarray and related problems
Opis algorytmów dla problemu znajdowania spójnej podtablicy o największej sumie w danej tablicy liczb. Omawia kilka klasycznych algorytmów, jak również mniej klasyczne rozwiązujące wariant, w którym znajdujemy kilka rozłącznych podtablic. EN
Opublikowane w marcu 2019 (prace w toku; dostępna pierwsza część)
Algorithms for arithmetic in Fibonacci and golden ratio representations
Omówienie alternatywnych sposobów reprezentacji liczb całkowitych, używając liczb Fibonacciego, jak również pozycyjnego systemu liczbowego o niewymiernej podstawie równej złotej proporcji. Zawiera również wydajne algorytmy dla operacji arytmetycznych wykonywanych bezpośrednio na tych reprezentacjach. EN
Opublikowane w lipcu 2019 (prace w toku; dostępna pierwsza część)
Solutions to problems from IOI 2018
Szczegółowe rozwiązania wszystkich sześciu zadań z Międzynarodowej Olimpiady Informatycznej 2018, rozgrywanej w Japonii w mieście Tsukuba. EN
Opublikowane w grudniu 2019