Wielki Zderzacz Termionów
Autorzy zadań do Potyczek Algorytmicznych trzymają naprawdę wysoki poziom. Jak oni wymyślają te zadania? Nie wiem. Krótkie streszczenie treści zadania W zadaniu Wielki Zderzacz Termionów mamy trzy rodzaje cząstek elementarnych: Czerwony (C), Zielony (Z) i Niebieski (N). Cząstki elementarne ustawia się w rzędzie i reagują ze sobą. Dwa sąsiednie termiony Czerwone mogą zamienić się w […]
Liczba potyczkowa
Rozpoczęła się runda próbna tegorocznych Potyczek Algorytmicznych. O tym co można sprawdzić w rundzie próbnej napisałem w poprzedniej notce. Zwykle zadania w dniu próbnym są bardzo łatwe. Klasycznym przykładem jest zadanie w którym należy dodać dwie liczby do siebie. Ja chciałbym wrócić pamięcią dwa lata wstecz, kiedy to na dniu próbnym pojawiło się zadanie, którego […]
Drzewa Czerwono-Czarne [Potyczki]
Dzisiaj będziemy rozwiązywać zadanie Drzewa Czerwono-Czarne z Potyczek Algorytmicznych 2021. Zadanie wprawdzie z dywizji C ale było ciekawe i przyniosło mi bardzo dużo radości. W zadaniu mieliśmy dane drzewo, którego wierzchołki zostały pomalowane na czarno i czerwono. Możemy wykonać ruch polegający na wzięciu krawędzi łączącej dwa wierzchołki różnego koloru i przemalowaniu jednego z tych wierzchołków […]
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 […]