Informatyka UJ forum

exeman · Wysłany: Nie 23:22, 26 Mar 2006 Temat postu: J* - Punkty

[link widoczny dla zalogowanych]

Co o tym myslicie? Ja tu widze jakies grafy :P

hansu · Wysłany: Nie 23:40, 26 Mar 2006 Temat postu:

Zwyczajne zadanie na divide and conquer... Troche sie trzeba bedzie pomeczyc nad 3 krokiem ale tak to rekurencja zalatwi sprawe... (chyba bo jeszcze nie myslalem nad tym zadaniem szczegolnie)

exeman · Wysłany: Nie 23:43, 26 Mar 2006 Temat postu:

hansu: mysle, ze tym sposobem bedzie TLE.

mateo · Wysłany: Nie 23:52, 26 Mar 2006 Temat postu:

exeman · Wysłany: Nie 23:57, 26 Mar 2006 Temat postu:

Mateo: nie chodzilo mi o sama rekurencje, ale o sama idee wyszukiwania binarnego. Wydaje mi sie, ze poprostu nie tedy droga.

Robson · Wysłany: Pon 0:49, 27 Mar 2006 Temat postu:

Chyba was zmartwie, ale ta gwiazdka nie jest przypadkowa w tym zadaniu. I wydaje mi sie że może to zadanie byc bardziej upierdliwe niz takie A naprzykład, bo jesli sie nie mylę to jest to książkowy przykład na algorytm zamiatania, gdzie trzeba użyć zrównoważonego drzewa, np AVL. I stad sie chyba bierze jego gwiazdka...

mateo · Wysłany: Pon 1:06, 27 Mar 2006 Temat postu:

Madras · Wysłany: Pon 1:47, 27 Mar 2006 Temat postu:

Cormen s. 1013 i po zadaniu ;).

mateo · Wysłany: Pon 15:31, 27 Mar 2006 Temat postu:

Robson · Wysłany: Pon 17:31, 27 Mar 2006 Temat postu:

na pierwszy rzut oka wydaje mi się że obie metody są równie pokręcone (znaczy sie są logiczne i bazuja na podobnym pomysle, tylko implementacja jest skomplikowana)...
jeszcze nie wiem która lepsza, i nie zamierzam sie tym zajmować aż do weekendu, bo nie mam czasu, ale jakby co to chyba zrobie AVL drzewka - kiedys w koncu trzeba przez to w zyciu przejść ;)

Adams

Ten algorytm z Cormena spokojnie przechodzi. Dodałem sobie jeszcze ładne sortowanie danych po wczytaniu i wszystko śmiga jak burza. Moim zdaniem nie ma sensu udziwniać tego zadania drzewkami AVL...

Uwaga na typ odległości. Dla skrajnie dalekich punktów, może przekroczyć longinta. Mówię, bo sam to sobie uświadomiłem tuż przed wysłaniem zadania :P

Robson

Chciałem zapytać jak poradziliście sobie jesli jekies (wiecej niz jeden) punkty leżą na prostej podziału? Bo ja mam juz niezłego zwisa. Punkty pamietam tak jak ma być: Raz posortowane po x-ach w drugiej tablicy po y-kach. Czy moze to jest obojętne do którego przediału wpadają jakie y-ki?

Np taki przykład:

posortowane x: (0,1) (1,2) (2,5) (2,4) (2,3) (4,8 ) (5,4) (5,1);

posortowane x: (0,1) (5,1) (1,2) (2,3) (5,4) (2,4) (2,5) (4,8 );

i teraz robie unmerge według (2,4):
(0,1) (1,2) (2,3) (2,4)
(5,1) (5,4) (2,5) (4,8 )
no i wtej pierwszej tablicy są pary, które nie wystepuja w posortowaniu według x-a z lewej strony pary (2,3). Czy to moze zaważyć na algorytmie w jakiś sposob, skoro z tablicy x-a kozystamy tylko do wybrania elementu dzielącego? czy wystarczy tylko zadbać o to zeby była równowaga tych tablic?

Rogal

Robson

No i pewnie miałeś racje.. jak narazie ans, ale nie chce mi sie szukać dziur dzisiaj ;) i tak dobrze poszło - 2h i punkt zaczepienia mam ;)

hansu

A ja to robie na listach wiazanych... Tzn na najnizszym poziemie rekurencji, gdy mam 2 albo trzy punkty tworze z nich posortwana liste wiazana... A na wyzszych poziomach odbieram od nizszych dwie listy i robie im merga... Dziala bardzo dobrze tylko trzeba sie w listach nie pogubic :)

Robson

Sięgnąłem do testerki mateo... powiedzcie mi co znaczy jak mam ans i pisze [expected: ...] [received: ...] ?

hansu

To znaczy ze Twoj program dal odpowiedz (received) inna niz oczekiwana (expected).

Robson

no ok, ale dlaczego kropeczki, a nie tak jak w innych przypadkach jakieś liczby? Swoją drogą mam naprawde dziwny błąd bo moj program zawsze podaje mniejsze odpowiedzi :P pewnie mam coś zrypane w liczeniu odległości (!) ;)
---------------------
Hehe juz wiem - u mnie daje dobre wyniki, a na virgo złe, bo jakiejś zmiennej nie inicjalizuję, albo znowu bląd z int64... jeszcze nie wiem dokładnie która zmienna ale sie dowiem :P

mateo

Robson

juz przeszło :) pare głupich naprawde byków strzeliłem i zrobiłem jeden kardynalny - nie scalałem podtablic jak wracałem z rekurencji - i sie sortowanie piepszyło - cóż o tym nie napisali w Cormenie explicite ;)

jeszcze raz wielkie dzieki Mateo za testerke, bo tak to bym siedział i pisał teraz własne generatory i wzorcówki na n^2 złożoności... a tak poszło szybko i bez zbednego bółu :)

exeman

A ja mam taki problem.

1. Prog moj dziala na virgo, dla testow z malymi zakresami dziala, dla duzych juz daje zle wyniki. Stosuje QWordy, ale mimo wszystko zle dziala dla ogromnych odleglosci.

2. Jest wolny (TLE dla duzych testow), mimo, ze stosowalem algorytm Cormena, z jedna modyfikacja: Nie dziele Y na Y1 i Y2 (zeby pasowalo do X1, X2), tylko przekazuje do procki (rekurencyjnej) tylko lewy i prawy zakres z X, co mi daje odpowiedni przedzial po X, a ten Y wyliczam sobie przy wejsciu do procedury (wyciagam z globalnej tablicy posortowanej po y). Dziala, wolno, moze dlatego?

Pozdro :)

Madras

1. Sądzę, że wykonujesz działanie typu longint * longint, a dopiero potem wynik wpisujesz do QWorda. Jeśli masz -1000000 * -1000000, to wynik przekroczy zakres longint'a i dostaniesz śmieci. Dlatego trzeba najpierw zrzutować na większy typ (przynajmniej jedną ze zmiennych), a dopiero wykonywać działanie. Jednak jeśli użyjesz QWorda do tego celu, to konwersja będzie niepoprawna (QWord nie ma znaku), dlatego jedyne sensowne wyjście to użycie Int64. Co prawda ma dwukrotnie mniejszy zakres, jednak w tym zadaniu w zupełności on wystarcza. Ewentualnie przyczyną blędy może być kompilacja z optymalizacją, jeśli powyższe uwagi nie pomogą, to ściągnij testy do siebie, i sprawdź, czy zwykła kompilacja i kompilacja -OG2p3 daje takie same wyniki. Jeśli nie, to musisz popróbować ze wstawianiem x:=x w różnych miejscach kodu (najprawdopodobniej w okolicy rzutowania na int64/wykonywania na nich obliczeń), to już 2 osobom tego typu rzeczy się zdarzały.
2. W jakim czasie wyciągasz z globalnej tablicy, O( n )? Jeśli tak, to nie powinno być problemu przez to... Ja obie podtablice tworzyłem od nowa korzystając z tablic dynamicznych i mi przeszło wszystko.

exeman

Madras: dzieki duzo pomoglo :)
Teraz mam RD8 w niektorych przypadkach, ale to juz raczej niestety sam musze sie pomeczyc :P

Spectro

O ile dobrze pamiętam, w treści zadania było zaznaczone, że punkty są parami różne. Natomiast w niektóych testach matea zdarzały się przypadki równych punktów i właśnie tam mój program dostawał runtimy ;) .

Hetman

gdyby ktos mogl zapodac jak sciagnac testy to bylbym wdzieczny (sposob "standardowy" nie dziala:/ )