Delta mi!

W rozważaniach naszych nie będziemy chwilowo dążyli do ścisłej definicji algorytmu ani do formalizacji zapisu algorytmów. Celem naszym będzie wyrobienie u Czytelnika przekonania, że algorytm jest uściśleniem przepisu postępowania prowadzącego do zamierzonego celu.

W tym miesiącu rozwiążemy zadanie Darmowe rozmowy z Obozu Naukowo-Treningowego im. Antoniego Kreczmara w roku 2011.

W zeszłym miesiącu zajmowaliśmy się uogólnieniem następującego zadania: dla danego kwadratu rozmiaru podzielonego na pól, z których niektóre były zabronione, należało znaleźć prostokąt o największym polu, który nie zawierał żadnego zabronionego pola. W tym numerze rozważymy jeszcze inną wariację tego zadania, a mianowicie będziemy szukać największych prostokątów, które zawierają co najwyżej zabronionych pól (nazwiemy je prostokątami prawie pustymi).

W tym miesiącu zajmiemy się dość klasycznym zadaniem. Dany jest kwadrat rozmiaru podzielony na pól, przy czym niektóre pola są zabronione. Dowolny zawarty w tym kwadracie prostokąt, który nie zawiera żadnego pola zabronionego, nazwiemy prostokątem pustym. Należy znaleźć pusty prostokąt o jak największym polu.

W pierwszej części tego artykułu pokazaliśmy, że dla szczególnej klasy grafów (kraty i ich podgrafy), istnieje działający w czasie wielomianowym algorytm, który wyznacza liczbę doskonałych skojarzeń dla dowolnego grafu z tej klasy. Ten wynik można uogólnić na szerszą klasę grafów - a konkretnie na grafy planarne, czyli takie, które można narysować na płaszczyźnie tak, by żadne z ich krawędzi się nie przecinały.

Zajmiemy się takim oto zadaniem: dana jest szachownica rozmiaru i kostek domina, z których każda może przykryć dwa sąsiednie pola szachownicy. Na ile sposobów możemy przykryć całą szachownicę?

Tym razem omówimy zadanie Fiber-optic Network, które pojawiło się na zeszłorocznych zawodach ACM-ICPC Asia Mudanjiang Regional Contest.

Tym razem zadanie Candies z Bałtyckiej Olimpiady Informatycznej z 2010 roku.

Dzisiejsze zadanie pochodzi z VII obozu informatycznego ILOCAMP.

Wyobraźmy sobie sytuację, w której grupa speleologów chce wyeksplorować nieznaną jaskinię. Przy każdym rozgałęzieniu muszą podejmować decyzję, ilu z nich pójdzie każdym z nowych tuneli.

W tym kąciku omówimy zadanie Wiercenia, które pojawiło się na Potyczkach Algorytmicznych w roku 2009.

Jednym z najtrudniejszych zadań, z którym mierzyli się uczestnicy światowych finałów konkursu ACM ICPC w roku 2014, było zadanie pt. Metal Processing Plant.

W tym kąciku omówimy zadanie Filary, które pojawiło się na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym 2014. Zadanie, pomimo prostej treści i (jak się za chwilę przekonamy) całkiem prostego rozwiązania, sprawiło sporo kłopotów drużynom startującym w zawodach i ostatecznie zostało rozwiązane tylko przez jedną z nich.

W numerze 10/2010 Delty pojawił się artykuł Wojciecha Plandowskiego, w którym autor po ciężkich bojach pokazuje rozwiązanie pewnego konkretnego typu równania na słowach. Mogłoby się wydawać: udało się, sprawa skończona. Tymczasem przy okazji w artykule pojawia się definicja i kilka ważnych własności słów pierwotnych, a stąd już tylko mały krok do innej ciekawej rodziny słów, mianowicie do słów pierwszych. To dobry pretekst, by coś o nich opowiedzieć.

W tym artykule rozwiążemy problem rozkładu słowa na najmniejszą liczbę słów Lyndona (zwanych też słowami pierwszymi). Problem ten jest inspirowany zadaniem Jan z pierwszej edycji Potyczek Algorytmicznych, która odbyła się w roku 2005.

W tym kąciku omówimy zadanie Fotoradary, które pojawiło się w 2013 roku na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym.

W tym miesiącu omówimy zadanie Sequence, które pojawiło się na tegorocznej edycji Bałtyckiej Olimpiady Informatycznej.

Zadanie Skarb pojawiło się w kwalifikacjach do konkursu Google Code Jam 2013.

Tym razem zadanie Smok z Akademickich Mistrzostw Polski w Programowaniu Zespołowym 2005, które odbyły się na Uniwersytecie Jagiellońskim.

W tym kąciku dwa zadania z cyklu naszych ulubionych, tzn. na pierwszy rzut oka ciężkie do ugryzienia, ale mające ładne i krótkie rozwiązania.

W tym kąciku informatycznym – zadanie Palindromy z finału XIII Olimpiady Informatycznej.

Tym razem zajmiemy się zadaniem Routing z finałów Akademickich Mistrzostw Świata w Programowaniu Zespołowym z 2006 roku...

W tym kąciku proponuję zadanie polecane przez mojego korespondenta w Jekaterynburgu, mieście znanym również z turnieju Ural Sport Programming Championship, którego zeszłoroczną atrakcją był bezwzględny pojedynek pięciu najlepszych drużyn z Rosji z pięcioma najlepszymi drużynami z Chin. Popatrzmy na zadanie, którego nie udało się rozwiązać żadnej z nich!

W tym kąciku omówimy zadanie Różne słowa z Obozu Naukowo-Treningowego im. A. Kreczmara w 2013 roku.