Informatyka UJ forum

r4ku

[link widoczny dla zalogowanych]
czy ktos jeszcze odnosi wrazenie ze jakos duzo tych zadan na 1 IX? :?

kafex

JA :]

Rogal

Zadanie jest ossstre, ale łatwe jak się wpadnie na pomysł :D
Zdecydowanie najciekawsze z tych co były do tej pory.

Jakby ktoś chciał to wrzuciłem binarkę
[link widoczny dla zalogowanych]

Makros

to zdradź nam jeszcze czy te kosmiczne ilości pamięci też są potrzebne...? :)

Rogal

Zdecydowanie nie potrzeba więcej pamięci niż do pozostałych zadań... Nie wiem po co jest tak duży limit, chyba tylko po to, żeby zmylić studentów :D

przem

dobra panowie i panie burza mozgow...
wypisujcie swoje pomysly zastanowimy sie wspolnie trzeba jakos rozkminic to zadanie.
moj pomysl:
z lewego gornego do prawego dolnego rozpatrujemy wszystkie mozliwe drogi, liczymy diamenty i usuwamy je z planszy
droga z powrotem to prosty dynamik (liczymy ile maksymalnie mozemy wziac z pozostalych diamentow), liczymy diamenty
sumujemy diamenty, wstawiamy do jakiejs tablicy i wszystko od nowa (oczywiscie diamenty ktore wzielismy poprzednio musza sie jakos znalezc z powrotem na planszy)
pozniej bierzemy maks po tej naszej tablicy
co wy na to? dlaczego zle dlaczego moze byc dobrze, czekam na jakies uwagi, sugestie itp itd

Rogal

Nie przejdzie bo ścieżek z góry do dołu jest zdecydowanie za dużo. Nie wiem dokładnie ile, ale coś mi mówi, że będzie to liczba w granicach n!

Spectro

@Rogal:
Mnie więcej. Ilość ścieżek jest bezpośrenio powiązana z symbolem Newtona. Dla maksymalnych danych mój kalkulator liczył kilkanaście sekund, po czym wywalił overflowa :P .

mateo

Rogal

No mi ono zajęło prawie 60 linii więc zaliczam je do raczej długich. Ale to pewnie dlatego, że robiłem je na 2 pętlach, a możnaby na 1, tylko trzebaby mocniej pomyśleć nad zapisem :D

luu

Niech ktoś walnie jakąś małą ale dość oczywistą podpowiedź.Nie róbcie ludzie z tego takiej tajemnicy.

Rogal

kg86

no ja wlasnie w ten sposob probowalem sie do tego zabrac :P tylko jak w jednym wymiarze zapamietac jedna sciezke, ktora jest co jak co dwuwymiarowa? :>
btw. dzieki za binarke, na pewno sie przyda :)

luu

Czy wypelniamy tablice kolumnami tj 1.1/ 1.2/ 1.3 ...1.n pozniej 2.1/2.2/ ....n.n ?

Spectro

To była tak ogromniasta podpowiedź, że teraz wszystko jest jasne ;) . Dzięki Rogal :) . Myślałem od 2 dni nad tym zadaniem i nawet idea tego rozwiązania mi przyszła do głowy, ale nie zaprzątała jej zbyt długo, niestety.

Co do kolumn, to ja na nich na pewno robić nie będę :P .

Robson

Czy ktos jest mi w stanie powiedziec dlaczego nie przechodzi na kolumnach?... Bo jakos to ogladam od kazdej strony, od kazdego indeksu i wychodzi ze powinno dzialac :? a tu klops... jedno dziala drugie nie... (wiem ze po kolumnach jest gorzej, trudniej, ale dlaczego jest ANS...? )

Spectro

O tej porze zdecydowanie nie mogę się skupić na indeksach moich tablic, przez co wszystko się krzaczy :? . Heh, odpowienio wszystko poindeksować to jednak jest sztuka ;] .

r4ku

ja jakis glupi jestem, kminie caly czas jak ja ten caly szajs mam trzymac zeby jeden index tablicy przechowywal mi informacje o koncu jednej drogi, skoro do opisu polozenia konca drogi potszebuje 2 wartosci:/ czy moglbym poprosic o jakies naprowadzenie?

Spectro

Rozważasz w jednym kroku wszystkie ścieżki tej samej długości :) . Czas działania mojego algorytmu to O((w+h)*min{w, h}^2) - być może to też będzie jakaś podpowiedź ;) .

mateo

No dobra. Sporo osob jeszcze nei zrobilo tego zadanka a termin juz sie zbliza wiec postanowilem napisac maly tutorial....:)

Po pierwsze jak pewnie wiecie to to zadanko trzeba rozwiazac dynamicznie i ja osobiscie nie widze mozliwosci rozwiazania tego zadania innym sposobem (w rozsadnej zlozonosci). Wszelkie proby zachlanne czy jakies bfsy albo takie rzeczy daja bledne wyniki.
A jesli chodzi o dynamiczne podejscie do zadania to mozna tutaj rozwazyc dwie mozliwosci. 1 Szukamy dynamicznie najpierw jedenj sciezki a potem drugiej (no ale to jak wiadomo jest bledne, polaczenie tego z jakimis algorytmami zachlannymi itp albo dodatkowymi heurystykami tez raczej niczego nie da) 2. Szukamy obydwu sciezek rownoczesnie.

A wiec trzeba teraz sie zastanowic w jaki sposob mozna szukac naszych optymalnych sciezek rownoczesnie. Po pierwsze mozna zauwazyc ze nei ma roznicy z ktorego rogu do ktorego ida nasz sciezki (tzn nie ma roznicy miedzy rogiem lewym gornym i prawym dolnym). Mozemy zatem zalozyc ze zarowno pierwsza jak i druga sciezka ida z rogu gornego lewego do prawego dolnego.
Ja znam 2 sposoby na rozwiazanie tego. Pierwszy sposob jest chyba znacznie latwiejszy do zrozumienia. Drugi teoretcznie dziala tak samo, ale w innej kolejnosci jest obliczana macierz i troche bardziej zamotane sie mi to wydaje. (no ale akurat ja wymyslilem ten drugi sposob:))

1. Dynamika po dlugosciach sciezek.
Musimy znalezc 2 sciezki o dlugosci w + h - 2 kazda takie ze suma diamentow na tych dwoch sciezkach jest mozliwie najwieksza.
Robimy dynamike po dlugosciach sciezek od 1 do w - h - 2 i w 'k'-tym kroku rozpatrujemy wszystkie mozliwe pary sciezek dlugosci 'k' kazda (a raczej nie tyle wszystkie pary sciezek co pary koncowych elementow tych sciezek). Kazda sciezka dlugosci 'k' konczy sie w pewnym punkcie o wspolrzednych (x, k - x + 2). Czyli latwo zauwazyc ze pierwsza wspolrzedna ostatniego elementu pierwszej sciezki determinuje druga wspolrzedna i podobnie dla drugiej sciezki. Wiec w kazdym kroku naszego algorytmu dynamicznego musimy zrobic podwojna petle po wszystkich mozliwych x1 dla pierwszej sciezki i po wszystkich mozliwych x2 dla drugiej sciezki.

Przykladowo: jestesmy w 7-dmym kroku naszego algorytmu (rozpatrujemy sciezki dlugosci 7) mamy teraz do rozpatrzenia wszystkie pary sciezek, ktorych dlugosc jest rowna 7. Jedna z takich par jest zaznaczona na rysunku ponizej:

Niebieskie kropki oznaczaja koncowe elementy tych sciezek. Dokladna trasa tych sciezek nas zupelnie nie interesuje, gdyz nie ma znacznie ktoredy one przebiegaja. Mamy obliczyc jedynie maxymalna ilosc diamentow jaka mozemy zebrac gdy optymalne sciezki beda sie konczyly wlasnie w tych miejscach. No i teraz pytanie: -> skoro rozpatrywane sciezki koncza sie wlasnie w tych miejscach oznaczonych kropkami to gdzie moga sie znajdywac przedostatnie elementy tych sciezek? Sa 4 mozliwe przypadki. Do kazdego z koncowych elementow moglismy dojsc albo z gory albo z lewej strony (tak jak pokazuja czerwone strzalki). A poniewaz kazda mozliwa para elementow przedostatnich reprezentuje pewna pare sciezek dlugosci 'k'-1 to dla kazdej takiej pary mamy juz obliczona maxymalna ilosc diamentow jaka mozemy zebrac wybierajac optymalne sciezki konczace sie w tych wlasnie elementach. Wybieramy zatem maxymalna wartosc z tych 4 mozliwych wartosci dla kazdej pary elementow 'przedostatnich'. No i do tej wartosci musimy dodac ewentyalne diamenty ktore znajduja sie w aktualnie rozpatrywanych elementach 'ostatnich' (czyli w niebieskich kropkach). Trzeba oczywiscie uwazac zeby nie policzyc 2 razy diamentu gdy akurat rozpatrujemy przypadek gdy koncowe elementy znajduja sie w tym samym miejscu oraz w tym miejscu znajduje sie akurat diement. A teraz pytanie: skad mamy gwarancje, ze nie znajac przebiegu naszych sciezek mamy pewnosc ze napewno nie liczmy zadnego diamentu dwukrotnie na tych sciezkach (bo bo przeciez moze byc tak ze optymalne dwie sciezki, konczace sie w aktualnie rozpatrywanej parze koncowych miejsc, przecinaja sie w polu z diamentem)?. Ano wlasnie stad ze dowolna sciezka prowadzaca do pola (x, y) ma zawsze dlugosc x + y - 2. Zatem jesli optymalne dwie sciezki przecinaja sie w miejscu z diamentem, to fragmenty (do miejsca tego przeciecia) tych sciezek sa rownej dlugosci i sa optymalna para sciezek konczacych sie w tym wlasnie miejscu z diamentem (gdyby nie byly optymalne to wybralibysmy inna lepsza pare konczaca sie w tym miejscu z diamentem i tym samym przeczyloby to temu ze ilosc diamentow dla naszej wyjsciowej pary jest policzona optymalnie). Zostaly one policzone zgodnie z naszym algorytmem a zatem diament na koncowym polu zostal policzony raz (gdyz to jest ten przypadek o ktorym pisalem wyzej, ze wtedy trzeba ten diament liczyc raz) i to dowodzi tego ze zaden diament nie ma prawa zostac policzony wiecej niz raz w zadnej parze sciezek.

No wiec defakto tak wyglada cala idea algorytmu. Sama implementacja raczej trudna nie jest. mozna sobie ulatwic dodajac zerowe: wiersz i kolumne. Pozatym jesli chodzi o sam wyglad tablicy mozna zrobic 3-wymiarowa tablice gdzie pierwszy wymiar oznacza dlugosc sciezki,drugi oznacza wspolrzedna 'x' pierwszej sciezki, a trzeci wspolrzedna 'x' drugiej sciezki. Takie cos jednoznacznie okresla kazda pare sciezek (elementow 'koncowych'). No ale jak latwo sie przekonac nie potrzebujemy pierwszego wymiaru tej tablicy bo korzystamy zawsze jedynie z wartosci obliczonych dla sciezek o 1 krotszych. Szukany wynik znajdziemy w jedynym elemencie tablicy dla sciezki dlugosci w + h - 2;
takze tak wyglada pierwszy algorytm.

Jesli chodzi o zlozonosc czasowa to tak na pierwszy rzut oka jest to O((w+h)*min{w,h}^2)

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Heh, przepchnalem wlasnie i wchodze na forum z zamiarem spisania 'opisu przejscia'... a tutaj taki prezencik od Matea :D

Mateo - rispekt, ze Ci sie chcialo tyle napisac.

Rogal - dzieki za binarke do testow, ale sie krzaczy ;)) Gdzie, to lepiej na priva Ci wysle, bo by Ci jeszcze TCS mogl jakis test dowalic i cofnac OKeya ;)
(Chyba, ze to jakas wina wczytywania lub mojego zlego wygenerowania pliku wejsciowego)

Anyway, [link widoczny dla zalogowanych] lezy binarka do generowania testow - jak zwykle instrukcja po wlaczeniu bez parametrow. Of koz nie odpowiadam za nia, moze sie krzaczyc - mi raczej dobrze dzialala. (Mowie, bo niektorzy mi dawali info, ze ktorys tam moj generator cos zle zliczal - nie wgralem wtedy ostatniej wersji na serwer, chyba pozniej ja update'nalem)

Spectro

Faktycznie, robiłem pierwszym sposobem, ale:

Rogal

r4ku

@mateo: respekcik

rozpisalem sobie wczoraj algorytm po dlugosci sciezek ale nie bylem pewien jego poprawnosci w moim wydaniu, okazalo sie jednak ze jest on izomorficzny z pierwsza metoda wiec biore sie za kodzenie :D

mateo