CERC 2010: Szkice rozwiązań
28.11.2010
E: Enter The DragonTreść (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 dodatkoweZamiast 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