Notka druga, w której dowiadujemy się dlaczego warto zajmować się programowaniem konkursowym
Jest wiele powodów dla których warto zainteresować się programowaniem konkursowym. Oto kilka z nich: Ułatwiona edukacja. Tytuł finalisty Olimpiady Informatycznej daje wolny wstęp na wiele polskich uczelni. Podobnie tytuł finalisty Olimpiady Informatycznej Juniorów daje wolny wstęp do szkół ponadpodstawowych. Do tego gwarantowana ocena celująca z informatyki i zwolnienie z matury z informatyki (nawet jeśli szkoła […]
Notka pierwsza, w której poznajemy nasze pierwsze zadanie i je rozwiązujemy
Zamiast przydługawego wstępu, przejdźmy od razu do rzeczy. Oto nasze dzisiejsze zadanie: Problem 1: Polski Chiński Mur Tomek próbuje wybudować mur z klocków. Mur przypomina konstrukcję złożoną z dwóch rzędów trójkątów. Każdy z nich składa się z 2n-1 trójkątów. Rzędy są zwrócone do siebie dłuższą podstawą. Dla n = 7 konstrukcja wygląda następująco Do konstrukcji […]
Replace the Numbers
Dzisiaj chciałem wam opowiedzieć o tym jak przekombinowałem rozwiązanie zadania Replace the Numbers z treningów codeforce. Zadanie należało do tych prostszych. Mieliśmy tablicę na której mogliśmy wykonywać dwa rodzaje operacji: Wstawienie elementu v na koniec tablicy Zamiana wszystkich wystąpień elementu a na element b (będę oznaczał jako a -> b) Mając daną listę instrukcji należało […]
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 […]