Informatyka UJ forum

Pandunia · Gość

[deleted]

Spectro

Skrobocik

Też mają czegoś dwie sztuki, więc mogą :wink: :twisted:

PS

Rogal

Robson

Spectro

Aha, dość istotna uwaga: treść zadania nie wyklucza cyklów o wartości ujemnej, ale testów z takim przypadkiem na athinie nie ma. Doświadczalnie sprawdzone przez Maze'a ;) .

Jakby coś to, zgodnie z przewidywaniami, zadanie idziem Bellmanem-Fordem :) .

mateo

no wlasnei mnie gnebilo troche to ze tutaj sa te cykle z ujemnymi wagami (tzn ze moga byc) dlatego wlasnie ten bellman-ford moglby sie sypac. No ale tak czy siak to ja i tak dalej jeszcze nie widze jak tutaj podpiac bellmana-forda zeby to dzialalo.

Makros

Nam na ćwiczeniach ćwiczeniowiec powiedział że w sumie wystarczy dać czystego BF.... jeszcze się nad tym nie zastanawiałem... ale jak wtedy tak "prawił" to wydawało się, że ma racje... Ale ręki nie dam sobie uciąć... :P

Robson

BF jak najbardziej przechodzi. Dowód przez athine -> ;)

insane

witam ;]
chcialbym podzielic sie z wami jakze cennym spostrzezeniem odnosnie tego zadania!!! Otoz ;] nie probujcie nic optymalizowac w samej procedurze bellmana-forda ;] ja probowalem mianowicie zejsc z O(n*m) do czasu liniowego niechcacy zapominajac napisac zewnetrznej petli od 1 do n-1 ;]]]]]]]]]]]]] Musze przyznac ze alg dzialal znaczaco szybciej ;] Pojawily sie jednak niewielkie usterki w prawidlowosci wynikow jakie zwracal ;] na prawde byly one minimalne :D:D:D:::D:D:D::D ale wstretna athina ma wlasnie takie testy ktore to wykryly i zaowocowalo to trzema BoMpkaMI ;]]]]]]]]

nie no ;] niewiele osob potrafi dokonac tego co udalo sie mi;] wszytko co bylo do napisanai przeze mnie bylo dobrze ;] jedynie to co przepisalem z wykladu mialo blad ;] huh ;] zaHcik branzowy taki ;]] :D:D:D:

hansu

Ins - avatar MIAZDZY!!!!!!!!!!!! Dobre 10 minut tarzalem sie po ziemi jak go zobaczylem. Good point :) btw wypada zebym sobie jakas opone dodal do mojego :)

insane

bez dwoch zdan hans bez dwoch ;]]]]]]]]]]]]]]] myslalem o jakims motywie z przymusem chodzenia (moze forrest gump? ) ;D:D:D::D ale nic do glowy mi nie przyszlo ;]]]]]]]]]

Rogal

@mateo: Nie ma bata, żeby był cykl na którym zyskujesz, tj. cykl o ujemnej wadze. Z tej prostej przyczyny, że jeśli zaczynasz z miasta o wysokości powiedzmy n to przechodząc po tym cyklu skończysz w tym samym mieście, czyli też na wysokości n. Łatwo zauważyć, że to ile możesz "zarobić" na zmianach wysokości jest zawsze ograniczone od góry przez ilość ścieżekw cyklu. Tj. jeśli cykl ma długość 100 to nie ważne jakie by nie były zmiany wysokości nie "zarobisz" na zmianach wysokości więcej niż 99. To wynika z własności działania div. A ponieważ ścieżki mają długość całkowitą dodatnią to przejechanie ich kosztuje cię co najmniej 100. Prosty wniosek, że na takim cyklu nie możesz nawet wyjść na 0, najlepszy możliwy cykl to taki na którym tracisz "tylko" 1.

Makros

Heh... :) Dwie gwiazdki bo zrobiłem dokładnie ten sam błąd co Insane :)... I to znając już jego posta :P... No cóż... późno było.... :) Ale potwierdzić moge jedno... po wynikach trudno sie połapać, że to właśnie oto chodzi... :)

mateo

kg86

a jesli zdarzy sie tak, ze jest jedna droga, ktora caly czas prowadzi z gorki i w ten sposob zuzycie energii wychodzi ujemne? to co nalezy wypisac?
a co nalezy wypisac jesli poza taka droga sa inne, ktore maja nieujemne zuzycie energii? najmniejsza wartosc z nieujemnych? :)
btw. ma ktos testy do tego zadania? :)

kap00ch

jak jest ujemna wypisz 0 ;]

kg86

po walce z RD8 zadanko przeszlo :) mialem kilka smiesznie prostych bledow, typu nie nilowalem wskaznika, uzylem integera zamiast longinta w liczniku petli, itp. generalnie zadanko proste na ok. 2h [mi zajelo 4 :P]

btw. dodalem mala optymalizacje - wywolywalem algorytm nie dla wszystkich krawedzi, tylko dla krawedzi odchodzacych od 'kandydatow', ktorych z kolei wyznaczalem w poprzedniej iteracji :) gdzie 'kandydatem' jest miasto, w ktorym w poprzedniej iteracji nastapila zmiana dlugosci sciezki :) a pierwsza iteracja byla wywolana tylko dla jednego...

jagm

Taka mała uwaga. Pamiętajcie, że jeśli wynik na wyjście wychodzi ujemny, to trzeba wypisać 0! Niektórzy zapominają i potem się męczą szukając błędów, zamiast sobie zadanie P przerabiać ;)

Spectro

Jeżeli ktoś nie wyifował przypadków dodawania nieskończnoności, to może mieć pewien problem z przekroczeniem zakresu longinta przy za dużej stałej infinity ;] . Sam się na tym przejechałem :P .

Madras

Ja też ;].
BTW, powiedzcie mi, jaki jest przypadek, gdy program, który ma iterację w głównej pętli ma do liczby dróg, zamiast liczby miast, poda złą odpowiedź? Bo miałem ten błąd, ale myślę, myślę, i wymyśleć nie mogę ;].

mateo

Madras

Masz rację ;]. Tzn. nie szła od 2, ale szła do krawędzi - 1 (w poście powyżej źle napsiałem, przepraszam). Po prostu przekopiowałem kod z wykładu, niewiele myśląc za n wstawiłem liczbę krawędzi. Czyli dołączyłem do grona osób, które były w stanie zepsuć Bellmana-Forda z wykładu ;].

szymku

Czy nie ma ktoś wygenerowanych jakiś sprośnych testów do Q?? Athina po długim namyśle zwraca mi ANS, a wydaje mi się że wszystkie Wasze wskazówki ująłem w moim alg.

edited: ogarnięte.

trywialna

Ma ktoś może jakieś testy do tego zadania? :(