Delta mi!

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

Dzisiejsze zadanie pochodzi z VII obozu informatycznego ILOCAMP.

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

W tym miesiącu omówimy zadanie Kuglarz z pierwszej rundy Potyczek Algorytmicznych 2014. Tytułowy kuglarz zaprasza przechodniów do następującej gry...

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 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.

W tym kąciku omówimy dwa zadania z Potyczek Algorytmicznych 2012. Pomimo krótkich rozwiązań, zadania te wymagały od zawodników niemałej dozy pomysłowości.

Tym razem w kąciku zadanie Świetliki, z którym mierzyli się finaliści Potyczek Algorytmicznych 2013.

Tym razem omówimy zadanie o drogach stanowych (State Roads) z pierwszej rundy zawodów Yandex.Algorithm 2013. Zadanie to można sformułować w języku teorii grafów, a do tego w ujęciu dynamicznym...

W tym kąciku zmierzymy się z zadaniem Karty z Potyczek Algorytmicznych 2013. Oryginalne sformułowanie zadania dotyczyło kart perforowanych, my jednak przedstawimy je nieco inaczej, przy okazji wprowadzając niejawnie kilka nieznaczących uproszczeń.

W tym kąciku zajmiemy się zadaniem Dwóch generałów, które pochodzi z Uniwersyteckich Zawodów Informatycznych organizowanych przez Uniwersytet Jagielloński, a konkretnie z konkursu z października 2009 roku.

W tym kąciku zajmiemy się zadaniem Delayed search, które pojawiło się w 2004 r. w konkursie Internet Problem Solving Contest, organizowanym co roku przez Słowaków. Zadanie jest wariacją na temat znanej zabawy „zgadnij, o jakiej liczbie myślę”...

W tym kąciku omówimy Dwa torty – kolejne zadanie z finałowej rundy Potyczek Algorytmicznych 2012.

Jednym z klasycznych problemów algorytmicznych jest tzw. problem plecakowy...

Tym razem zajmiemy się zadaniem z finałów Akademickich Mistrzostw Świata w Programowaniu Zespołowym 2012, które odbyły się w Warszawie. Zadanie zatytułowane Infiltration zostało rozwiązane przez 31 spośród 112 drużyn i było średnim pod względem trudności zadaniem na tych zawodach.

W tym kąciku zajmiemy się zadaniem Quadrilaterals z obozu w Petrozawodsku w 2006 roku. Na płaszczyźnie dane jest  punktów w położeniu ogólnym (tzn. żadna trójka punktów nie leży na jednej prostej). Należy wyznaczyć liczbę czworokątów wypukłych, których wierzchołki znajdują się wśród podanych punktów.

Zadanie Odśnieżanie z zeszłorocznego Obozu Naukowo-Treningowego im. A. Kreczmara można sformułować w języku teorii grafów następująco. W nieskierowanym, ważonym, spójnym grafie  wyróżniono cztery wierzchołki. Należy usunąć część krawędzi z grafu tak, żeby nadal istniały ścieżki pomiędzy każdą parą wyróżnionych wierzchołków i żeby suma wag krawędzi, które pozostały w grafie, była jak najmniejsza.

W niedawno wydanej książce W poszukiwaniu wyzwań – zbiorze zadań z konkursów programistycznych – Filip Wolski opisał rozwiązanie zadania Dwa przyjęcia z finału XII Olimpiady Informatycznej. W zadaniu tym występuje  osób, z których niektóre się znają (wiemy które). Chcemy podzielić ten zbiór na dwa rozłączne podzbiory (przyjęcia) w taki sposób, aby zmaksymalizować liczbę osób, które mają parzystą liczbę znajomych na przyjęciu, na którym przebywają...

W tej edycji kącika omówimy zadanie pt. Podlewanie ogórków (naprawdę!) z rundy 2A konkursu TopCoder Open 2012.

Tym razem omówimy zadanie z pogranicza informatyki i muzykologii, które pojawiło się na Bałtyckiej Olimpiadzie Informatycznej w bieżącym roku.

Tym razem w kąciku lekko zmodyfikowana wersja zadania Listonosz z konkursu Wielka Przesmycka 2004.

W tej edycji kącika znowu cofniemy się w czasie do 2005 roku, do pierwszej edycji konkursu Potyczki Algorytmiczne, i omówimy zadanie z finału próbnego tego konkursu pt. Drogi (bardzo podobne zadanie pojawiło się zresztą w jeszcze bardziej zamierzchłej przeszłości, na Międzynarodowej Olimpiadzie Informatycznej w 1996 roku).

W tym miesiącu omówimy zadanie, które pojawiło się w pierwszej edycji konkursu Potyczki Algorytmiczne, w roku 2005.

Tym razem omówimy zadanie Robot sortujący (ang. Robotic Sort) z Mistrzostw Europy Środkowej w Programowaniu Zespołowym 2007 (CERC 2007).

Tym razem zajmiemy się zadaniem Nurkowanie z Obozu Naukowo-Treningowego im. Antoniego Kreczmara w 2007 roku.

W tym miesiącu opiszemy zadanie Monety, które pojawiło się na Potyczkach Algorytmicznych w roku 2010.

W tym kąciku rozwiążemy zadanie Prostokąty (Rectangles), które pojawiło się w 2007 roku na konkursie organizowanym przez MIT w serwisie spoj.pl.

W tym miesiącu omówimy zadanie, które rozwiązywali uczestnicy Obozu Naukowo-Treningowego im. A. Kreczmara w 2009 r.

Zadanie omawiane w tym kąciku pochodzi z obozu treningowego drużyn rosyjskich z 2008 roku (autor zadania: Andrew Stankevich).

W tym kąciku omówimy pierwsze zadanie z finału konkursu Google Code Jam 2010.

O pewnym zadaniu z zeszłorocznego Obozu Naukowo-Treningowego im. A. Kreczmara.

Napisanie programu, który generuje rysunek fraktala, idealnie nadaje się na zadanie dla początkującego programisty. Proste reguły prowadzące do powstania skomplikowanych wzorów powodują, że przy stosunkowo niewielkim wysiłku programistycznym można osiągnąć całkiem ambitne efekty wizualne. Ponadto samopodobieństwo fraktali pozwala ćwiczyć jedną z podstawowych koncepcji programistycznych – rekurencję.

Jednym z zadań, które zostały postawione przed uczestnikami akademickich drużynowych zawodów programistycznych ACM ICPC Dhaka Regional Contest 2010, było zadanie o nieco mylącym tytule Network Flow (Przepływ w sieci).

W tym numerze Delty dużo uwagi poświęcono ciągowi EKG, który zarówno z matematycznego, jak i z informatycznego punktu widzenia przejawia wiele interesujących własności. W kąciku kontynuujemy temat ciekawych ciągów liczbowych. Zajmiemy się zadaniem Ciąg z finału II Olimpiady Informatycznej Gimnazjalistów, w którym poproszono uczestników o wyznaczenie -tego wyrazu pewnego ciągu, zwyczajowo wiązanego z nazwiskiem matematyka Solomona Golomba.

Tym razem przyjrzymy się zadaniu Training z Międzynarodowej Olimpiady Informatycznej 2007.

W tym kąciku spróbujemy rozwiązać zadanie Electric needs pochodzące z drużynowych zawodów studenckich z serii ACM ICPC, a konkretnie z mistrzostw Ameryki Łacińskiej 2010.

W tym kąciku zajmiemy się rozwiązaniem zadania pochodzącego z jednej z finałowych rund konkursu TopCoder Open 2010, o nazwie Shrooks on the Board.

Tematem kolejnej edycji Kącika jest zadanie pochodzące z zeszłorocznej Międzynarodowej Olimpiady Informatycznej o nazwie Oszczędny kod (ang. Saveit).

W tym odcinku zajmiemy się zadaniem, które zamiast na zawodach, pojawiło się na... kolokwium (z Algorytmów i Struktur Danych). Stanowiłoby ono bardzo ładne zadanie na zawodach.

Tym razem dwa zadania „z haczykiem”.