Ilość n-elementowych malejących podciagów ciągu

Question

Siemka,

mam trudność z wymyśleniem jakiegoś sensownego sposobu na znalezienie w dosyć szybki sposób (przynajmniej szybszy od O(n^2)) liczby wszystkich n-elementowych malejących podciagów ciągu. Dodatkowy haczyk polega na tym, że podciąg ten niekoniecznie musi się składać z kolejnych wartości oryginalnego ciągu.

Przykład:

ciąg: 2 7 8 9 8 8 1 2, n = 3

poprawna odpowiedź: 4

wyjasnienie:

• 2 7 8 9 8 8 1 2
• 2 7 8 9 8 8 1 2
• 2 7 8 9 8 8 1 2
• 2 7 8 9 8 8 1 2

Comments

Łatwo da się chyba znaleźć liczbę wszystkich podciągów malejących. Znalezienie liczby podciągów dla konkretnego n będzie trudniejsze

Answer 1

To jest zadanie klasy O(n) lub O(n * logn). Bardzo proste IMO. Chyba, ze czegoś nie rozmiem....

 

Piszesz o wszystkich n-elementowych malejących podciągach. Dlaczego wszystkie podciągi są tutaj 3-elementowe? A co z 2-elementowymi?

Masz oryginalną treść zadania i czy to "wyjaśnienie" to jest Twoje, czy dołączone do zadania?

 

Comments

masz rację, zakreśliłem tylko te 3-elementowe, i rzeczywiście zadanie polega na znalezieniu tych 3-elementowych (niedopatrzenie podczas kopiowania kawałka treści zadania), ale ja chciałem uogólnić tą treść i znaleźć rozwiązanie dla każdej wartości n.

---

Dla trójelementowych to jest dużo prostsze niż dla n w ogólnym przypadku. Wtedy n będzie z przedziału <2, 10>.

---

a masz jakiś konkretny plan na zrobienie tego zadania dla trójek?

---

Robiłem podobne zadanie, tylko trzeba było znaleźć jeden najdłuższy ciąg malejący czy rosnący. U ciebie może być wiele trójelementowych, więc to trochę inaczej wygląda, ale zastanowię się i może wrzucę kod, ale nie w C++ :)

Spodobał mi się ten przykład, spróbuję go zrobić.

 

---

Rozwiązanie dla n=3 jest chociażby tutaj: https://forum.pasja-informatyki.pl/576478/w-jaki-sposob-uzyc-drzewa-przedzialowego