Programowanie dynamiczne - problem z zastosowaniem

Chcesz poznać moje problemy z programowaniem dynamicznym? Najważniejsze różnice: nie ma niczego w necie bo problemy narzuca rynek i za brak rozwiązania z dowodem poprawności tracisz pracę bo nie umiesz zrobić dobrego modelu Implementacja to pikuś, choć po ostatnim pomyśle “warstwy biznesowej” mam co robić z pełnym wdrożeniem rozwiązania.

Cicho! Na tym forum są ludzie, którzy uważają, że googlowanie to zbrodnia bo to szukanie gotowców co musi być złe! Ludzie, którzy nawet tablic maturalnych nie uznają bo przecież to ściąga

1. jak patrzę na hotele to moje rozwiązanie nie jest dynamikiem. Znaczy formalnie, czysto teoretycznie, jest to pewien szczególny trywialny przypadek dynamika, ale nikt w realu nie nazwie tego nawet rozwiązaniem zachłannym tylko inaczej… (jeśli podpowiadam albo wprost przeciwnie gmatwam to sorry)
2. igiełka jest w średnich więc możemy przyjąć, że nie jest łatwa ergo nie jest prost(sz)a
3. programiści - a zwłaszcza nowi - rzadko stosują dynamiki. O kwestie zawodowe martwić się tutaj nie musisz.

Ona jest praktyczna w takim kontekście w jakim została napisana. Na SPOJu dzieło bezwartościowe chyba, że znudziło Ci się wygrywanie tysiaków w Dolinie Krzemowej i postanowiłeś w ramach emerytury ogarniać FRAKTALe. Wtedy jednak nawet nie musisz tam zerkać by z pamięci przepisywać dużo ambitniejsze rzeczy

Jako autor własnych BigNumów polecam Ci ćwiczenie: zaimplementować coś takiego samemu. Idea jest prosta, podpowiedzi w sieci co nie miara, zabaw typu robienie potem własnych BigFractionów albo wyznaczanie liczby pi z dokładnością do n-tej cyfry w postaci ułamka nieskracalnego jeszcze więcej. Oczywiście jeżeli już umiesz tworzyć funkcjonalne klasy to szkoda czasu na to ćwiczenie.

Niestety to najlepsza książka (moim zdaniem) w kontekście SPOJa. I nie tylko. Ma oczywiście wady, np. jest rozwodniona różnymi bzdetowatymi ćwiczonkami i takimi tam, ale co kto lubi. Do tego wykłady algorytmiki stosowanej http://was.zaa.mimuw.edu.pl/23 i ASD ze strony https://eduinf.waw.pl/inf/alg/001_search/index.php20.

Nie powiem Ci niestety jak masz to czytać, aby zrozumieć. Wiele zależy od tego ile chcesz rozumieć. Jeżeli sporo:

1. Zrób sobie plik. Najlepiej zwykły “wordowski”, ale to pod warunkiem, że umiesz już zrobić taki w LaTeX Plik ma składać się z punktów typu:

   1. Zaimplementuj sortowanie przez wstawianie na sposób iteracyjny i rekurencyjny (Cormen, s. 22, zadania, własne)
   2. Zaimplementuj sortowanie przez wybór na sposób iteracyjny i rekurencyjny (Cormen, s. 28, zadania, własne)
   3. Zaimplementuj sortowanie bąbelkowe na sposób iteracyjny i rekurencyjny (Cormen, s. 40, zadania, własne)
   4. Zaimplementuj algorytmy wyszukiwania liniowego i binarnego na sposób iteracyjny i rekurencyjny (Cormen, s. 38, zadania, własne)
   5. Zaimplementuj algorytm merge, który przyjmuje tablicę n-elementową A, której dwie części są posortowane niezależnie od siebie, tzn A[l..m] i A[m + 1..r] gdzie l <= m < r są posortowane (Cormen, s. 31 i zadania s. 38)
   6. Zaimplementuj algorytm partition, który dla elementów tablicy A[l..r] dokona ich podziału względem elementu A[m], l <= m <= r. Elementy na lewo od A[m] będą mniejsze (lub równe A[m], a na prawo – większe (Cormen, s. 169 – 172)
   7. Zaimplementuj algorytm sortowania przez scalanie (Cormen, s. 34)
   

2. w drugiej części pliku oczywiście teoria typu:

   12. Zademonstruj jednoczesne wyznaczenie minimum i maksimum zbioru wykonując około 3n/2 porównań dla zbioru liczb: 9, 9, 1, 3, 7, 0, 1, 9, 3, 2
   13. Zademonstruj wyszukiwanie lidera w zbiorze 1, 2, 1, 3, 3, 3, 3, 2, 3
   14. Zademonstruj drzewo BST utworzone z liczb: 9, 9, 1, 3, 7, 0, 1, 9, 3, 2. Następnie podaj jego wierzchołki w kolejności pre-, in- oraz post-order, a także zademonstruj wyszukiwanie minimum i maksimum z     elementów znajdujących się w drzewie
   

3. Masz zadania, wiesz gdzie szukać odpowiedzi (odpowiednie nawiasy za każdym pytaniem; btw nie wszystko jest w Cormienie, ale plik zacznij tworzyć bazując na nim + Tarnów LO), masz cały internet (patrz: np. moje linki, geeksforgeeks) w razie problemów “czemu tak a nie inaczej?” więc… robisz po kolei. Zaczynasz od teorii - jeżeli rozumiesz, tzn. potrafisz krok po kroku np. zademonstrować wyszukiwanie lidera w zbiorze (zad. 13) albo dane sortowanie dla 10 liczb to bierzesz się za kodowanie tego. NIGDY W JEDNYM JĘZYKU bo wtedy zamiast doskonalić zrozumienie ćwiczysz pamięciowe opanowanie kodu co jest beee. Polecam napisać kod najpierw w C++ (bo najłatwiej znaleźć pomoc w razie problemów), potem w Javie (bo podobna do C++), potem JavaScript, PHP, Python i Perl. Za każdym razem DOKŁADNIE weryfikuj poprawność swojego rozwiązania - testy z sieci, gotowce z sieci, … . Najlepiej stwórz sobie zestawy testowe i program sprawdzaj przekierowując kolejne inputy i diffując kolejne outputy, ale to już ofc. jak będziesz przerabiać dane ćwiczenie po raz enty i jedynym możliwym błędem będzie pomylenie i++ z ++i W zadaniach z C++ mam np. takie makro, które pomaga mi sprawdzać sortowania - “naocznie” porównuję wyniki moich kodów i tego co robi działająca funkcja biblioteczna:

   #define ti(arr, brr, n) for(int i = 0; i < n; ++i)\
                    cout << arr[i] << " ";\
                    cout << endl;\
                    cout << isort(arr, 0, n - 1) << endl;\
                    for(int i = 0; i < n; ++i)\
                    cout << arr[i] << " ";\
                    cout << endl;\
                    sort(brr, brr + n);\
                    for(int i = 0; i < n; ++i)\
                    cout << brr[i] << " ";\
                    cout << endl << endl;
   

Co ważne, jeżeli nie umiesz poradzić sobie z czymś teoretycznym to w ogóle nie bierz się za kodowanie. Podstawą jest dla Ciebie pseudokod z Cormena - jeżeli naprawdę nie wiesz o co chodzi to dla coraz bardziej złożonych danych piszesz na duuużej ilości kartek papieru krok po kroku co się dzieje po wykonaniu danej linii kodu. Na ogół to wystarcza by załapać, że “no przecież, ta pętla pozwala sprawdzić, czy…”.

Jeżeli interesuje Cię SPOJ to fascynujące teorematy o liczeniu takich a nie innych złożoności z uśmiechem na twarzy pomijasz podobnie jak rozdziały o kopcach Fibbonacciego itp.

Najpierw podstawy (to co wypisałem). Potem kreatywność - nie walczymy z średnimi nie mając 50% łatwych (choć nie każdy się ze mną zgodzi). Co jakiś czas możesz posiłkować się gotowcami, aby wpaść na ideę rozwiązywania danego typu problemów na SPOJu (i nie tylko), ale w takim przypadku bezmyślne przeklejanie kodu jest złe - trzeba go dokładnie przeczytać i zrozumieć aby odkryć przczyny swoich niepowodzeń. Często poznasz w ten sposób nowe algorytmy - w sam raz do dopisania do listy

Nie ma “prawdziwych programistów” na rynku pracy. Są konkretne zadania i konkretni ludzie ze swoimi ambicjami, ograniczeniami, planami, pomysłami itp. Albo je realizujesz albo nie. Gwarantuję Ci, że zdumiewająca większość zadań nie polegających na bezmyślnym klepaniu kodu jest daleka od algorytmiki, choć oczywiście nawyki wyniesione z rozwiązywania nawet prostych zadań algorytmicznych są wskazane np. przy tworzeniu jakiejś nowej funkcjonalności w danym projekcie.

Ja długo nie mogłem z czystym sumieniem powiedzieć, że rozumiem rekurencję. Dopiero https://pl.spoj.com/problems/AL_16_09/31 pozwoliło mi ją zrozumieć i potem już jakoś poszło z dynamikami i nie tylko. Jak coś zacząłem od rysynku “drzewka” dla dwóch strzałów, potem szkic dla trzech, a potem już wiedziałem co chcę zrobić tylko zostało jeszcze to zapisać rekurencyjnie. I wyszło. Dla mnie najtrudniejsze było dostrzeżenie co robi rekurencja w takich stosowanych przypadkach na poziomie wyższym niż liczenie silni i po dziś dzień uważam, że to zadanie świetnie to obrazuje.

To chyba jedno z najlepszych zadań na SPOJu (brawo @witman!)

DISCLAIMER

1. nie przerobiłem niestety nawet połowy mojego pliku z Cormenem i innymi bo praca zabrała mi sporo czasu. Natomiast nie dobiłem dwudziestego zadania z każdej części, a we fraktalach skoczyłem z okolic miejsca 20-któregoś do pierwszej dziesiątki (przedostatnio byłem chyba piąty, ostatnio chyba 10., a przedostatnio właśnie 20-któryś)
2. formalnie nie posiadam wykształcenia informatycznego
3. fajnie posłuchać innych, ale pamiętaj, że Ty wiesz co robić i czego potrzebujesz. Nie traktuj więc moich odpowiedzi jako jakichś prawd objawionych - to tylko moja metoda, a choćbym miał pierwsze miejsce na Code Jam to nie udowodnię, że to dzięki tej metodzie
4. metoda, którą Ci proponuję, jest ciężka, ale gwarantuję, że ćwicząc dany algorytm po raz enty będzie Ci się on śnił po nocach, a jak już podstawy będą bardzo klarowne to przejście do dynamików też nie będzie trudne.
5. ucz się niekoniecznie w takiej kolejności, jaką sugeruje Cormen
6. algorytmów ucz się “po ludzku” - żadnych cudów typu sortowanie struktur na templatach z funkcjami lambda itp. Algorytm to matematyka i masz to rozumieć matematycznie. Na dzikie implementacje też przyjdzie czas, ale na pewno nie gdy widzisz coś pierwszy raz na oczy. W szczególności stosowanie vectorów do nauki sortowań jest złe bo zaćmiewa to prostą ideę tablicy, choć oczywiście jak zrobisz wszystko na tablicy to czemu nie na vectorze?
7. piszę dużo o sortowaniu bo od sortowania musisz zacząć, np. ogarnąć te inwersje. Dynamiki to gdzieś tak połowa drogi

Odnajduję się w wielu punktach, które opisałeś.

Według mnie jest to spowodowane tym, że większość zadań łatwych i kilkadziesiąt średnich bardziej się skupia na teorii i na podstawach algorytmiki, niż na samodzielnym myśleniu. Dopiero po przebrnięciu przez te zadania zaczynają się ciekawsze rzeczy (np. zadania w których googlowanie do niczego nie doprowadzi, zadania które trzeba sprowadzić do innych, prostszych problemów, zadania w których wymagane są jakieś sprytne modyfikacje znanych algorytmów, itp…). Wydaje mi się, że niestety wiele osób traci motywację zanim uda im się dotrzeć do tych perełek. Często bywa też tak, że ludzie się zniechęcają gdy widzą, że zadanie, które próbują rozwiązać jest dla nich za trudne. Sam kilka razy dochodziłem do wniosku, że już więcej zadań nie potrafię zrobić. Z drugiej strony jednak, katowanie zbyt trudnych zadań jest chyba najszybszą drogą do rozwoju. Sam tego doświadczyłem podczas walki z zadaniami Dżungla14 i XOR8. Co prawda w Dżungli nadal nie mam AC, ale i tak uważam, że jeszcze żadne zadanie mnie tyle nie nauczyło jeśli chodzi o drzewa przedziałowe.

Też raczej jeszcze raczkuję jeśli chodzi o drzewa przedziałowe. W moim przypadku największe zamieszanie było spowodowane tym, że istnieje wiele gatunków tych drzew. Kluczem jeśli chodzi o naukę tego tematu było dla mnie zapoznanie się z kilkoma podstawowymi drzewami - Fenwick tree (AKA binary indexed tree), merge sort tree, interval tree i segment tree. Też pamiętam, że miałem problemy ze znalezieniem sensownego kursu. W końcu wyszło tak, że próbowałem aż do skutku napisać własną wersję tych drzew posiłkując się Wikipedią i implementacjami z Githuba
Jeśli chodzi o merge sort tree, pomocny był ten materiał: https://discuss.codechef.com/questions/94448/merge-sort-tree-tutorial10

Pamiętam, że potrzebowałem kilku podejść jeśli chodzi o grafy. Za pierwszym razem nic nie wskórałem, za drugim też nie, ale za trzecim coś mi przeskoczyło w głowie. Być może przesadzam, ale mam wrażenie, że większość zadań z grafami sprowadza się do użycia zmodyfikowanej wersji DFS (i/lub BFS).

Ja bym Ci polecał zajrzeć na inne platformy z zadaniami algorytmicznymi (np. Codeforces6, czy chociażby międzynarodową wersję SPOJa). Codeforces oferuje dużo więcej zadań, w których wymagane jest samodzielne myślenie. Plusem jest też to, że możesz filtrować zadania według kategorii, więc jak chcesz się podszkolić w dynamicznym programowaniu to możesz przerabiać zadania z tego działu w rosnącej kolejności pod względem trudności.

To makro jest bez sensu. Wystarczyłoby użycie instrukcji warunkowej/asercji z std::is_sorted, a do wypisania użyć najnormalniejszej funkcji/szablonu (lub po prostu debuggera).

Jak uważasz

Jak najbardziej

To ja mam inną wskazówkę. Ktoś kiedyś niefortunnie wprowadził na spoju podział na łatwe, średnie i trudne. Na to zupełnie nie ma co patrzeć. Czemu nie wprowadzić na przykład innego podziału np. na zadania ciekawe, bardziej ciekawe i najprzyjemniejsze? Wprowadź sobie własną skalę taką, że im bardziej nie wiesz jak rozwiązać dane zadanie i próbowałeś wielu sposobów, które nie przynoszą efektów, to dopiero wtedy robi się najciekawiej i najprzyjemniej! Nie wtedy kiedy widzisz rozwiązanie zadania od razu, tylko wtedy kiedy kolejna próba zawodzi i poszukujesz i podejmujesz następne i nie odpuszczasz. Punktuj podjęte nieudane próby, popełnione błędy, a nie udane rozwiązania. Jeśli będziesz czerpać z tego przyjemność i przy tym zaspakajać swoją ciekawość, to znajomość algorytmów i kreatywne myślenie stanie się drugorzędne i przyjdzie samo.

Podejrzewam, że nie [tylko] dobrymi chęciami, ale takimi podejrzeniami jest piekło wybrukowane. Jeżeli nie wiesz na pewno, a tylko gdzieś to wyczytałeś [np na forum ode mnie] to lepiej nie pisz i nie powtarzaj takich rzeczy, bo obrażasz nie tylko adminów, ale każdego myślącego użytkownika portalu. Jeżeli przeczytałeś to w jakiejś mojej starej wypowiedzi, to pisałem to pod wpływem emocji, ale mogę Cię zapewnić, że nie przypominam sobie ani jednego takiego tematu na starym forum.

Sam wiesz, jak zatytułowałeś ten wątek i wsadziłeś go do działu tutoriali i poradników, a ma on tyle wspólnego z poradnikiem PD ile ma piernik do wiatraka. Teraz następne kolejne pokolenia młodych miłośników rozwiązywania zadań algorytmicznych metodą googlowania, szukając informacji na temat PD, może przypadkiem trafić tu i stwierdzić , że ten dział jest do d… a nie do podpowiadania i radzenia, i przy okazji dowiedzą się, jeżeli doczytają do końca, że kiedyś istniał raj na ziemi, stare forum, w którym było wszystko i zostało odebrane biednym programistom.

W sumie nie rozumiem Cię i nie wiem czego oczekujesz, ale być może po prostu dzieli nas przepaść pokoleniowa.

Wprowadzenie … nie jest łagodnym… ani nie jest serią nie dla opornych. To jest swego rodzaju biblia i nie czyta się jej od deski do deski, ale korzysta. A korzystać z książek, najlepiej jednak w formie papierowej, tak jak i z internetu trzeba się nauczyć. I to nie są jedyne książki, więc należy wybrać inne i korzystać nie z jednej czy dwu, ale z dziesięciu i więcej.

Nic z tych rzeczy. Po prostu Cię nie rozumiem. Dla mnie myślenie, to najczęściej kartka papieru i ołówek czy długopis, potem książka, a dopiero na końcu internet. Dla Ciebie, tak zrozumiałem z twojej wypowiedzi, myślenie to googlowanie. Ja musiałem używać suwaka logarytmicznego, Ty pewnie możesz zobaczyć co to jest tylko w internecie, czy może jakimś muzeum.

Zająłeś na ostatnim fraktalu drugie miejsce. Na Spoju masz pewnie rozwiązanych co najmniej 100 zadań. Więc powinieneś już zauważyć, że znajomość algorytmów to jedno, a zastosowanie konkretnego algorytmu do konkretnego zadania …A to już nie to samo…
PD nie jest algorytmem, tak jak rekurencja czy inna metoda, więc może dlatego jest Ci jeszcze trudniej.

Przecież to nie ja z tego korzystam, więc sam pomyśl. A zapomniałem …
Może więc podstawy programowania? A może powinieneś napisać i poprosić adminów, o jakiś dodatkowy dział, np off topik? Po prostu, uważam, że jakbyś napisał jakiś poradnik albo tutorial, to jak najbardziej, tutaj jest odpowiednie miejsce.

Panowie, spokojnie… każdy wyraził swoje zdanie. Toczenie wojen o wyższość takich a nie innych metod rozwiązywania problemów na SPOJu czy w życiu albo o wyższość wiedzy teoretycznej / praktycznej / k-tego miejsca na FRAKTALu / n-tego miejsca na SPOJu / s-tego miejsca na innym konkursie / pracy w IT / m-lat doświadczenia / … względem pozostałych w sytuacji, gdy żaden dyskutant o to nie pytał wprost jest niecelowe i zdecydowanie psuje opinię o polskim SPOJu. Nie róbmy tu biolog pl czy vmc z sensownymi działami kończącymi się dyskusjami na poziomie “merytorycznie wątpliwym”.

A z ciekawostek niektórzy młodzi mieli w rękach suwak logarytmiczny, który np. został po starszym członku rodziny Z pomocą wstępu matematycznego napisanego w jakiejś starej książce do chemii udało mi się nawet tego wihajstra użyć.

zrobiłem to zadania na 9ptk, nie mam pomysłu na zestaw którego nie przechodzi mój algorytm, może ktoś ma testowe dane które mogą nie przejść ?
pozdr.

To tzn. które zadanie (najlepiej link)? W tym temacie sporo zadań się przewinęło…

Btw: nie ten dział. Napisz w “Zbiór zadań”. “Tutoriale, poradniki” służą - jak widać - do czegoś innego.

zadanie Igiełka

O testy będzie ciężko…

robisz to plecakiem? Jak nie to masz przyczynę błędu

Moze sa jakies trudne do przejscia testy, jednak zaliczam tylko 9/15.

Właśnie nie ma trudnych testów. Temu pytam jak to robisz bo jeśli masz heurystykę to oczywiście bez szans. Najprostsze dają może 6/15, ambitniejsze pewnie więcej. Twój wynik sugeruje, że albo skopałeś plecak albo robisz to zupełnie źle.

@eksekk Cześć nie przejmował bym się, zależy kim chcesz być w przyszłości, teoretykiem - algorytmikiem, czy inżynierem.
Obecnie studiuję sobie Wirtualną Maszynę Javy - JVM, przerabiam Java Memory Model, widzę jak przede wszystkim ważny jest zmysł inżynierski, a nie tylko wyuczone algorytmy. Algorytmy odśmiecania pamięci w JVM są połączeniem nie tylko jakiś klasycznych, abstrakcyjnych konceptów ale w dużej mierze znajomością, systemów operacyjnych, architektury i organizacji komputerów, jak działa cache w procesorach, przewidywanie skoków itp.