Mopadulo
Dzisiaj zajmiemy się rozwiązaniem zadania mopadulo z potyczek algorytmicznych 2021. W zadaniu tym pytają się nas na ile sposobów można podzielić ciąg na spójne fragmenty tak aby suma każdego fragmentu modulo p była parzysta. Dla przykładu dla ciągu [10, 1, 5, 8] i p = 11 są trzy takie podziały: Zacznijmy od przestawienia algorytmu dynamicznego […]
Poborcy podatkowi
Dzisiaj zajmiemy się zadaniem Poborcy podatkowi z Potyczek Algorytmicznych 2021. W zadaniu mamy do dyspozycji drzewo ważone na krawędziach. Chcemy wybrać zbiór rozłącznych krawędziowo ścieżek o długości 4, który maksymalizuje sumę wartości na krawędziach. Mamy drzewo. Chcemy coś maksymalizować. Więc prawdopodobnie trzeba użyć programowania dynamicznego na drzewach. Dla każdego wierzchołka v chcemy policzyć cztery wartości: […]
Od deski do deski
Dzisiaj zajmiemy się zadaniem z Potyczek Algorytmicznych 2021. Blokiem nazywamy co najmniej dwuelementowy ciąg liczb naturalnych, rozpoczynający się i kończący tą samą liczbą. Mówimy że ciąg jest ciekawy jeśli jest pusty lub gdy powstaje przez sklejenie ciekawego ciągu z blokiem. Zadanie polegało na policzeniu ile jest wszystkich n-elementowych, ciekawych ciągów, w których elementy są mniejsze […]