• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytmika | Problem - Podział ciągu na odpowiednie podciągi

0 głosów
80 wizyt
pytanie zadane 9 stycznia w Algorytmy przez użytkownika WWOTEX Mądrala (6,160 punkty)
Witam,
Ostatnio zajmuję się algorytmiką i mam tu zadanie, do którego sam odpowiedzi nie znajdę. Nie oczekuję koniecznie gotowego sposobu. Czy zna się ktoś na tym i mógłby mi wytłumaczyć co w takich zadaniach się robi i dlaczego?

Zadanie:
Podziałem ciągu cyfr na sumy nazwiemy podział go na spójne podciągi, które mają tę własność, że suma cyfr w i-tym podciągu jest mniejsza bądź równa sumie cyfr w i+1-tym podciągu. Przykładowo dla ciągu ‘11157’ poprawnym podziałem jest ’11-15-7’. Twoim zadaniem, jest dla podanego ciągu, obliczyć liczbę jego różnych podziałów na sumy.

Przykład:
Wejściowy ciąg: 112                 Poprawna odpowiedź: 4
Wejściowy ciąg: 11                   Poprawna odpowiedź: 2

Ilość liczb w ciągu to maksymalnie 50, a każdy program ma maksymalnie 1000 zestawów testowych(ciągów do obliczenia).

Z góry dziękuję chętnym za poświęcenie cennego czasu! :)

2 odpowiedzi

+1 głos
odpowiedź 12 stycznia przez użytkownika Benek Pasjonat (21,950 punkty)
wybrane 6 dni temu przez użytkownika WWOTEX
 
Najlepsza

To zadanie faktycznie jest złożone i liczenie wszystkich przypadków nie ma sensu. Mamy jednak tutaj pewne ograniczenie górne, które eliminuje nam pewne rozwiązania bez potrzeby ich dalszego badania i tracenia zasobów obliczeniowych.

TEORIA

Punktem wyjścia niech będzie definicja nowego ciągu utworzonego z ciągu pierwotnego. Każdy N-elementowy ciąg K możemy przekształcić do nowego ciągu Q :

K = {k1, k2, ... , kN}, N <= 50
Q = {q0, q1, ... , qM}, M <= N

Ciąg Q ma tę własność, że jest nierosnący i może być złożony z dowolnej kombinacji sum cyfr z ciągu K, przykładowo zakładając N=9 możemy skonstruować ciąg:

q0 = k8 + k9
q1 = k7
q2 = k6 + k5
q3 = k4 + k3 + k2 + k1

wtedy i tylko, gdy:
q3 <= q2 <= q1 <= q0

Na przykład wiemy, że każdy ciąg K będzie zawierał podciąg zupełny, który po przekształceniu do ciągu Q da nam ciąg jednoelementowy:

K = {1,2,6,3,4}
Q = {16}, bo q0 = 1 + 2 + 6 + 3 + 4

Z założeń zadania wiemy, że ostatni wyraz dowolnego podciągu ma osiągać maksimum. Taki wyraz możemy wyznaczyć, czyli wyznaczyć ostatnie j cyfr, które będą stanowić q0. Niestety jest to zadanie wieloetapowe, ponieważ zależy ono od pozostałych wyrazów ciągu Q, idąc od końca do początku ciągu K .

WYZNACZENIE ELEMENTU q0

Najpierw wędrujemy od końca ciągu K ku jego początkowi, szukając lokalnego maksimum. Jeśli na ostatniej N-tej pozycji mamy cyfrę taką że:

k(N-1) <= k(N)

to zakładamy, że jest to lokalne maksimum i przechodzimy do badania elementu q1. Jeśli tak nie jest, to sumujemy elementy i porównujemy ich sumę. Załóżmy, że lokalne maksimum jest na pozycji N-3. Wtedy zajdzie:

k(N-3) > k(N-2) + k(N-1) + k(N)

Przykładem niech będzie ciąg 12457321. Widzimy, że jego podział będzie zawsze taki, że ostatnie cztery cyfry będą razem 7321. Nie da się tego już podzielić, bo 7 zawsze będzie większa od sumy 3, 2 i 1. Dla tego ciągu q0 = 13. To jednak nie jest odpowiedź, bo q0 może być większe, a to wszystko zależy od tego, czy pozostałe elementy spełnią założenie relacji <=.

POZOSTAŁE ELEMENTY CIĄGU Q

Z poprzedniego kroku mamy już pewne górne ograniczenie. Otóż element q1 musi być mniejszy bądź równy q0. Najrozsądniej będzie dokładać kolejne cyfry tworząc sumy q1 dopóki warunek q0 => q1 będzie spełniony. Gdy przekroczymy tę barierę, to wyznaczyliśmy q1. Teraz należy analogicznie wyznaczyć q2 i pozostałe elementy, dochodząc do początku ciągu. Oczywiście może się zdarzyć, że q1 < q2 nawet jeśli q2 składa się z jednego elementu. Przykład 13281237321. W tym przypadku:

q0 = 13 = 7 + 3 + 2 + 1
q1 = 6 = 1 + 2 + 3
q2 = 8

Widzimy więc, że nie ma sensu badanie ciągów, dla których q0 = 7 + 3 + 2 + 1. Innymi słowy z sekwencji 12457321 nie da się zbudować pociągu, który miałby ostatni wyraz równy 7321, oszczędzamy więc czas. Co wtedy? Wtedy należy wrócić do q0 i powiększyć je o dodatkową cyfrę i powtórzyć całą procedurę, czyli wracając do przykładu wyżej teraz q0 będzie równe 5+7+3+2+1=18.

CIĄG Q SPEŁNIA ZAŁOŻENIA

Postępując z powyższą instrukcją w końcu dojdziemy do sytuacji, kiedy to:

qM <= ... <= q1 <= q0

Niestety to nie koniec. Po pierwsze wyznaczyliśmy tylko q0 graniczne. Dokładając kolejną liczbę z lewej strony otrzymamy nowe q0 i w rzeczywistości tak musimy zrobić, bo mamy zbadać przecież wszystkie podciągi. Zwróćmy uwagę, że dokładając cyfry z lewej strony w końcu dojdziemy do sytuacji, gdzie podciąg będzie równy wyjściowemu ciągowi K. Po drugie, co gorsze, musimy również zbadać pozostałe przypadki zmniejszając i-ty wyraz qi. Niemniej, procedury zawsze zostaną przerwane, jeśli zajdzie:

q'(i+1) > q'(i)

i dalsze badanie wyrazów nie ma sensu.

0 głosów
odpowiedź 10 stycznia przez użytkownika morele123 Gaduła (3,890 punkty)
No ja to bym po prostu wypisał wszystkie możliwe takie podciągi i policzył ile ich jest, a nawet nie wypisywał tylko sprawdzał czy taki ciąg istnieje. Sprawdzałbym poprzez porównywanie wszysttkich elementów.
komentarz 11 stycznia przez użytkownika WWOTEX Mądrala (6,160 punkty)
W ten sposób byłoby za prosto. To by dało rozwiązanie zbyt dużej złożoności. Nie umiem ci jej na szybko podać, ale wiem, że byłaby za duża. Potrzebne mi rozwiązanie liniowe lub kwadratowe ewentualnie, bo też powinno wejść. (ale założę się że jest rozwiązanie liniowe)
komentarz 11 stycznia przez użytkownika morele123 Gaduła (3,890 punkty)
Mam tego świadomość i nie widzę innego sposobu. Co nie znaczy, że go nie ma. Co do złożoności no to kwadratowa powinna być, jeśli nie mniejsza.

Podobne pytania

0 głosów
2 odpowiedzi 94 wizyt
pytanie zadane 23 listopada 2016 w Algorytmy przez użytkownika Piotr Ponikwia Początkujący (270 punkty)
+1 głos
3 odpowiedzi 180 wizyt
pytanie zadane 9 kwietnia 2016 w Rozwój zawodowy, nauka, szkoła, praca przez użytkownika ojel Nowicjusz (190 punkty)
0 głosów
2 odpowiedzi 85 wizyt
pytanie zadane 10 listopada 2016 w Algorytmy przez użytkownika BlueWee Użytkownik (650 punkty)
...