I kolokwium - zadanie 3 z 2007

Zadanie 3 [5 punktów]

Zaproponuj implementację następujących operacji na tablicy liczb naturalnych T[0..n+1], początkowo wypełnionej zerami, w taki sposób, żeby ich koszt zamortyzowany był stały.

Inc(i):: T[i]:=T[i]+1 // zawsze 0<i<n+1
BlockDec(i):: Jeśli T[i]=0 nic nie rób. W przeciwnym przypadku znajdź najbliższy indeks j taki, że T[i]≠T[j] (jeśli są dwa takie indeksy wybieramy mniejszy z nich). Dla każdego k pomiędzy i oraz j wykonaj T[k]:=T[k]–1

Hej, czy ktoś robił już to zadanie i ma pomysł jak je rozwiązać?
Próbowaliśmy na razie bezskutecznie walczyć z liniowym szukaniem końców bloków (uznaliśmy, że to wyszukiwanie psuje koszt zamortyzowany).

Wydaje mi się, że jeżeli zrobimy szukanie końców tak jak w zadaniu z palindromami - od środka rozjeżdżamy się wskaźnikami i zwiążemy z każdą wstawianą jedynką kredyt 3, to nam wystarczy na opłacenie przy zmniejszaniu.
3 = 1 na usunięcie, 1 na przeszukiwanie siebie, 1 na przeszukiwanie punktu powstałego przez odbicie lustrzane siebie względemu punktu i.

Chyba napisałem niejasno bo Filip na SO próbował to obalić
Jak zrobimy szukanie, to fizycznie odbieramy 2 zł od tych elementów z przedziału, które bedziemy zmniejszać - od krótszego przedziału, to wydaje się rozjaśniać to co napisałem wyżej. W ten sposób cały czas jest parzysta liczba złotówek

Podepne się pod ten temat:

Podaj strukturę danych umożliwiającą wykonywanie w czasie O(logn) następujących operacji na początkowo pustym zbiorze S:
insert(v,S)
deletemedian(S)
przy założeniu, że elementy zbioru S pochodzą z dowolnego zbioru liniowego uporządkowanego.

Any idea?

Mój pomysł jest taki:

EDIT: lepszy link:
https://docs.google.com/drawings/d/1UeesX4eQhJ8_7tri6K3abHYPjJbNaDpzW2cY5Ik4MpY/edit


Insert(v, S)
Patrzymy czy v jest większy czy mniejszy od mediany
większy ląduje w prawym kopcu, mniejszy lub równy w lewym
I robimy poprawienie struktury. Jeśli size(L) + 1 < size(P) lub odwrotnie size(L) > size(P) + 1 to robimy jakby rotację w lewo lub prawo odpowiednio.
Rotacja polega na przerzucenia korzenia do odpowiedniego kopca i wyciągnięcia z wierzchołka drugiego nowej mediany.

Delete polega na wyciągnięciu mediany i wzięciu elementu z odpowiedniego kopca tak, żeby zachować warunek |size(P) - size(L)| <= 1 - taki niezmiennik chcemy utrzymać i insert zapisany jak wyżej zdaje się go zachowywać.

Jak ktoś widzi błąd, to dajcie znać!

Mediana jest zdefiniowana jako: dla nieparzystego n to (n+1)/2 element, dla parzystego n, to średnia arytmetyczna, obu środkowych elementów. Tak więc trochę trzeba zmodyfikować tę strukturę, ale ogólnie pomysł mi się podoba

Racja! Ale wtedy jak usunąć medianę? Przecież ona fizycznie w zbiorze nie wystepuje... może jest jakieś założenie co do tego czym jest mediana?

Zgadzam się z Adrianem

Filip, spadłem z krzesła =)

Przez Ciebie będzie mi się dzisiaj KD śnić...

Raczej zakładałbym, że medianą będzie element najbliższy medianie mniejszy równy od mediany. Wtedy ma sens deletemedian

Hej, ma ktoś może dobrze zapisany algorytm sortowania mergesortem ze scalaniem w miejscu? Ten z podziałem na bloki itd.

Chciałem się dowiedzieć co się dzieje jak już mamy posortowane blokowo i mamy ten bufor na początku. Co dalej robimy - jak "wsortowujemy" bloki teraz?

http://www.mimuw.edu.pl/~walen/zajecia.php?przedmiot=aisd2010
aisd02