[Algorytmy] Znajdź liczbę podciągów ściśle rosnących

[matinf]

Dany jest ciąg liczb \(\displaystyle{ a_1, ..., a_n}\)
Znajdź liczbę podciągów ściśle rosnących (niekoniecznie spójnych).

Proponuję: dynamik + słownik:
W AVL kluczem jest wartość elementu, węzły przechowują dodatkowo ilość podciągów ściśle rosnących kończących się na tym elemencie (klucz).

Gdy chcę policzyć ile podciągów kończy się na danym elemencie \(\displaystyle{ a}\), to:
\(\displaystyle{ x =}\) węzeł w drzewie, taki że jego klucz jest największym mniejszym elementem
niż a.
Więc do wyniku doliczam \(\displaystyle{ 1 + x.\underline{ilosc}}\) oraz wstawiam do do drzewa. To jest \(\displaystyle{ O(n\log(n))}\). Czy to jest poprawne ? Czy da się \(\displaystyle{ O(n)}\) ?

[Afish]

Nie zadziała już dla ciągu \(\displaystyle{ 2,4,5}\). Dla dwójki wyjdzie Ci jeden ciąg, dla czwórki wyjdą Ci dwa ciągi (czwórka i jeden ciąg od dwójki), a dla piątki wyjdą Ci trzy ciągi (piątka i dwa od czwórki), co oznacza zgubienie podciągu \(\displaystyle{ 2,5}\).
Użycie wartości elementu jako klucza w drzewie jest słabe, bo nie obsłużysz powtarzających się wartości w ciągu.

[matinf]

Dzięki, to mnie naprowadziło na poprawkę.
powiedzmy, że mamy prawidłowo policzone dla \(\displaystyle{ [1....k]}\) i rozważamy \(\displaystyle{ k+1}\) liczbę.
To na czym nam zależy, to na sprawdzeniu o ile zwiększy się liczba ciągów ściśle rosnących.

Mamy policzone, tzn że dla każdej liczby w ciągu długości \(\displaystyle{ 1...k}\) wiemy ile ciągów rosnących kończy się na niej. Co teraz zmienia wprowadzenie liczby \(\displaystyle{ k}\)-tej ? Każdy krótszy ciąg, może uda się wydłużyć ? Jak to sprawdzić ?
Utrzymujemy w drzewie AVL (każdy węzeł):
(liczba, ile ciągów się na niej kończy, suma wartości drugiej w tej krotce z całego poddrzewa)
Wówczas zapytamy: ile dotychczas mamy ciągów spośród liczb z przedziału \(\displaystyle{ 1...k}\) kończących się na liczbie mniejszej niż \(\displaystyle{ (k+1)}\)-sza. Następnie wstawiamy do drzewa i gotowe.

Odpowiedź jest w korzeniu, jako ta suma.

[Afish]

Napisałeś to tak nieczytelnie, że nie jestem przekonany, iż rozumiem algorytm, ale mam wrażenie, że nie zadziała. Weź ciąg \(\displaystyle{ 2,2,2}\) i rozpisz krok po kroku.

[matinf]

Ok,
Bierzemy \(\displaystyle{ 2}\). W drzewie nie ma żadnej liczby, więc wychodzi nam \(\displaystyle{ 0 + 1}\) (bo sama dwójka). Dodajemy do drzewa trójkę \(\displaystyle{ (2, 1, 1)}\)

Bierzemy kolejną dwójkę. Teraz sumujemy po trzecim elemencie krotki, wszystkie te, których pierwsza krotka (która jest kluczem) jest mniejsza niż \(\displaystyle{ 2}\). Ponieważ jest zero takich, to mamy \(\displaystyle{ 0 + 1}\). Do drzewa nie dodajemy, ale akutalizujemy \(\displaystyle{ (2, 2, 2)}\). (aktualizujemy, a nie dodajemy bo dwójka już w drzewie jest).

Teraz dalej to samo dla \(\displaystyle{ 3}\)-ciej dwójki. Do drzewa dodajemy \(\displaystyle{ (3, 3, 3)}\).

Czyli odpowiedź do \(\displaystyle{ 3}\).

[Afish]

Okej, tylko po co drzewo w takim razie? Być może ciągle nie rozumiem, ale moim zdaniem tylko komplikuje ono rozwiązanie, a nie poprawia złożoności (która jest kwadratowa?).
Nie prościej coś takiego:
\(\displaystyle{ f(i) = 1 + \sum_{j=1, a_j < a_i}^{i-1}f(j) \\
R = \sum_{i=1}^{n} f(i)}\)
gdzie \(\displaystyle{ R}\) to rozwiązanie, a \(\displaystyle{ f(i)}\) oznacza liczbę ciągów rosnących zawierających i-ty element?

[matinf]

Moja złożoność nie jest kwadratowa. Drzewo jest po to, żeby przyspieszyć liczenie, zaś Twój wzór trzeba liczyć w czasie kwadratowym.

[Afish]

Teraz sumujemy po trzecim elemencie krotki, wszystkie te, których pierwsza krotka (która jest kluczem) jest mniejsza niż \(\displaystyle{ 2}\)

Jak dla mnie to ukwadratawia algorytm. Niemniej ciągle jest on dla mnie nieczytelny, więc mogę go źle rozumieć. Jeżeli chciałbyś jeszcze coś ze mną skonsultować, to zapisz algorytm precyzyjnie w postaci pseudokodu (lub w jakimś cywilizowanym języku), abym miał się do czego odnosić.

[norwimaj]

W szczegółowym wyjaśnieniu matinf trochę namieszał. Wcześniej napisał dobrze, chociaż skrótowo. Kiedy wstawiamy nowy element do drzewa, przechodząc po ścieżce od korzenia do liścia, to obliczamy sumę trzecich elementów krotek w lewych synach wierzchołków ze ścieżki, a tych jest \(\displaystyle{ O(\log n).}\) Trzeba tylko pamiętać, żeby ten trzeci element krotki dobrze aktualizować przy wszystkich rotacjach. Gdy już mamy liczbę ciągów kończących się na właśnie dodanym elemencie, to aktualizujemy wartości na ścieżce od korzenia do tego elementu w drzewie.

[matinf]

Podam algorytm, dlatego że teraz rozważam bardzo podobny problem - inny temat.
W drzewie przechowujemy trójki:
(element ciągu x, liczba ciągów, które kończą się na element x, suma z całego poddrzewa drugiego elementu tej trójki)

Kod: Zaznacz cały

for i = 1 to n do
   s = znajdź w drzewie liczbę ciągów kończących się na wartości mniejszej niż a_i 
   wstaw do drzewa (t, s + 1, s + 1);
   zaktualizuj trzeci element na wszystkich węzłach od wstawionego do korzenia za pomocą wzoru:
   node.(_, t, s) = node.left(_, _, s) + node.right(_, _, s) + t;

Ważne jest to, aby nie dublować danego elementu, tylko odpowiednio podwajać drugi element trójki i aktualizować trzeci element w górę drzewa

Dziękuję, jeśli ktoś sprawdzi.


PS Obstawiam, ze liniowka nie istnieje.

[Afish]

Kod: Zaznacz cały

s = znajdź w drzewie liczbę ciągów kończących się na wartości mniejszej niż a_i 

A to jak robisz?
Rozrysujesz drzewa dla ciągu \(\displaystyle{ 2,4}\) i \(\displaystyle{ 2,4,2}\)?

[matinf]

inaczej, postawię analogiczny problem, może będzie łatwiej:
możemy wstawiać wartości całkowite do drzewa postaci (6, 100). Oznacza to, że element 6 obciążasz setką. Możesz takie wstawienia wykonać. Czy potrafisz teraz na drzewie AVL zsumować obciążenia elementów na przedziale 1...312 ? No potrafisz, bo kluczem jest pierwszy element pary. Zawsze jesteś w stanie podjąć decyzję: skręcić w lewo czy w prawo. Jeśli skręcasz w prawo to dodajesz do sumy sumaryczne obciążenie dla całego poddrzewa lewego.

[Afish]

To jest jasne, martwi mnie tylko fakt, że drzewo AVL jest drzewem BST, co implikuje kolejność uporządkowania kluczy. Z tego powodu mam obawy, że

s = znajdź w drzewie liczbę ciągów kończących się na wartości mniejszej niż a_i

może wymagać przeszukania liniowej liczby kluczy, bo przechowujesz liczbę ciągów kończących się w danym elemencie. Niemniej jeżeli jesteś przekonany, że algorytm się nie ukwadratowi, to nie ma co drążyć tematu.

[matinf]

Ale tutaj sytuacja jest analogiczna co i przy zliczaniu tej sumy.