22.09.2009

Wtorek 22 września

Zaawansowany: Zadania z ONTAK-ów '08 i '09

Prowadził: Paweł Lipski

Na Mokipie omówiłem zadania z Obozów Naukowo-Treningowych im. Antoniego Kreczmara z lat 2008 i 2009.

Wszystkie te zadania (oprócz czasowo niedostępnej Macierzy) można rozwiązać w serwisie main.edu.pl, wchodząc na podstrony ONTAK 2008 i ONTAK 2009. Treść zadania Macierz i potrzebne biblioteki można znaleźć tutaj.

ONTAK 2009: Trójkąty

Pokazałem proste rozwiązanie działające w czasie $O(n + p \log L\log\log L)$, gdzie $L$ jest największą liczbą w danym ciągu $c$.

ONTAK 2009: Macierz

Najpierw wymieniłem kilka heurystyk, które nie zapewniają więcej niż 50% punktów. Następnie opowiedziałem rozwiązanie oparte na technice "dziel i zwyciężaj", które znajduje minimum lokalne za pomocą co najwyżej $2n+6\lceil\log n\rceil$ zapytań.

ONTAK 2008: Haszowanie

Rozwiązanie wzorcowe korzystało z triku (tzw. sideł na cyklu), który pozwalał osiągnąć złożoność $O(\sqrt{n})$ przy zużyciu stałej pamięci.

ONTAK 2009: Mechagodzilla

Zastosowałem odpowiednio wzbogacone drzewa przedziałowe, dzięki czemu program działał w czasie $O(nm + zn\log m)$.