Tylko ty podałeś rozwiązanie na największy spójny podciąg.
Tez na początku tak myślałem
.Tylko w tym rzecz trzeba znaleźć największy podciąg i niemam pomysłu kompletnie jak to rozwiązać w dobrym czasie narazie mam tylko O(n*n*t) i z programowaniem dynamicznym nie ma nic wspólnego.
UPS ! Codzień jakaś wtopa .
No to pozostaje zastosować taki myk - tworzysz tablice n*2001 ( - 1000..1000 ). W tablicy zaznaczasz różnice między bierzącym elementem danych wejściowych a wszystkimi kolejnymi do końca .
9
1 0 7 9 12 13 14 15 19
Analizę danych zaczynasz od ostatniego elementu danych wejściowych
__| 0 1 2 3 4 5 6 7 8 ( index )
19| 0 0 0 0 0 0 0 0 0 ...
Będzie ona wypełniona samymi zerami . Dla przed ostatniego elementu
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 1
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 2
14| 0 1 0 0 0 1 0 0...
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 3`
13| 0 1 1 0 0 0 1 0
14| 0 1 0 0 0 1 0 0...
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 4
12| 0 1 1 1 0 0 0 1...
13| 0 1 1 0 0 0 1 0...
14| 0 1 0 0 0 1 0 0...
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
__| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 5
09| 0 0 0 1 1 1 1 0 0 0 1...
12| 0 1 1 1 0 0 0 1...
13| 0 1 1 0 0 0 1 0...
14| 0 1 0 0 0 1 0 0...
15| 0 0 0 0 1 0 0 0...
19| 0 0 0 0 0 0 0 0...
Jak nietrudno zauważyć - wszystkie dane w bieżącym wierszu w stosunku do wiersza poniżej , są przesunięte o różnice między wartościami kolejnych danych wejściowych ( wystarczy przekopiować odpowiednio przesuwając ) .
Złożoność dla brute force -- pewnie gdzieś w okolicy n*n/2*sqrt(n*2) .
Załóżmy że pierwsza liczba to 100 a druga to 600 to kolejny element takiego ciągu już wychodzi po za zakres 1000 i podciąg dla różnicy 500 będzie miał co najwyżej 2 elementy . Jeżeli znalazłeś już podciąg o długości 50 elementów to w dalszych poszukiwaniach nie ma sensu rozpatrywać większej różnicy miedzy elementami niż 20 .
Moim zdaniem trochę złe podejśćie, nawet a może przede wszystkim w procesie uczenia się programowania i algorytmiki. Masz do rozwiązania zadanie-problem i to Ty decydujesz jaką metodą starasz się je rozwiążać/ywać. Potem to może faktycznie, kierownik powie, że masz to zrobić w taki i taki sposób, taką lub inną metodą i już. Teraz masz jeszcze wolność i swobodę wyboru. Więc jeżeli tak bardzo chcesz tu masz zadania otagowane programowanie dynamiczne: http://www.spoj.com/problems/tag/dynamic-programming7 ale czy są fajne, nie mam ani bladego ani zielonego pojęcia.
To nie znaczy, że musisz je tak rozwiązywać - ja zrobiłem zwykłym brutem z małą optymalizacją - ale trudno to nazwać, że zrobiłem w PD.
Tam raczej nie ma wszystkiego, więc może najlepiej zapytać prowadzącego?
PS
Dzień bez wtopy to dzień zmarnowany 
Nie rozumiem twojej metody - rozwiązałeś w taki sposób to zadanie?
Dla dwu elementowego ciągu [np 0, 1000 lub 1000, 0] tak - ale czy dla dwóch warto sprawdzać?
Dla trzech elementów max diff [[0,500,1000] == 500 lub -500, ale może też to szybko sprawdzić, a tablicę zacząć budować dopiero dla ciągów większych niż ..... i wtedy też mniejsza tablica lub tablica dynamiczna - mapa itd.
Nie widzę, jak twoja tablica zadziała dla ciągu np 1 1 1 1 1 2 3 .... lub 3 3 3 3 1 1 1 1 1 itd
Także, gdy jednakowe różnice "zazębią" się:
np (0 4 6 10 ...)
6 - 0 = 6 i 10 - 4 = 6 ?
No tak, ale jeżeli wybrane jest zadanie już z konkretnego działu to domyślnie pomysł na zadanie i jego rozwiazanie powinno być z tego wypadku PD. Każde zadanie powinno dać się też w inny sposób. W tym zadaniu trudno znaleźć pomysł na PD. Oczywiście te zadanie nie należy do łatwych, ale chciałbym je zrobić na PD.
Właśnie nie mam tego zadania rozwiązanego .
Dla takich danych algorytm zawiedzie -- trzeba go udoskonalić . W tablicy zamiast trzymać informacje że dana różnica wystąpiła trzeba przechowywać informacje o najdłuższe ścieżce podciągu ( dla danej różnicy ) jaka dotychczas wystąpiła .
For L1=N-1 downto 1 do Begin
For L2=L1+1 to N do Begin
Rest := Input[ oL1 ] - Input[ oL2 ];
If Dat[ L1 ][ Rest ] <= Dat[ L2 ][ oRest ] Then Dat[ L1 ][ Rest ] = Dat[ L2 ][ Rest ] +1;
End;
End;For L1=N-1 downto 1 do Begin
For L2=L1+1 to N do Begin
Rest := Input[ oL1 ] - Input[ oL2 ]; // Rest := Input[ L1 ] - Input[ L2 ]; ???
If Dat[ L1 ][ Rest ] <= Dat[ L2 ][ oRest ] Then Dat[ L1 ][ Rest ] = Dat[ L2 ][ Rest ] +1;
End;
End;
Nie rozwiązywałem tego zadania ale ciąg stały to też jest ciąg arytmetyczny z różnicą równą zero.Tak jest w tablicach matematycznych do szkół średnich.
W poradniku matematyczny dotyczącym już bardziej zaawansowanej matematyki (red. Dziubiński i Świątkowski) nie znalazłem wprost odniesienia do ciągu stałego, ale ciąg stały spełnia założenia definicji.
W podręcznikach zaawansowanej matematyki (przynajmniej w tych do których zaglądałem) nie znalazłem w ogóle odwołań do ciągu arytmetycznego. Jest dość zrozumiałe gdyż na studiach ciągiem arytmetycznym nikt się zajmuje.
A jak jest tutaj?
Może Autor wyłączył ciąg stały jako trywialny?
Moim zdaniem nie byłoby to dobre rozwiązanie, ale też nie robiłbym z tego tragedii.
W każdym razie to Autor ma władzę 
Pewnie masz rację ja tez nie rozwiązałem tego zadania. Ale czy ciąg stały nie może też być ciągiem geometrycznym?
Co złego w tym kodzie, lub jakieś przykłady dla którego nie działa. Unordered_map nie używałam więc mogłam coś namieszać…
…
Napisałem, że nie zrobiłem tego zadania i faktycznie, na podstronie WSDOCPP, nie zrobiłem. Ale to zadanie jest też na stronie pl.spoj i tam mam je zrobione.
Co do twojego rozwiązania. Dla ciągu dłuższego niż dwuelementowy, minimalna długoć to 2.
Masz w swoim teście wstawioną złą wartość t i może coś jeszcze? W jednym teście masz wynik 0 - a i w ostatnim - jaki dodałem też jest żle: https://ideone.com/8QqZMB3
Faktycznie, był jezcze jeden błąd w teście, poprawiłem i teraz jest ok.
Tzn, troche lepiej.
Wydaje mi się, że Twoj kod ma problem z powtarzającymi się liczbami. No i gdy juz jakas mamy długość, to nie szukamy do n-1, tylko raczej n-dl, czy może n-dl-1?
Błąd jest tutaj:
for(int j=i+1;j<n;j++) // szukamy ciągu arytmetycznego kończącego się na j i zaczynającego się na i
///a w środku tej pętli zmieniasz sobie j, więc Sama rozumiesz co się dzieje? :
j = ..... mp[next][k]; // uaktualniamy j na indeks kolejnego elementu ciąguNo i za wolno, dużo za woooooooolno. Pomyśl:
Taki ciąg:
1000
4 4 4 4 4 … 4 4 4 4 4 4 4 4 4
Mimo, że już po pierwszej iteracji program znajdzie najdłuższy ciąg = 1000, to i tak, będzie dalej szukał coraz to krótszych ciągów.
Podobnie dla takiego ciągu:
1000
1 2 … 999 1000
I dla podobnych do powyższych, lekko “zanieczyzczonych” wtrąconymi, dowolnymi liczbami.
Wspominałem o tym 3 posty wyżej.
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| MBPROB01 - History version in plaintext pl.spoj.com | Zbiór zadań | 6 | 178 | Jul '24 |
| FR_20_02 - Poszukiwacze skarbów - Błąd w testach? | Zbiór zadań | 1 | 99 | Apr 2 |
| PP0504B - StringMerge - w języku C | Zbiór zadań | 5 | 207 | Jun '24 |
| FR_08_11 - Gra w bańki | Zbiór zadań | 1 | 168 | Jun '24 |
| TOPSORTL - Porządek leksykograficzny w grafie | Zbiór zadań | 3 | 149 | Jul '24 |
Wiem co ma robić, a jakoś umknęło… Poprawa wraca do przekroczenie czasu…wrrr