Ĺadny brzuch
Robie sobie dalej te zad z OIGa (z tym poprzednim dalej nie wiem co jest zle, moze na mainie maja blad w testach...)... Obecnie zająłem się TYM zadankiem. Pomyslalem dłuższą chwilę nad nim i wymyśliłem że moj algorytm bedzie nastepujący: znajduję miasto, ktore ma za duzo towaru. Następnie ono rozwozi nadmiar do najblizszych miast (przy pomocy BFS, tu także od razu obliczam koszt). Jednak otrzymuję za to zad tylko 6 pkt, głównie dlatego, co jest dla mnie zaskoczeniem, mój algorytm w wiekszosci przypadków nie daje nawet poprawnych wyników. O tym że jest za wolny to nawet nie mowie... W związku z tym uznałem patrząc na testy (zawierające np. po 500000 miast), że robienie tego grafami nie ma sensu, gdyż nawet jak jakimś cudem bede miał poprawny algorytm, to sie on wysypie czasowo. W związku z tym mam pytanie: jak inaczej (czyt. poprawnie i optymalnie) rozwiązać to zadanie? Bo ja juz innego pomyslu (narazie) nie mam...
Na OI są zadania z rozwiązaniami. Może tam zajrzysz? ;]
Edit: Nah. Przecież to jasne, że z tegorocznych rozwiązań nie ma jeszcze. Ignorować mój post ^^
Użytkownik Lupinek edytował ten post 19 kwiecień 2008, 21:24
poczytaj o zagadnieniach transportowych - mialem cos takiego na studiach, lecz nie pisalem algorytmu w C/C++ tylko w Matlabie (tu dziala to bardzo szybko)
choc 500 000 miast to juz moze byc problem :/
Użytkownik fernandez edytował ten post 19 kwiecień 2008, 22:39
O ile pamiętam, były osoby, które dostały za to zadanie po 100pkt. i było ich całkiem sporo.
Ja rozwiązałem to zadanie na MAINie na 100 pkt.
Mój algorytm był taki: najpierw sortuje wszystkie miasta od najmniejszej liczby towarów do największej, najlepiej użyć do tego celu funkcji sort() bo nie trzeba się trudzić przy implementowaniu QuickSort, a poza tym jest chyba wydajniejsza. Potem sortuje połączenia między miastami. Następnie zapuszczam taką pętle: while(pierwsze miasto w posortowanej tablicy miast != ostatnie miasto w posortowanej tablicy miast) i wewnątrz pętli przy pomocy wyszukiwania binarnego (bo połączenia wcześniej posortowałem), wyszukuje wszystkie połączenia miasta, które w tej chwili jest na pierwszym miejscu w tablicy miast, czyli ma najmniej tego towaru (czy czegoś tam). Potem w jak najszybszy sposób (nie będę już pisał szczegółowo o tym sposobie) "aktualizuje" tablice tak, żeby miasta były posortowane. No i jak się pętla skończy wykonywać, to będziemy mieli we wszystkich miastach odpowiednią liczbę towarów.
EDIT: Oczywiście wewnątrz tamtej pętli najpierw temu pierwszemu miastu daje tyle, ile potrzebuje (o ile jest to możliwe) i odejmuje temu od którego zabiera ten towar, a dopiero później "aktualizuje" miasta.
Użytkownik Capellini edytował ten post 20 kwiecień 2008, 17:59
Hmm... Móglbys zapodać ten kod? Bo ja chyba czegos nie rozumiem albo nadinterpretowuje...
Ja niestety nie mogę, bo w tym momencie jestem na komputerze, na którym nie mam kodu źródłowego tego programu, ale tu masz jeszcze jedno rozwiązanie tego zadania: http://phpfi.com/289955
Thx, a tak btw to ono w dwóch przypadkach pamieciowo nie wydala :P
Co moge jeszcze zrobic zeby zmiescic sie w pamieci? ... bo zastosowalem nawet bitseta dla booli, ale nawet to nie pomoglo... dalej 2 przypadki przeginaja z pamiecia :/
EDIT: No jasne, przecie przy DFSie stos sie przepelnia, wiec to zla droga do tego zad xD Obrałem inna i ta sie okazała zwycięska :D Po wielu godzinach myslenia i klepania mam te 100 :D
Użytkownik Kamil Wajda edytował ten post 21 kwiecień 2008, 20:34
Po wielu godzinach myslenia i klepania mam te 100 biggrin.gif
Gratuluję :-)
Użytkownik Capellini edytował ten post 22 kwiecień 2008, 10:37
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
Na OI są zadania z rozwiązaniami. Może tam zajrzysz? ;]
Edit: Nah. Przecież to jasne, że z tegorocznych rozwiązań nie ma jeszcze. Ignorować mój post ^^
Użytkownik Lupinek edytował ten post 19 kwiecień 2008, 21:24
poczytaj o zagadnieniach transportowych - mialem cos takiego na studiach, lecz nie pisalem algorytmu w C/C++ tylko w Matlabie (tu dziala to bardzo szybko)
choc 500 000 miast to juz moze byc problem :/
Użytkownik fernandez edytował ten post 19 kwiecień 2008, 22:39
O ile pamiętam, były osoby, które dostały za to zadanie po 100pkt. i było ich całkiem sporo.
Ja rozwiązałem to zadanie na MAINie na 100 pkt.
Mój algorytm był taki: najpierw sortuje wszystkie miasta od najmniejszej liczby towarów do największej, najlepiej użyć do tego celu funkcji sort() bo nie trzeba się trudzić przy implementowaniu QuickSort, a poza tym jest chyba wydajniejsza. Potem sortuje połączenia między miastami. Następnie zapuszczam taką pętle: while(pierwsze miasto w posortowanej tablicy miast != ostatnie miasto w posortowanej tablicy miast) i wewnątrz pętli przy pomocy wyszukiwania binarnego (bo połączenia wcześniej posortowałem), wyszukuje wszystkie połączenia miasta, które w tej chwili jest na pierwszym miejscu w tablicy miast, czyli ma najmniej tego towaru (czy czegoś tam). Potem w jak najszybszy sposób (nie będę już pisał szczegółowo o tym sposobie) "aktualizuje" tablice tak, żeby miasta były posortowane. No i jak się pętla skończy wykonywać, to będziemy mieli we wszystkich miastach odpowiednią liczbę towarów.
EDIT: Oczywiście wewnątrz tamtej pętli najpierw temu pierwszemu miastu daje tyle, ile potrzebuje (o ile jest to możliwe) i odejmuje temu od którego zabiera ten towar, a dopiero później "aktualizuje" miasta.
Użytkownik Capellini edytował ten post 20 kwiecień 2008, 17:59
Hmm... Móglbys zapodać ten kod? Bo ja chyba czegos nie rozumiem albo nadinterpretowuje...
Ja niestety nie mogę, bo w tym momencie jestem na komputerze, na którym nie mam kodu źródłowego tego programu, ale tu masz jeszcze jedno rozwiązanie tego zadania: http://phpfi.com/289955
Thx, a tak btw to ono w dwóch przypadkach pamieciowo nie wydala :P
Co moge jeszcze zrobic zeby zmiescic sie w pamieci? ... bo zastosowalem nawet bitseta dla booli, ale nawet to nie pomoglo... dalej 2 przypadki przeginaja z pamiecia :/
EDIT: No jasne, przecie przy DFSie stos sie przepelnia, wiec to zla droga do tego zad xD Obrałem inna i ta sie okazała zwycięska :D Po wielu godzinach myslenia i klepania mam te 100 :D
Użytkownik Kamil Wajda edytował ten post 21 kwiecień 2008, 20:34
Po wielu godzinach myslenia i klepania mam te 100 biggrin.gif
Gratuluję :-)
Użytkownik Capellini edytował ten post 22 kwiecień 2008, 10:37