Informatyka UJ forum

Pandunia · Gość

[deleted]

exeman

Wydaje mi sie, ze w obu zadaniach wystarczy zapuscic dijkstre.

oinopion

Nie czytałem za dokładnie, ale w Q nie lepszy będzie B-F?

Spectro

W Q będziemy mieli wagi ujemne, więc Dijkstra nie jest najlepszym pomysłem ;] . Ale to lepiej napisać było w drugim temacie.

A w P to wiadomo, że chodzi o jakąś wersję Dijkstry. Sztuką jest natomiast wymyśleć, na jakiej zasadzie ta wersja ma działać ;] .

Robson

Hmmmm wydaje mi sie ze w P robimy normalną dijkstrę, tylko po kazdym kroku, po obliczeniu tej najkrótszej drogi prowadzącej z 1 do v przez u trzeba do tej drogi dodać czas potrzebny na wyczekanie momentu bezpieczenstwa drogi... i dopiero takie wartosci wrzucić na kopiec z powrotem...

Makros

Moje pierwsze skojarzenie to zrobić to tak jak przychodnie, ale z Dijkstrą...

dzendras

Wygląda na to, że jest to ostatnie zadanie z serii nie bonusowych. Bo ostateczny termin oddania zadań (żółte kartki się do nich nie przydadzą) mija 12 czerwca, czyli w dniu ropoczęciem sesji. Także ostatnie zadanka czas przepchnąć...

Pawel Str.

P to ewidentnie Dijkstra, tak, jak pisał Robson. W zadaniu jest mały haczyk, na który się wiele osób nacięło - otóż -1 też jest liczbą całkowitą, więc pierwszy "bezpieczny okres" może się zaczynać przed momentem wyjazdu.

Swoją drogą, u nas to zadanie miało *, ale to może przez limit pamięci.

W Q wydaje mi się, że BF, o ile może wyjść krawędź ujemna (a chyba może).

Fidel

dzendras

A to właśnie Dr Ślusarek uspokajał nas na wykładzie przed Wielkanocą, gdy nasze nastroje były nienajlepsze, żebyśmy byli spokojni, zadań nie będzie tak dużo i będziemy mieli ten miesiąc przed sesją bez zadań. Ech :/

mateo

Co do zadanka P to ono jest rzeczywiscie proste... zwykla dijkstra lekko zmodyfikowana. Tylko ze sporo do skodowania no ale samo zadanko latwe.... No a jesli chodzi o Q no to rzeczywiscie sie tutaj bardzo narzuca rozwiazanie tego Bellmanem-Fordem bo bedziemy miec krawedzie z ujemnymi wagami.... no ale jest taki maly zonk, ze zwykly B-F napewno nie daje dobrego wyniku w tym zadaniu. Tzn przez zwykly mam na mysli taki, ktory traktuje po prostu dlugosc sciezki jako zmiane energi pomiedzy miastem poczatkowym a tym do ktorego dochodzi sciezka.

Pawel Str.

Co do zadanka P, to pozwolę sobie tylko pokazać to:

mateo

To ze ty dostales na tym zadaniu 18 gwiazdek to nie znaczy ze jest ono trudne :P

Jedyny problem jaki ja tutaj widze to to ze trzeba to napisac w pascalu, a nie w c++. Bo tak to bym sobie przerobil kod programu do zadanka z zeszlorocznych MWPZ -> tam bylo podobne zadanko (tylko nieco trudniejsze niz Baza Babilon)
[link widoczny dla zalogowanych]

Skrobocik

Makros

Ma ktoś jakieś ciekawe testy do tego zadania??

Pawel Str.

Wam powinno być łatwiej, macie chyba normalniejszy limit pamięci. U nas de facto to było problemem. No i kwestia i==-1, którą ręcznie odsiewałem (odsiewaliśmy?) wbrew treści zadania.

Jeszcze raz potwierdzam, podany tu pomysł, żeby robić "Dijkstrę z czekaniem" jest dobry.

Robson

P to kolejne zadanie z cyklu Kobyła. Algorytm Dijkstry mimo ze bardzo porsty wymaga jednak uzycia specjalnego kopca, z odnosnikami, do tego dochodza jeszcze sprawy z tym czekaniem na mozliwośc wyjazdu, co tez komplikuje sprawe.

Jak na razie wymysliłem cos takiego:
1. Zainicjuj wszytsko tak jak do DIJkstry
2. Wybierz z tablicy D najmniejszą wartośc, powiedzmy ze jest to D[u]. oznacz ja jako zrobiona.
3. Dla kazdego v-nastepnika u "poczekaj" na mozliwośc wyjazdu (sprowadza sie do znalezeinia takiej najmniejszej wartosci czasczekania ze D[u]+czasczekania nalezy do [a+it,a+ti+l) dla pewnego i), po czym sprawdz czy przejazd (D[u]+dlugosc(u->v)+czasczekania) skraca droge w D[v].
4. Powtarzaj kroki 2-4 az wszystkie drogi nie zostaną oznaczone jako zrobione.
5. Sprawdz czy D[n]<+NIESKONCZONOSC, jesli tak to wypisz D[n], wpp NIE

trzeba jeszcze rozpatrzyc pewne specjalne przypadki np. kiedy jakas droga jest typu (a=const,t=0,l=const) czyli kiedy droga jest bezpieczna tylko na początku w czasie od a do a+l ... przynajmniej tak mi wynika z zadania ze tak bedzie to działać...

Moze ktos potwierdzić moje wypociny? ;)

Pawel Str.

Potwierdzam 1-5. Przy czym krok 2 robi się już z kopca.
Natomiast t==0 wtedy i tylko wtedy, gdy a=0 i l=0, zatem droga jest stale bezpieczna. Nie istnieją drogi bezpieczne tylko na początku (zauważ, że w treści jest a<t, zatem t=0 => a=0, podobnie wtedy l=0);

Każda droga jest więc okresowo bezpieczna lub stale bezpieczna.

Makros

P właśnie poszło.... Niestety z jedną gwiazdką z powodu mojej głupoty...
Cóż moge powiedzieć zwracajcie uwage czy zmienne macie dobrej wielkości... (ja za bardzo przyzwyczaiłem się do smallintow :) )...

A co do reszty to ak jak napisał Robson z tym, że w pkt. 3 to całe "poczekaj na mozliwość wyjazdu"... sprowadza się do "wylicz kiedy możesz jechać"... troche dodawania mnożenia i modulo...

jakby ktoś chciał to moge zapodać binarke i banalny generator (generuje tylko max testy tzn. jeden zestaw na 50000 wierzcholkow i 1000000 dróg... bo poprawność można sprawdzać na malutkich testach... a to do Runtimów :) )
-----
edit: jak bede miał jutro czas to może zrobie jakiś generator...
edit: binarka: [link widoczny dla zalogowanych]

kap00ch

uffff.........poszlo....nic mnie ostatnio tak jak to nie zmordowalo...ale jakos poszlo...ogolem to hmmm...to co z rad potrzebne to jest juz wyzej...w zasadzie ciezko inny algorytm wymyslec:P

polecam przemyslec liczenie czasu oczekiwania...bo moje okazalo sie porazka i dzialalo na wszystkich moich examplach:D na szczescie makros wydatnie poratowal...ale w sumie gwozdziem do trumny okazal sie typowy blad paszczalowy...zmienilem tablice z 50000 na 50001 co nie mialo wiekszego uzasadnienia i poszlo :O

aaa i jak ktos nie wie RC8 to blad podzialu przez 0:P taka nauczke mam:D

no nic pora spac:>

mateo

No i po raz kolejny upewnilem sie w przekonaniu jak popierdolonym jezykiem jest pascal. Szczerze mowiac nie wiem wogole po co jest w nim zrobiona funkcja sizeof ktora tak naprawde wielkiego chooja mowi o tym ile dany obiekt zajmuje w pamieci (o tym ze niewiadomo czemu dodanie wskaznika jako nowego elementu danego obiektu powoduje czasem wzrost zuzycia pamieci o 8 bajtow to juz wspominal nie bede...). W kazdym razie liczenie zuzycia pamieci przy uzyciu funkcji sizeof sie raczej mija z celem, bo obiekty tworzone na stercie zajmuja i tak w pizdu wiecej niz powinny... nie mam zielonego pojecia czemu.

W kazdym razie zeby nie bylo ze moja subietywna opinie wzialem z kosmosu to dla porownania identyczny program do zadania Baza Babilon tyle, ze napisany w c++, ktory rozni sie od tego w pascalu tym ze zamiast listy jednokierunkowej ma liste dwukierunkowa (dla nastepnikow) i ze zamiast uzywac indexow wierzcholkow (zajmujacych 2 bajty) uzywa wskaznikow do wierzcholkow (zajmujacych 4 bajty) zuzywa w sumie okolo 8 MB pamieci mniej na maxymalnych danych i jest to dokladnie tyle co mozna sobei policzyc recznie.

Ale dobrze ze juz sie konczy ta meka z pascalem bo moze czlowieka szlag trafic jak sie okazuje, ze jedynym bledem w programie jest to ze jest on napisany w tym zjeba.... jezyku.

kap00ch

hehe...normalka ;] to tak jak mi 6bajtowy packed record allokowal na 16bajtow ;p

insane

nie no to jest parodia z tym fpc 4 bombki przez to ze zabraklo mi jakze waznej linii w moim kodzie o ktorej pamieta kazdy szanujacy sie programista a mianowicie :
edge^.v := edge^.v

no comment
na miejscu kogos kto ma poprawke przez tego typu bledy nie czekalbym ani chwili tylko wzial taboret i zaczal lac sie po glowie

niech zyje florian klaempfl ;]

Rogal

@Insane:
A w jakich miejscach trzeba takie linijki wstawiać? To jest jakoś określone, czy tak na chybił trafił się wstawia wszędzie gdzie się da i patrzy czy działa? :lol:

kap00ch

ogolem wsadzaj co druga linijke i jak dziala to wykomentowywuj po kolei optymalizujac kod :DDDDDDDDDD <algorytm optymalizacyjno uruchomieniowy:>>