Jan 2016
1 / 14
Jan 2016
Jul 2023
tarpauwatratar
Jan '16

http://pl.spoj.com/problems/SPEEDM/51

Tak się bawię z tym zadankiem i bawię... i mam kilka problemów.

Próbowałem algorytmu zachłannego - z łatwych wyniosłem, że qsort załatwia wszystko. Ale to są średnie i dostaję WA.

Intuicja podpowiada mi, że problem jest do rozwiązania programowaniem dynamicznym. Przeszukiwanie internetów zasugerowało mi, że może to nawet być problem plecakowy: jeżeli policzę sumę wszystkich liczb (S) a następnie sumę podzbioru tych liczb (x) najbliższą połowy sumy wszystkich liczb (x = około S/2), to odemowanie da mi minimum.

Moje pytania:

  1. Czy intuicja nie zawodzi mnie?
  2. Jeżeli nie zawodzi, to... jak nauczyć się programowania dynamicznego? Dotychczas stosowałem (raczej nieświadomie) programowanie dynamiczne do rozwalania rekurencji (gdy zadowalało mnie O(n)) typu silnia albo liczby Fibonacciego. Nie wydaje mi się, aby zadanie średnie wymagało ode mnie schematów na poziomie dzikiego konkursu algorytmicznego i problem zapewne jest trywialny. Niestety z przyczyn takich a nie innych nikt w tajniki programowania dynamicznego bezpośrednio nie może mnie wprowadzić. Szczególnie interesuje mnie, czy są jakieś schematy postępowania, gdy problem wydaje się być do rozwiązania programowaniem dynamicznym oraz gdzie takie schematy znaleźć. Przez schemat rozumiem uniwersalne podejście, które pozwala rowiązać problem bądź zbliżyć się do tego rozwiązania - coś jak pierwiastniki dla równania kwadratowego.

Z góry dziękuję za pomoc i przepraszam, jeżeli coś pokićkałem - jestem adeptem a nie mistrzem aglorytmów.

  • created

    Jan '16

  • last reply

    Jul '23
  • 13

    replies

  • 2.1k

    views

  • 6

    users

  • 2

    likes

  • 4

    links

narbej
Jan '16
1

Moja intuicja nie jest intuicją kobiecą, więc pewnie mnie często [zawsze] zawodzi. Moja intuicja podpowaiada mi, że to zadanie nie ma nic wspólnego z pakowaniem plecaka/ów i walizek na wakacje. Moja intuicja mówi, że sortowanie nie tylko jest tu niepotrzebne ale nawet niewskazane.

AD 1
Chyba jednak częściowo zwodzi, tzn każdy krok zbliża nas do znalezienia rozwiązania ale czy to jest typowe zadanie na programowanie dynamiczne?

AD 2
1. Ksiązki.
2. Nauczyciel
3. Guru
4. Przyjaciel.
5. Internet?
5 a) Wpisz w googla: jak nauczyć się .....
i znajdziesz np : http://www.wykop.pl/ramka/2188870/mirek-uczy-z-czego-i-jak-uczyc-sie-programowania-w-c/57 <-- ale jest to wpis z przed ponad roku. [jest już c++14]

PS
Jednak jest tam i o C++14 i fajne komentarze. W każdym razie w komentarzach są zastrzeżenia do pewnego videokursu online. Ten wpis dopiero co znalazłem i jeszcze go dokładnie nie "przetrawiłem".

tarpauwatratar
Jan '16

AD 1, 2
Dziękuję za odpowiedź. Nie wiem, czy to typowe zadanie jest na programowanie dynamiczne. Brakuje mi tak zwanej wprawy zadaniowej. Książki to raczej teoria, ale może poznanie od strony teoretycznej prostych problemów w sam raz na programowanie dynamiczne rzeczywiście mnie olśni. Niestety w tej chwili chyba lepiej pozmywać naczynia i nauczyć się na egzamin z pędu i termy technicznej smile

AD PS
Trudno nie mieć zastrzeżeń do pewnego videokursu online. O ile początki były na prawdę świetne (uczyły podstaw i pokazywały, że każdy - jeśli chce - może nauczyć się programować) o tyle wszystko dalej okazało się być dość infantylne a miejscami nawet błędne - aktualnie jestem na etapie tworzenia własnej strony internetowej i nie wyobrażam sobie robić ją według pomysłów podawanych w pewnym videokursie online. Leży także matematyka - algorytmy wołają o pomstę do nieba i są przedstawione bardziej jako zbędna ciekawostka dotycząca sortowania a nie coś ważnego. Zastępują je numerologiczne rozważania o klątwach ciążacych na różnego rodzaju liczbach...

Zakładam, że mówimy o tym samym kursie i wiadomość jest zrozumiała.

Pozdrawiam, dziękuję raz jeszcze i chwilowo żegnam SPOJa. Biorę się za te naczynia, a potem kto wie... może rozwiążę to zadanie smile

narbej
Jan '16

Możliwe, że moja intuicja jest zwodna, dawno robiłem to zadanie i możliwe, że jednak to jest typowe DP [programowanie dynamiczne].

3 months later
sebastian_mroz
May '16

Witajcie, zrobiłem to zadanie używając algorytmu do problemu plecakowego. Po optymalizacji udało mi się zejść do czasu 0.07. Tutaj rodzi się moje pytanie... Czy zejście do 0.00 to kwestia innego podejścia( algorytmu? ) czy optymalizacji ? Byłbym bardzo wdzięczny za jakiekolwiek wskazówki jak można zmniejszyć czas wykonania :wink:

narbej
May '16

A co jest plecakiem, jaką ma pojemność i co jak szybko pakujesz?

PS
Zrobiłem 0.00 i zastanawiałem się czy użyłem fast i/o? I nie, nie użyłem. Dodatkowo, teraz wyłączyłem ios::sync_with_stdio(0) [zakomentowałem] i uzyskałem czas 0.01 - czyli w granicach błędu pomiarowego identyczny czas.

sebastian_mroz
May '16

Plecakiem są kolejne sumy do uzyskania ( od 1 do sumy_wszystkich/2 ). Wychodzi mi złożoność O( n * suma_wszystkich/2 ) .

narbej
May '16

Więc plecak się u Ciebie rozciąga? Chyba, że to z twojej strony przejęzyczenie. Plecakiem, [jego pojemnością] wg mnie jest, sumy_wszystkich/2, a pakowanymi elementami - pomierzone prędkości.

Twoja złożoność, jak by nie liczyć, dla danych z zadania sumy_wszystkich/2 przeważnie jest większa od n, chyba, że będą same zerowe prędkości, więc masz O(n^2).

Opytymalizacje:
1. Nie pakuj od 1 do suma/2, tylko od tyłu od suma/2 do 1
2. Nie pakuj od suma/2 tylko od suma/2 - ai do 1
3. Wstaw wartownika na 0 i pakuj od pkt 2 do pierwszego wystąpienia [zapakowanego już elementu lub sumy elementów]
Zrobiłem tak jak wyżej i mam AC 0.00. Zrobiłem [wymyśliłem] to bardziej intuicyjnie, chociaż pakowanie od tyłu [ale bez tak głębokich :wink: optymalizacji] jest też we wzorcówce do tego zadania. Wzorcówką, wg mnie, raczej nie uzyska się czasu 0.00.

5 years later
niedzwiadek28
May '22

Powie mi ktoś, gdzie tutaj jest błąd?

1 year later
yorker
Jul '23

od kilku dni próbuję jakoś rozgryźć ten problem, ale nie wiem czemu ten kod zwraca że błędna odpowiedź, mimo że we wszystkich testach wychodzi poprawnie:

quenthui
Jul '23

Hej, zacząłbym od poprawienia sposobu tworzenia tablicy

int lpowt,liczbad= 0;
scanf("%d",&lpowt);
for(int i = 0; i < lpowt; i++){
    scanf("%d", &liczbad);
int  min = 0,max = 0;
int tab[liczbad]; <- błąd
int ltab[liczbad]; <- błąd

Tworzysz statyczną tablicę (której rozmiar jest ustalany na etapie kompilacji) ze zmiennej, której zawartość znana jest dopiero w czasie działania programu. Dla małych wartości to jakoś działa, ale dla większych już nie musi.

Dodatkowo poczytaj o funkcji qsort zamiast pisać samemu sortowanie bąbelkowe :smiley:

yorker
Jul '23

dobra, po tych poprawkach mi zaakceptowało :sunglasses:
dzięki

quenthui
Jul '23

Świetnie, to jeszcze prośba, żebyś usunął kod z wcześniejszego postu