Droga długości 6

Po kolejnej długiej przerwie proponuję zadanie, które pojawiło się drugiego dnia na tegorocznym obozie w Petrozavodsku w zestawie autorstwa Xiaoxu Guo. W zadaniu dostajemy nieskierowanym graf i jesteśmy proszeni o policzenie dróg długości 6, które nie są cyklami prostymi.

Czytaj dalej

Reklama

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

Przystanek autobusowy

Jako pierwsze w tym roku proponuję zadanie o marznięciu na przystanku w oczekiwaniu na autobus. Interesuje nas policzenie wartości oczekiwanej minimum z n niezależnych zmiennych losowych, z których każda ma rozkład jednostajny ciągły.

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

Trening z drzwiami I

Na rozpoczęcie sezonu proponuję zadanie o nawiasach z południowych eliminacji do NEERC 2015. Rozważamy nawiasy umieszczone na prostokątnej planszy. Interesuje nas zliczenie jej wszystkich (też prostokątnych) fragmentów, w których każdy wiersz jest prawidłowym nawiasowaniem.

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