Miasta

Ty razem proponuję ciekawe zadanie interaktywne prosto ze słonecznego Kazachstanu, czyli z IOI 2015. Naszym celem będzie wyznaczenie pewnych informacji na temat drzewa (dla niepoznaki jak zwykle nazwanego siecią dróg) zadając niewiele pytań o odległości między jego liśćmi.

Czytaj dalej

Rezydencja

W tym (już całkiem wakacyjnym) odcinku proponuję zadanie o ninja zakradającym się do rezydencji. Co prawda ninja został świetnie wyszkolny, lecz rezydencja jest nie tylko świetnie strzeżona, ale i złożona z nieskończenie wielu pomieszczeń. Nie będzie łatwo.

Czytaj dalej

Ewolucja

Dzisiaj obiecane w poprzednim odcinku całkiem świeże zadanie z finałów ACM ICPC 2015. Co prawda nie jest ono najtrudniejsze w całym zestawie (bo tego najtrudniejszego nie umiem), ale mimo zgrabnej treści nie jest też takie całkiem proste. A co najważniejsze, jest z algorytmów tekstowych!

Czytaj dalej

Autostrada

Zgodnie z tradycją, choć tym razem ze sporym opóźnieniem, proponuję omówienie jednego zadania z ostatniej edycji Wielkiej Przesmyckiej. Jest w nim odrobina geometrii, ale główna trudność ma charakter bardziej algorytmiczny niż implementacyjny, a zadanie jest dość konkretne nawet w wersji easy.

Czytaj dalej

Jastrzębie

Ciężko uznać za fajne zadanie, którego rozwiązanie zaczyna się od parsowania wyrażenia boolowskiego. Proponuję na chwilę o tym jednak zapomnieć i dać szansę zadaniu Fox Hawks z tegorocznego finału Facebook Hacker Cup. Mimo smutnego kawałka na samym początku można w nim znaleźć całkiem elegancki i chyba niekoniecznie standardowy pomysł.

Czytaj dalej

Lisek chytrusek

Po długiej przerwie wracam z zapasem świeżych pomysłów i na początek proponuję zadanie za 1100 punktów z Single Round Match 651. Zadanie to może wydawać się standardowym ćwiczeniem na programowanie dynamiczne, jednak szybki rzut oka na limity pozwala od razu przekonać się, że to ćwiczenie raczej nie jest standardowe, a być może nawet ma niewiele wspólnego z programowaniem dynamicznym.

Czytaj dalej

Zbiórka

Dla złapania oddechu po walce z palindromami proponuję niezbyt trudne (choć nieco podchwytliwe) zadanie z „udawanej” geometrii, które pojawiło się całkiem niedawno na zawodach ACM ICPC NWERC 2014. Udawanej, bo w 2D i z odległością taksówkarza, ale też całkiem fajne.

Czytaj dalej

Synteza wirusa

Kolej na zadanie o palindromach z ACM ICPC CERC 2014. Palindromy są fajne. W tym konkretnym dostajemy dość długi napis, który należy skonstruować zaczynając z napisu pustego za pomocą jak najkrótszego ciągu operacji. Każda operacja to doklejenie nowej litery na początku, doklejenie litery na końcu, lub doklejenie odwróconej kopii całego aktualnego napisu (na początku lub na końcu). Docelowy napis może składać się z nawet 10^5 liter, więc ewidentnie celujemy w rozwiązanie o złożoności bliskiej liniowej. Czyli fajnie.

Czytaj dalej

Fragmentacja

Dziś proponuję przyjemne (choć może niezbyt trudne) i świeże zadanie F z NEERC Northern Subregional 2014. Autor prosi nas o pokrojenie podanego ciągu na jak najmniej kawałków tak, aby przestawiając otrzymane kawałki można było posortować cały ciąg. Oczywiście interesuje nas skonstruowanie rozwiązania o liniowym czasie działania.

Czytaj dalej

Przydatne drogi

W tym roku nie znalazłem wystarczająco ciekawego zadania o torcie urodzinowym, będzie więc takie o grafie skierowanym. Zadanie pochodzi z tegorocznej edycji NEERC Southern Subregional (co wróży raczej dobrze) i, w zależności od tego, czy zna się pewien trik, czy też nie, jest bardzo trudne lub zupełnie standardowe.

Czytaj dalej