Na wypadek awarii

W ramach wakacyjnego relaksu proponuję zadanie z zawodów Central European Programming Contest organizowanych osiem lat temu przez Instytut Informatyki Uniwersytetu Wrocławskiego. Zadanie jest oczywiście z geometrii, ale tym razem w tylko dwóch wymiarach: dostajemy n \leq 10^5 punktów na płaszczyźnie, dla każdego z nich chcemy znaleźć najbliższego sąsiada. Odległość jest standardowa, to znaczy euklidesowa.

Czytaj dalej

Zamiana

Na rozgrzewkę przed zbliżającymi się finałami ACM ICPC proponuję przyjemne zadanie o „zepsutej” procedurze heapify z Baltic Olympiad in Informatics 2016. Zadania nie jest kosmicznie trudne, więc skomplikujemy sobie życie próbując skonstruować rozwiązanie, które działa w czasie liniowym.

Czytaj dalej

Karmienie śledziami

Co prawda już po świętach, ale jako już ostatnie w tym roku proponuję zadanie o śledziach z zawodów CTU Open 2015. Interesuje nas w nim policzenie sposobów, na jakie można przedstawić podaną liczbę n jako a+b+c tak, żeby a,b,c\geq L oraz żadna z liczb a,b,c nie zawierała cyfry 3 w swoim zapisie dziesiętnym.

Czytaj dalej

Exodus superbohaterów

Na kolejny nieciekawy grudniowy wieczór proponuję ciekawe zadanie o superbohaterach z ostatnich Mistrzostw Wielkopolski w Programowaniu Zespołowym, w którym jesteśmy proszeni o pokolorowanie wierzchołków dość specyficznie skonstruowanego grafu. Ponieważ całe zadanie jest o superbohaterach, kolorowanie także nie będzie takie całkiem zwyczajne!

Czytaj dalej

Lepsza produktywność

Tym razem krótko o zadaniu z NWERC 2015, w którym interesuje nas podzielenie podanego zbioru przedziałów na ustaloną liczbę niepustych grup tak, aby zmaksymalizować sumę długości przecięć przedziałów przydzielonych do tej samej grupy. Spróbujemy rozwiązać je nieco szybciej niż autorzy!

Czytaj dalej

Miejska geografia

Na ponury grudniowy wieczór proponuję zadanie z Ural Sport Programming Championship 2015, którego treść można przedstawić w jednym zdaniu: chcemy znaleźć drzewo spinające o jak najmniejszej różnicy kosztu między najdroższą na najtańszą krawędzią. Brzmi fajnie, prawda?

Czytaj dalej

Gra planszowa

Urodziny kojarzą się zwykle z prezentami, a prezenty (i ich owijanie) z otoczką wypukła. Wiadomo. W związku z tym dzisiaj proponuję zadanie o najbardziej odległych różnokolorowych punktach, które pojawiło się kilka dni temu na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym.

Czytaj dalej

Trudne związki

W ramach rozgrzewki przed sezonem proponuję krótkie i przyjemne zadanie o rekonstrukcji grafu na podstawie stopni jego wierzchołków. Żeby nie było całkiem standardowo, pozwalamy na istnienie wielokrotnych krawędzi (które nie są pętlami), ale za to graf koniecznie musi być spójny.

Czytaj dalej

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