![]() |
||||||||||||||||||||||||||||
Piotr Chrząstowski (treść, opracowanie) Marcin Sawicki (program wzorcowy) LollobrygidaW fabryce poduszkowców do budowy torów testowych używa się standardowych bloków o różnych wysokościach, ustawianych jeden za drugim. W idealnie zbudowanym torze, zwanym lollobrygidą, nigdy nie występują obok siebie dwa bloki jednakowej wysokości, nigdy też trzy kolejne bloki nie mają kolejno coraz większych, albo coraz mniejszych wysokości. Mówiąc bardziej formalnie, niech h_1,... ,h_n oznacza ciąg wysokości kolejnych bloków należących do toru. Jeśli dla każdego
PrzykładZ zestawu 5 bloków o wysokościach 3, 3, 3, 5, 2 nie da się zbudować lollobrygidy, gdyż albo musiałyby stać w niej obok siebie dwa bloki wysokości 3, albo musi się w niej pojawić jedna z niedozwolonych sekwencji 2, 3, 5 lub 5, 3, 2. A oto przykład lollobrygidy, poprawnie zbudowanej z innego zestawu bloków: 3, 2, 5, 2, 3, 1. Z tego zestawu można też zbudować inne lollobrygidy. ZadanieNapisz program, który wczyta z pliku tekstowego LOL.IN liczbę zestawów danych i dla każdego zestawu:
Wejście W pierwszym wierszu pliku tekstowego LOL.IN znajduje się liczba całkowita d, W pierwszym wierszu każdego zestawu danych znajduje się liczba całkowita n, W kolejnych n wierszach znajdują się wysokości bloków. Każdy z tych wierszy zawiera jedną liczbę całkowitą h równą wysokości odpowiedniego bloku, Kolejne zestawy danych następują bezpośrednio po sobie. WyjściePlik tekstowy LOL.OUT powinien zawierać dokładnie d wierszy, po jednym dla każdego zestawu danych. W i-tym wierszu pliku LOL.OUT powinien być zapisany jeden wyraz:
PrzykładDla pliku wejściowego LOL.IN2 5 3 3 3 5 2 6 3 3 1 5 2 2poprawną odpowiedzią jest plik wyjściowy LOL.OUT NIE TAK RozwiązanieZadanie o lollobrygidzie w dużej części sprowadzało się do znanego i opisywanego w literaturze zadania o wyborze lidera. Zadanie to formułuje się następująco: Stwierdzić, czy w ciągu Okazuje się bowiem, że zachodzi następujące twierdzenie: Twierdzenie. Z elementów
Dowód. Najpierw pokażemy, że jeżeli istnieje lider nie spełniający warunku (2), to lollobrygidy ułożyć się nie da, a potem, że jeśli ciąg spełnia którykolwiek z warunków (1) lub (2), to lollobrygidę ułożyć się da. Załóżmy więc, że istnieje lider nie spełniający warunku (2). Jeżeli n jest parzyste, to lider występuje co najmniej Jeżeli n jest nieparzyste i lider występuje co najmniej Pokazaliśmy więc pierwszą część twierdzenia. Pozostaje wykazać, że jeśli lidera nie ma lub jeśli jest lider, ale spełniający warunek (2), to lollobrygidę da się ułożyć z podanych wartości. Proste jest pokazanie, że jeśli lider spełnia warunek (2), to lollobrygidę daje się ułożyć. Wystarczy na wszystkich nieparzystych pozycjach ulokować lidera, a pozostałe elementy umieścić dowolnie na parzystych pozycjach. Warunek lollobrygidy w oczywisty sposób jest spełniony. Zostało zatem do wykazania, że jeśli lidera nie ma, to lollobrygidę zawsze się da ułożyć. Dowód będzie indukcyjny ze względu na długość ciągu n. Wzmocnimy najpierw nieco tezę - jest to częsty chwyt przy dowodach indukcyjnych; korzystamy przecież wtedy z mocniejszego założenia indukcyjnego. Pokażemy zatem, że jeśli lidera w ciągu Bazę indukcji pokażemy dla wartości n=2. To nie szkodzi, że w sformułowaniu zadania Załóżmy teraz, że teza zachodzi dla każdego ciągu Najpierw n nieparzyste. Niech m będzie modą ciągu Taki ciąg po usunięciu jednego elementu będącego modą spełnia założenie indukcyjne: jest krótszy od n i nie zawiera lidera, zatem można z niego utworzyć lollobrygidę Jeśli n jest parzyste, to mamy trochę inną sytuację, bo usunięcie mody może doprowadzić nas do sytuacji, w której pojawi się lider w ciągu n-1-elementowym i nie będzie można skorzystać z założenia indukcyjnego. Poradzimy sobie z tym przypadkiem zauważając, że tak może być jedynie wtedy, gdy w ciągu występują tylko dwie wartości i każda z nich jest modą. Wtedy nie musimy stosować indukcji - wystarczy ustawić jedne wartości na nieparzystych, a drugie na parzystych miejscach i mamy lollobrygidę. W każdym innym przypadku po usunięciu z ciągu, w którym nie było lidera, jednego elementu o wartości mody, lidera nadal nie będzie. Możemy wtedy stosować założenie indukcyjne. Załóżmy więc, że ciąg Jeżeli teraz m>b_1 lub Wyczerpaliśmy tym samym wszystkie przypadki, za każdym razem pokazując, że lollobrygida jest możliwa do ułożenia. Twierdzenie zostało tym samym udowodnione. Uff! Mamy już w ręku ważny wynik, który ułatwi rozwiązanie zadania w efektywny sposób. Pozostaje więc sprawdzić, czy lider istnieje i jeżeli nie, to odpowiedź jest TAK, a jeśli lider istnieje, to wystarczy upewnić się, czy nie spełnia warunku (2). Jeżeli spełnia, to odpowiedź jest TAK, a jeśli nie spełnia, to odpowiedź jest NIE. Omówmy tu 4 różne algorytmy stwierdzania istnienia lidera. Pierwszy algorytm, być może najprostszy do wymyślenia, polega na posortowaniu danych i znalezieniu w posortowanym ciągu najdłuższej sekwencji tych samych elementów. Koszt dobrego sortowania jest proporcjonalny do Drugi algorytm bazuje na spostrzeżeniu, że jeśli w ciągu jest lider, to jest on równy medianie ciągu, czyli elementowi, który w posortowanym ciągu wystąpiłby pośrodku (dla n parzystego jako medianę definiuje się dowolny z dwóch elementów środkowych). Algorytm zatem rozbija się na dwie części: wyznaczenie mediany i sprawdzenie, czy mediana jest liderem. Ta druga część jest bardzo prosta. Wyznaczenie mediany jest bardziej kłopotliwe, o ile nie chcemy korzystać z sortowania. Medianę można wyznaczyć w czasie pesymistycznym proporcjonalnym do n, ale nie jest to proste. Zadanie to realizuje na przykład algorytm Bluma, Floyda, Pratta, Rivesta, Tarjana, zwany algorytmem piątek lub algorytmem pięciu - każda z nazw jest uzasadniona. Algorytm ten opisany jest np. w książce [10]. Problem polega na tym, że koszt tego algorytmu, choć liniowy, obarczony jest dużą stałą i dla potrzeb naszego zadania algorytm ten raczej się nie nadaje. Przy podanych ograniczeniach na rozmiar danych uzyskanie za pomocą tego algorytmu lepszego czasowo rozwiązania, niż przez sortowanie, wydaje się trudne, a być może jest wręcz niemożliwe. Pamiętajmy bowiem, że choć teoretycznie złożoność jednego algorytmu może być lepsza od złożoności drugiego, to wcale nie znaczy, że zawsze należy stosować ten pierwszy. Na przykład dla krótkich ciągów danych (rzędu kilku-kilkunastu) nie należy sortować quicksortem, tylko którymś z algorytmów o złożoności kwadratowej, choćby przez proste wstawianie. Z praktycznego punktu widzenia lepiej byłoby tu zastosować opisany również w [10] algorytm Hoare'a wyznaczania mediany. Jego idea jest podobna do pomysłu sortowania quicksortem. Losuje się bowiem jedną z wartości ciągu, a następnie rozrzuca pozostałe wartości na 3 grupy: elementów mniejszych, równych i większych od tej wartości, po czym szuka się elementu o odpowiednim numerze w jednej z tych grup, tą samą zresztą metodą. Ten algorytm ma kwadratową złożoność pesymistyczną (gdy zawsze będziemy mieli pecha i wybierali element skrajny jako wartość, względem której rozrzucamy), ale średnio działa w czasie liniowym. W praktyce doskonale nadaje się do znajdowania mediany i jest dość prosty do zakodowania - własność bardzo ważna w trakcie zawodów. Trzeci algorytm, trochę niepewny, bo nie dający dobrych rezultatów ze stuprocentową pewnością, to algorytm probabilistyczny polegający po prostu na kilkukrotnym wylosowaniu dowolnej wartości i sprawdzeniu, czy jest ona liderem. Zauważmy, że jeśli lider istnieje, to z prawdopodobieństwem większym niż Czwarty algorytm, wzorcowy, i bardzo elegancki, którego poprawność jest wysoce nieoczywista. Algorytm ten opisany jest w książce [23]. Ze względu na prostotę algorytmu podamy tutaj jego pełny kod pascalowy.
Uwaga: aby użyć tego algorytmu do rozwiązania naszego zadania, w drugiej pętli należy dodać fragment sprawdzający warunek (2) z udowodnionego twierdzenia. Fragment ten pominęliśmy, aby nie popsuć przejrzystości tekstu. Nie od razu widać, dlaczego ten algorytm miałby dawać poprawne odpowiedzi. Najlepiej się o tym przekonać próbując skonstruować kontrprzykład. Po kilku próbach okaże się to niemożliwe. Pełny dowód poprawności algorytmu jednak nie jest banalny. Przy okazji warto zauważyć, że o ile poprzednie algorytmy potrzebowały tablicy do zapamiętania wszystkich wartości ciągu, to tutaj możemy z tablicy zrezygnować i wczytywać na bieżąco wartości z pliku. Dwukrotne wczytanie wystarcza, żeby stwierdzić istnienie lidera. Algorytm ten ma zatem koszt czasowy liniowy, a pamięciowy stały. Pozostaje jeszcze wyjaśnić, dlaczego tor o podanych własnościach nazwaliśmy lollobrygidą. Narciarze zapewne wiedzą, że taką nazwę nosi jedna z bardzo muldziastych tras narciarskich w Szczyrku. Dlaczego jednak trasa ta została nazwana nazwiskiem słynnej włoskiej aktorki, pozostawmy dociekliwości czytelników. TestyTesty i czasy odcięcia zostały tak dobrane, aby możliwie jak najdokładniej oddzielić algorytmy liniowe od algorytmów o czasie działania rzędu Każdy test składa się z 30 przypadków. Pierwsze 4 testy, to testy poprawnościowe, zawierające same proste przypadki ( Oto opisy poszczególnych testów: ![]() W testach wydajnościowych występują przemieszane wszystkie 4 powyższe przypadki parzystości i istnienia, lub nie, lidera. Czasy odcięcia były dobrane tak, aby więcej niż dwukrotnie przewyższały czas działania wzorcowego rozwiązania, ale dla dużych testów powodowały odcięcie przy korzystaniu z procedur sortujących. Małe testy doczepione zostały do dużych aby wyeliminować algorytmy zgadujące odpowiedzi, bowiem jedynie rozwiązanie kompletu 30 przypadków zaliczało test. |