Programowanie dynamiczne - problem z zastosowaniem

[eksekk]

Tak jak w tytule, mam problem z programowaniem dynamicznym.

Zadania, gdzie trzeba pogooglować, idą mi zazwyczaj dobrze (zarówno takie, że tak to ujmę, proste (!= łatwe), gdzie wystarczy znaleźć jedną rzecz, jak też złożone, w których trzeba zrobić dłuższy research, a niekiedy nawet zastosować rzeczy, które wcześniej robiło się jako pojedyncze zadania).

Niestety w momencie, gdy trzeba cokolwiek wymyślić samemu, leżę. I to totalnie. Nie idą mi zarówno jak mniemam prostsze zadania (takie jak “Igiełka”), jak też te trudniejsze (np. “Tanie hotele” - nie mam pojęcia, kto i w jakim celu je wstawił do łatwych - chyba tylko po to, żeby dołować nowych programistów ). Klasyczny problem sumy podciągu był dla mnie czarną magią, dopóki nie przerobiłem znalezionego w internecie kodu (tzn. przepisywałem i starałem się zrozumieć, czemu działa). Dzisiaj próbowałem zrobić zadanie “Ciąg arytmetyczny II” - rano przyszedł mi do głowy pomysł (jak zresztą dosyć często). Niestety moje rozwiązanie było błędne. Poprawiłem błędy, to przekraczało limit czasu. Wtedy zdałem sobie sprawę, że właściwie robię zwykły brute force i to nie ma prawa przejść. Zero pomysłów, jak to inaczej zrobić. A miało być tak dobrze…

Często mam też problem ze zrozumieniem różnych algorytmów, np. KMP (i nadal nie do końca wiem czy rozumiem, bo nie miałem za bardzo okazji robić zadania, gdzie byłby wymagany). Chciałem zrozumieć drzewa przedziałowe, to nigdzie nie mogłem znaleźć jakiegoś fajnego kursu/tutoriala z przykładami, wszędzie tylko albo sam kod albo niezrozumiały (przynajmniej dla mnie) opis. Wszędzie zaczyna się od reprezentacji drzewa w postaci tablicy, podczas gdy ja do niedawna nie rozumiałem, jak reprezentować i wykonywać operacje na najzwyklejszych binarnych drzewach poszukiwań. Moja próba zrozumienia grafów zakończyła się na próbie zakodowania algorytmu Dijkstry bez korzystania ze wskazówek, potem dałem sobie spokój.

Książki algorytmiczne (głównie w postaci PDF) niby mogłyby być rozwiązaniem, ale obydwie, przez które próbowałem przebrnąć, mają swoje wady. “Algorytmika praktyczna” - niezrozumiały kod, używający makr i jednoliterowych nazw zmiennych, często bez wyjaśnienia, jak dany algorytm działa. Ale spoko, jestem w stanie zrozumieć “praktyczna” w tytule, nawet sam autor w rozdziale dotyczącym BigNumów kładzie nacisk na to, żeby brać, co w danej chwili jest potrzebne. Może też jestem jeszcze za mało zaawansowany, żeby zrozumieć niektóre rzeczy. Niestety, kolejna książka, a mianowicie “Wprowadzenie do algorytmów” (zwracam uwagę na “wprowadzenie” w tytule) też mnie zawiodła. Szczerze przyznam, że przerwałem czytanie w momencie, w którym po zaprezentowaniu sortowania przez scalanie autor dał zadanie polegające na wyznaczeniu liczby inwersji w tablicy w czasie O(n log n) (jako wskazówka jest podane, żeby użyć właśnie sortowania przez scalanie). Nie wiem, czy to ja jestem jakiś niemyślący, ale gdyby nie to, że wiedziałem już o tym przed rozpoczęciem czytania, nigdy bym nie wpadł na to, że w ogóle można za pomocą merge sort takie coś zrealizować, a co dopiero zaimplementować (nawiasem pisząc nadal nie rozumiem, dlaczego ten algorytm działa).

Zastanawiam się, czy może trafiłem już w granicę, która dzieli “prawdziwych programistów” od klepaczy kodu. Ciężko mi idzie kreatywne myślenie, a zauważyłem, że w robieniu nieco bardziej złożonych zadań, gdzie nie widać rozwiązania na pierwszy rzut oka, jest wręcz niezbędne.

Dziękuję tym, którzy przebrnęli przez tę ścianę tekstu. Bardzo mi byłoby miło gdybyście się wypowiedzieli, jak to u was wyglądało, czy może też mieliście takie doświadczenia. Przeglądałem forum, ale nie znalazłem żadnej informacji w tym stylu (poza tematem Czy Spoj [forum] pomaga w pisaniu "dobrych" podpowiedzi?, a w szczególności postem @tarpauwatratar). Podejrzewam, że takich tematów było na starym forum sporo, no ale niestety dla niektórych (adminów) lepiej zepsuć coś, co działało…

[tarpauwatratar]

Mam problem z programowaniem dynamicznym

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.

Zadania, gdzie trzeba pogooglować (…)

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

Niestety w momencie, gdy trzeba cokolwiek wymyślić samemu, leżę. I to totalnie. Nie idą mi zarówno jak mniemam prostsze zadania (takie jak “Igiełka”), jak też te trudniejsze (np. “Tanie hotele” - nie mam pojęcia, kto i w jakim celu je wstawił do łatwych - chyba tylko po to, żeby dołować nowych programistów )

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.

“Algorytmika praktyczna” - niezrozumiały kod, używający makr i jednoliterowych nazw zmiennych, często bez wyjaśnienia, jak dany algorytm działa.

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

(…) sam autor w rozdziale dotyczącym BigNumów kładzie nacisk na to, żeby brać, co w danej chwili jest potrzebne (…)

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.

Szczerze przyznam, że przerwałem czytanie w momencie, w którym po zaprezentowaniu sortowania przez scalanie autor dał zadanie polegające na wyznaczeniu liczby inwersji w tablicy w czasie O(n log n) (jako wskazówka jest podane, żeby użyć właśnie sortowania przez scalanie). Nie wiem, czy to ja jestem jakiś niemyślący, ale gdyby nie to, że wiedziałem już o tym przed rozpoczęciem czytania, nigdy bym nie wpadł na to, że w ogóle można za pomocą merge sort takie coś zrealizować, a co dopiero zaimplementować (nawiasem pisząc nadal nie rozumiem, dlaczego ten algorytm działa).

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/ i ASD ze strony https://eduinf.waw.pl/inf/alg/001_search/index.php.

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.

Zastanawiam się, czy może trafiłem już w granicę, która dzieli “prawdziwych programistów” od klepaczy kodu. Ciężko mi idzie kreatywne myślenie, a zauważyłem, że w robieniu nieco bardziej złożonych zadań, gdzie nie widać rozwiązania na pierwszy rzut oka, jest wręcz niezbędne.

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.

Bardzo mi byłoby miło gdybyście się wypowiedzieli, jak to u was wyglądało, czy może też mieliście takie doświadczenia.

Ja długo nie mogłem z czystym sumieniem powiedzieć, że rozumiem rekurencję. Dopiero https://pl.spoj.com/problems/AL_16_09/ 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

[rzaba]

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

Niestety w momencie, gdy trzeba cokolwiek wymyślić samemu, leżę. I to totalnie.

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żungla i XOR. 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.

Chciałem zrozumieć drzewa przedziałowe, to nigdzie nie mogłem znaleźć jakiegoś fajnego kursu/tutoriala z przykładami, wszędzie tylko albo sam kod albo niezrozumiały (przynajmniej dla mnie) opis.

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-tutorial

Moja próba zrozumienia grafów zakończyła się na próbie zakodowania algorytmu Dijkstry bez korzystania ze wskazówek, potem dałem sobie spokój.

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. Codeforces, 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.

[hipcia]

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;

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).

[tarpauwatratar]

To makro jest bez sensu.

Jak uważasz

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

Jak najbardziej

[swiergu]

Niestety w momencie, gdy trzeba cokolwiek wymyślić samemu, leżę. I to totalnie.

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.

[narbej]

Podejrzewam, że takich tematów było na starym forum sporo, no ale niestety dla niektórych (adminów) lepiej zepsuć coś, co działało…

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.

[eksekk]

Dziękuję za odpowiedzi, nie spodziewałem się takiego odzewu

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)

Podejrzewam, że chcesz mnie nakierować na prostsze rozwiązanie, które niekoniecznie jest dynamikiem. Niestety na razie tego nie dostrzegam, więc będę musiał potem pomyśleć/pogooglować

Jako autor własnych BigNumów polecam Ci ćwiczenie: zaimplementować coś takiego samemu

Kiedyś implementowałem własne BigNumy, ale było to na początku nauki programowania i cała klasa była zorganizowana na stringach, przez co wydajność była fatalna. Niemniej jednak, nauczyłem się wtedy mocnych podstaw programowania obiektowego, co zaprocentowało w przyszłości. Myślę, że zaimplementowanie tego ponownie z doświadczeniem, które mam teraz, jeszcze bardziej mi pomoże (czuję się niekomfortowo chociażby z dzieleniem BigNumów, trzeba to zmienić ).

Zrób sobie plik

Możesz być pewny, że zrobię

NIGDY W JEDNYM JĘZYKU bo wtedy zamiast doskonalić zrozumienie ćwiczysz pamięciowe opanowanie kodu co jest beee.

Masz rację i myślę, że w tym może tkwić część moich problemów ze zrozumieniem różnych algo. Oczywiście posługuję się wyłącznie C++ (poza jednym zadaniem z challenge, które trzeba było zrobić w perlu, ale to się właściwie nie liczy), będę musiał się zabrać za inne języki.

Sam kilka razy dochodziłem do wniosku, że już więcej zadań nie potrafię zrobić

O to to, ja mam tak średnio raz na tydzień

W końcu wyszło tak, że próbowałem aż do skutku napisać własną wersję tych drzew

Ja miałem podobnie z BST, któregoś dnia po prostu postanowiłem, że spróbuję, może mi nie wyjść, ale wtedy najwyżej zajrzę do internetu i jakoś poszło. Zaliczyłem nawet zadanie z trudnych (choć na początku miałem problem ze zrozumieniem, że poprzednik i następnik danego węzła to niekoniecznie jego lewy i prawy syn… tak to jest, jak się nic nie patrzy w internecie). Drzewa przedziałowe pewnie będzie mi najłatwiej ogarnąć podobną metodą.

Ja bym Ci polecał zajrzeć na inne platformy z zadaniami algorytmicznymi

Dzięki, na pewno je sprawdzę

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?

Bardzo fajne podejście, na pewno je zaadoptuję

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.

Może rzeczywiście trochę za ostro napisałem (jeżeli jakiś admin to czyta, to oficjalnie przepraszam). Nie mam pojęcia, czy na starym forum był taki temat, ale fakt, że istniało ono przez kilka razy więcej niż obecne, pozwala mi sądzić, że być może tak było.

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

Do jakiego działu powinienem go zatem wsadzić? Pytam poważnie, mi dział “tutoriale i poradniki” wydawał się najodpowiedniejszy, jako że nie piszę o jednym konkretnym zadaniu, a oczekuję porady, jak radzić sobie z czymś ogólniejszym.

kiedyś istniał raj na ziemi, stare forum, w którym było wszystko i zostało odebrane biednym programistom

Wiem, że piszesz to ironicznie, ale mam właśnie takie podejście i z tego co czasem czytam na forum, wydaje mi się ono słuszne.

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

Jeśli w czasie swojej kariery programistyczno-algorytmicznej nigdy nie miałeś momentu, gdzie pomyślałeś, że:
a) programowanie może nie jest dla Ciebie
b) nie wiesz jak zrobić jakieś zadanie
c) doszedłeś już do szczytu swoich możliwości
To wtedy jednocześnie gratuluję i zazdroszczę, i w takim przypadku mógłbym Cię zrozumieć. Ale w przeciwnym wypadku nie rozumiem, dlaczego mnie nie rozumiesz

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.

Racja, ale jednak te problemy nieco mnie zniechęciły.

[narbej]

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.

Do jakiego działu powinienem go zatem wsadzić?

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.

[eksekk]

Dla Ciebie, tak zrozumiałem z twojej wypowiedzi, myślenie to googlowanie.

Czyli źle zrozumiałeś. Nie googluję jak zrobić każde zadanie, tylko googluję rzeczy, na które jest prawie niemożliwym wpaść w inny sposób (przykład: zadanie “Dzielenie” (AL_31_05): czy wpadłbyś za pomocą kartki i długopisu na to, że długość okresu ułamka to multiplicative order 10 modulo mianownik bez czynników równych 2 i 5, a cyfry przed okresem to max(wykładnik 2 w faktoryzacji mianownika, wykładnik 5 w faktoryzacji mianownika)? Nawet mając na uwadze Twoje doświadczenie, nie uwierzyłbym w odpowiedź twierdzącą). Jeśli tylko jest możliwość też korzystam najpierw z kartki papieru i długopisu, ale czasem po prostu się nie da.

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…

Nie mam problemów z dopasowaniem konkretnego algorytmu do odpowiedniego zadania, tylko problem z takimi zadaniami, gdzie trzeba samemu wymyślić algorytm, zwłaszcza bazujący na programowaniu dynamicznym. Poprosiłem o pomoc, więc miałem nadzieję, że obejdzie się bez złośliwości…

Do jakiego działu powinienem go zatem wsadzić?

Przecież to nie ja z tego korzystam, więc sam pomyśl. A zapomniałem …

To sobie mogłeś darować…

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.

Programowanie dynamiczne to raczej nie podstawy programowania. Off topic zdecydowanie nie pasuje, bo temat jest o programowaniu i zadaniach ze spoja. Co do nowego działu, nie ja jestem tutaj moderatorem i nie ja powinienem dbać o ich powstanie (może to brzmieć złośliwie, ale taka jest prawda). Ten wątek natomiast może się stać poradnikiem, jeśli nie będzie w nim takich bezsensownych dyskusji, tylko rzeczowe porady (jakich poprzednicy potrafili udzielić).

PS: myślałem nawet nad tym, żeby napisać poradnik dla początkujących, który by wyjaśniał najważniejsze kwestie, które były na starym forum (wczytywanie danych, co robić w przypadku WA itp.), ale jeśli w swojej własnej prośbie o pomoc będę otrzymywał takie czepialskie posty jak Twój, to chyba całkowicie zarzucę ten pomysł.

[tarpauwatratar]

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ć.

[ronie_1982]

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.

[tarpauwatratar]

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.

[ronie_1982]

zadanie Igiełka

[tarpauwatratar]

O testy będzie ciężko…

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

[ronie_1982]

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

[tarpauwatratar]

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.

[camilyed]

@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.