CERC 2010: Szkice rozwiązań

28.11.2010

E: Enter The Dragon

Treść (pdf) | wyślij rozwiązanie.

W tym zadaniu dla każdego dnia i z opadem (nad jeziorem oznaczanym przez ti należy znaleźć dzień bez opadu j < i, a następnie nakazać smokowi wypicie wody z jeziora ti w dniu j. Główne pytanie, nad którym należy się zastanowić, to jaki dzień j wybrać, jeśli mamy więcej niż jeden do wyboru. Pierwszą przymiarką do rozwiązania jest zachłanny wybór możliwie najmniejszego, jeszcze nie wykorzystanego dnia j. Jednak takie podejście jest nieprawidłowe, jak pokazuje przykład ciągu 0 0 1 0 1 0 1 2. W tym przypadku druga jedynka musi zostać przypisana do zera występującego po pierwszej jedynce. W lepszym (i poprawnym) podejściu wybieramy minimalne możliwe j, ale występujące po poprzednim wystąpieniu ti.

Aby zaimplementować to podejście wymagana jest struktura umożliwiająca dwa typy operacji: wstawianie liczby i znajdowanie następnika. Wystarczająca jest tu struktura set z biblioteki STL, dzięki której możliwy jest do osiągnięcia czas O(n log n).

Informacje dodatkowe

Zamiast struktury set można wykorzystać implementację union-find opartą na zbiorach rozłącznych, uzyskując czas O(n log* n). Taka implementacja jest niestety tylko nieznacznie szybsza od wzorcowej i nie została wykorzystana przez żadną drużynę rozwiązującą to zadanie.

Zadanie to jest prostym wariantem tzw. problemu buforowania pakietów. W takim problemie mamy m wejściowych kolejek, do których może nadchodzić dowolna liczba pakietów i jedno wyjście. Pakiety niemieszczące się w buforach są tracone. Pytanie, czy dla buforów zdolnych pomieścić po jednym pakiecie jest możliwe bezstratne obsłużenie danej sekwencji, jest zakamuflowane w historyjce o smoku i jeziorach.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com