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 […]
Fioletowe żabki
Pewna czarownica omyłkowo odstawiła fiolkę z bardzo silną trucizną na półkę z innymi fiolkami i teraz nie pamięta, która z nich zawiera niebezpieczną substancję. Postanowiła ona przetestować fiolki za pomocą żabek, które są na truciznę odporne, ale u których po wypiciu trucizny następuje efekt uboczny w postaci zmiany koloru na fioletowy. Zmiana koloru następuje w […]
Pionek na planszy
Podczas rekrutacji, moglibyśmy trafić na następujące zadanie: W linii prostej znajduje się n pól. Na każdym polu znajduje się pewna liczba całkowita. Na polu z numerem pierwszym znajduje się pionek. Pionek może poruszać się po planszy w prawą stronę, ale w każdym kroku nie może poruszyć się o więcej niż k pól. Jaka jest możliwie […]
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 […]