Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 1 ] 
[Runda 21] - Bloki 
Autor Wiadomość
Gwiazda 3Gwiazda 3

Dołączył(a): 17 lis 2009, o 02:37
Posty: 141
Post [Runda 21] - Bloki
W zadaniu mamy rozstawić Pawła (P) i Władka (W) tak, by odległość między nimi była jak największa. Na początku możemy zauważyć, że jeśli mamy tylko 1 blok, należy ich rozstawić na pierwszym i ostatnim piętrze, zaś w przypadku większej liczby bloków, obaj będą umieszczeni w różnych blokach na ostatnich piętrach.

Rozważmy zmodyfikowany problem, w którym bloki rozmieszczone są na prostej, z założeniem, że W możemy umieścić w bloku o numerze > od tego, w którym został umieszczony P. Umieszczamy P w 1 bloku i szukamy bloku dla W tak by odległość między nimi była maksymalna. Załóżmy, że umieściliśmy W w bloku k.

Obserwacja :
Umieszczając P w dowolnym bloku o numerze < k, maksymalną odległość między nimi uzyskamy po umieszczeniu W w bloku k.

Uzasadnienie obserwacji jak i rozw. zmodyfikowanego problemu pozostawiam jako ćwiczenie.

Wróćmy teraz do rozmieszczenia bloków na okręgu. W tym problemie nie działa obserwacja poczyniona powyżej. Mój pomysł polega na podzieleniu okręgu na proste odcinki długości n/2 o początku w kolejnych blokach od 1, .., n (zauważmy, że na takim odcinku obserwacja już działa). W możemy umieszczać w bloku o numerze z przedziału [(i+1)%n, (i+n/2)%n], gdzie i to numer bloku w którym umieściliśmy P.

Rozpatrujemy teraz pierwszy odcinek umieszczając P w 1 bloku i szukając bloku k, w którym umieścimy W w czasie O(n). Mamy policzoną maksymalną odległość na odcinku 1,.., n/2 przy założeniu, że P jest w bloku 1. Teraz chcemy znaleźć maksymalną odległość na odcinku 2,.., n/2+1 przy założeniu, że P jest w bloku 2. Zauważmy, że W nie będzie w bloku j, takim że 2 <= j <= n/2, j != k ponieważ w takiej sytuacji odległość między j i 2 byłaby maksymalną odległością (gdy P jest w bloku 2) na odcinku 1,..,n/2 a to jest sprzeczne z obserwacją (umieszczając P w bloku o numerze < k najlepszą odległość między nimi uzyskamy po umieszczeniu W w bloku k != j). Zatem możemy ograniczyć się do umieszczenia W w bloku k lub n/2+1, a w ten sposób policzymy to co chcemy w czasie O(1). Zauważmy, że rozpatrując takie odcinki dla każdego początku 1,..,n otrzymamy maksymalną odległość na całym okręgu (gdyby maksymalna odległość miała być realizowana np. przez bloki 1 i n/2+5, to zostanie ona znaleziona przy wyznaczaniu najlepszej odległości na odcinku o początku n/2+5). Ponieważ każdy odcinek (poza pierwszym) rozpatrujemy w czasie O(1), a takich odcinków jest n, cały algorytm działa w czasie O(n).

Należy uwzględnić jeszcze jedną sytuację, którą przedstawię na przykładzie. Dla pierwszego odcinka znaleźliśmy blok k, w którym będzie W. Okazało się, że był on najlepszy dla każdego umieszczenia P w 1, 2, .., k-1. W tej sytuacji nie wiemy gdzie umieścić W, zakładając, że umieścimy P w bloku k.

By rozwiązać ten problem przy rozpatrywaniu odcinka o początku i (aktualna pozycja P), w sytuacji gdy i+n/2 jest gorszy niż aktualne k, należy wrzucić blok i+n/2 do tablicy kandydatów na sam koniec, a następnie przesuwać go do początku dopóki bloki w tej tablicy dają mniejszą (lub równą) odległość dla aktualnej pozycji P. Następnie z tablicy usuwamy wszystkie bloki, które znajdą się za i+n/2. Gdy zajdzie sytuacja, w której i = k, po prostu wybieramy pierwszego kandydata, którego pozycja jest > i jako nowe k.

Edit: Proszę o wszelkie uwagi na PW, będę poprawiał.


9 mar 2010, o 18:37
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 1 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL