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 […]
Co zrobić w dniu próbnym
Żaden szanujący się konkurs algorytmiczny, nie odbywa się bez dnia próbnego (albo chociaż sesji próbnej). Dzień próbny jest potrzebny organizatorom, aby upewnić się, że wszystko zostało dopięte na ostatni guzik. Działa sprawdzaczka, zadania zostały odpowiednio załadowane, komputery zostały odpowiednio przygotowane i tak dalej. Dzień próbny jest również istotny dla zawodników, aby mogli się zapoznać ze […]
Płytkie nawiasowania
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Płytkie nawiasowanie”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. Opiszę tu pokrótce o co w zadaniu chodziło, ale zanim to nastąpi to wytłumaczę czym jest poprawne nawiasowanie. Poprawne nawiasowanie to taki napis złożony z symboli ( oraz ) w którym każdy nawias otwierający ma […]
Zboże
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Zboże”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie w zadaniu było dane ukorzenione drzewo z wagami na krawędziach oraz ciąg wierzchołków z tego drzewa. Dla każdego wierzchołka z ciągu należało policzyć jego sumaryczną odległość do wszystkich wierzchołków leżących w ciągu przed […]
Wyprzedzanie
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Wyprzedzanie”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie: jednym pasem jedzie n ciężarówek. Pasem równoległym ciężarówki wyprzedza Bitazar (zły brat bliźniak Bajtazara). Policja Bajtocka chce teraz ukarać Bitazara mandatem. Wysokość mandatu zależy od tego ile razy Bitozar mógł podczas wyprzedzania zjechać […]
Pociąg towarowy
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Pociąg towarowy”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie w zadaniu mieliśmy dany ciąg oraz jego podciąg. Niestety – mając takie dane nie jesteśmy w stanie określić które dokładnie elementy zostały wybrane do podciągu. Dla przykładu: jeśli ciągiem jest 1 3 […]
Kolorowy wąż
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Kolorowy wąż”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie: w zadaniu graliśmy w węża i zjadaliśmy kolorowe jedzenie z planszy. Gdy wąż zjadł jedzenie, zwiększał się o jeden segment z przodu i segment ten stawał się koloru tego jedzenia. Podczas gry […]
Jak zmniejszyć złożoność swojego algorytmu?
W zadaniu Wyspa z IX Olimpiady Informatycznej danych było n miast ułożonych na okręgu oraz odległości między dwoma sąsiednimi miastami. Należało znaleźć największą odległość między dwoma miastami, przy czym odległość między dwoma miastami definiujemy jako mniejszy z dystansów: zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara. Na rysunku powyżej widzimy przykładową wyspę. […]
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 […]