Informatyka UJ forum

Madras

To dlaczego do cholery mam ANS?...

BTW thx za opdowiedź.

Fidel

jak chcesz to moge spojrzec na kod

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

Madras

@Fidel: Thx again za helpa ;].

liffe

kurczę, trzy gwiazdki na tym, że zapominałem linije debagujące wykomentowywać :smt022

chlebek

bywa, bywa. Ja dostalem pierwszego ANS-a bo mialem lustra nie w ta strone. drugiego bo wypisywalem TAK po tablicy wynikowej no i 3 bo nie mialem odstepow w wyniku, i po co bylo sie spieszyc? :]

Spectro

Rogal

Spectro

jagm

no memset raczej nie śmiga ;] kiedyś czyściłem 3 tablice dwuwymiarowe memsetem i dostałem przez to tle :P

Madras

@Rogal:
Dowód jest przez indukcję na ilość wierszy. Ścinając wiersz od góry, jeden z promieni przekierowujesz lustrem w otwór po prawej, natomiast pozostałe w ten sposób, żeby nie naruszyć warunku na istnienie rozwiązania. Gdy masz już tylko jeden wiersz, ustawiasz lustro pod każdym promieniem, który ma wpaść w dziurę nie leżącą bezpośrednio pod nim.
Mogę Ci to jutro formalnie rozpisać, jak mnie dorwiesz w przerwie między zajęciami (15:15-16:00, 17:30-18:00), bo nie lubię czegokolwiek na kompie rozpisywać, a nie mam skanera, żeby to zrobić na papierze i wrzucić ;P.

kafex

hmm hmm ANS po 3s....odp dla wszystkich testow fidela mam takie same...powiedzcie mi po co w tym zadaniu jakiekolwiek czyszczenie ? :]

Rogal

Spectro: Po ostatnim skoku z tej strony widać, że to nie jest logarytmiczne tylko liniowe, acz z dużo mniejszą stałą. I naprawdę nie chce mi się wierzyć w to, że mógłbyś to zrobić logarytmicznie w jakikolwiek sposób... Bo nawet gdybyś chciał oznaczać w jakiś sposób bloki pamięci to później przy odwoływaniu się do danej komórki byś musiał sprawdzać dla każdego bloku w jakim ona leży, czy ten blok przypadkiem nie jest jakoś znakowany. Niby więc mógłbyś zrobić czyszczenie szybsze, ale korzystanie z każdej komórki pamięci by nie było już w czasie stałym tylko też w jakimś logarytmicznym.

chlebek

kafex

Uzywał ktoś może jakiegoś skutecznego generatora & móglby go zapodac ? :] to jest zadanie z gatunku WTF u wszystkich daje OK ino na athinie nie

kg86

na poczatku probowalem to napisac tak, jak cwiczeniowiec omawial - strasznie zamotany algorytm, mialem 2 tablice po 2000 elementow, jedna wskazywala na poczatki promieni, druga na konce (p[k1] = k2, w[k2] = k1), meczylem sie z tym zadaniem w piatek przez cala noc - nie chcialo chujstwo przejsc :P r4ku mi zapodal ciekawy algorytm - wstawiaj lustra gdzie sie da, skodowalem to w 15 minut i poszlo :) takze r4ku pomoz innym i opisz swoj algorytm, albo pozwol i ja opisze [uzywalem prostszych struktur danych - jednej tablicy na 2000 elementow :)]

Madras

Polecam test:
3 3
G 1 D 2
G 2 P 2
G 3 P 1
L 1 D 1
L 2 P 3
L 3 D 3

Odpowiedź -
\\\
..\
..\

kafex

Poszlo, algos był dobry, wczytywanie też dobre, od początku wszystko ok...tylko programista debil źle deklaruje ;P

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

Dobra, to a propos złożoności, memseta i paru innych spraw.

Traktować jako luźne dywagacje, a nie pretekst do jakiegoś flame'a, na którego i tak nikt nie ma czasu! ;)

1. Złożoność

Mamy policzyć w*h elementów, i tego nie obejdziemy. Można by jedynie oszacować czego będzie mniej (luster czy pustych pól) i stworzyć jedynie zbiór tych punktów. Jedyne rozwiązanie które mi przychodzi później do głowy na stały czas sprawdzenia to hashowanie (pamiętajmy, tablice odpadają bo wtedy trzeba by je zerować!) - jeśli mamy hita, to należy, jeśli missa, to nienależy. Ale hashowanie z obsługą kolizji (inne nas nie interesuje tutaj) pesymistycznie i tak ma zawsze czas liniowy wyszukiwania... (liniowy względem liczby wyników, bo tyle maksymalnie rzeczy będzie w tabeli).

(Dla uproszczenia - K = liczba wyników).

Inna sprawa to trzymanie wyników w formie posortowanej. Możemy założyć strukturkę podobną do countinga. Tj. wyniki trzymamy w tablicy wyniki[] o długości K, a w tablicy count[] o długości h ( przy założeniu h > w, inaczej transponujemy) szereg ilości elementów w kolejnych wierszach (czyli count[ i ] = ile jest łącznie luster we wszystkich wierszach do i-tego włącznie; inaczej: pozycja ostatniego lustra na i-tym poziomie w tablicy wyniki[]). Wtedy sprawdzenie czy dana pozycja pudełka zawiera lustro czy nie jest binserchem po wynikach odpowiedniego poziomu ( binsearch( left = count[ i-1 ], right = count[ i ], szukany ) ), czyli de facto w wersji z dwoma porównaniami O( log( min{ w, K } ) ).
Opłacalne tylko dla liniowej ilości pól które sprawdzamy.

To tak z nudów napisane, tak czy siak - każda reprezentacja się kwadraci już przy liczeniu dla liczby luster rzędu kwadratowego ;))

Za to ciekawy problem - jaka jest maksymalna minimalna ilość luster niezbędnych do wstawienia? Dla zestawu (n,n) dla którego dobrą odpowiedzią byłyby lustra na każdej pozycji istnieje przykładowo rozwiązanie liniowe ( lustra na przekątnej ). Dla nieco zaburzonych danych, np. 4 x 10, wychodzi 10.
Ciekawe, czy liczba jest zawsze liniowa, np. od dłuższego boku czy sumy?

2. Czyszczenie tablicy

a) tak naprawdę, to jeśli to co raku napisał przetransponować na wiersze (zamiana indeksów) to przy założeniu, że najpierw idą dane dla wszystkich promieni z jednej ściany nie trzeba pamięci niczego trzymać poza jedną ścianą - WPP trzeba trzymać obie, i tyle: wszystko to, co byśmy liczyli dla tablicy lub jej wiersza można puszczać od razu na wyjście (i po zrobieniu kolejnego wiersza wczytywać następny promień z drugiej ściany). Czyli pamięciowo Th( 1*min{ w, h } + 1 ). Oczywiście - wtedy nie ma czego czyścić.

b) memset logarytmicznie nie zadziała. Może bardzo szybko, ale logarytmicznie nie nawet jeśli znakowałby całe bloki jako wyczyszczone, to przy pierwszym odwołaniu do niego i nadpisaniu już spójność "czystości" by się poszła kochać i trzeba by zapamiętywać informacje o zmianach - więc byłby już zbiór informacji, które przy każdym odwoływaniu trzeba by przeszukiwać. (Pewnie binsearchem, ale kogo to obchodzi - byłoby to szalenie długie nawet gdyby sprowadzało się do logarytmu iterowanego).

Rogal

cct: Co do złożoności to poniżej O(w*h) nie da się zejść w tym zadaniu i jest to chyba oczywiste. W końcu trzeba choćby tablicę wypisać...

Natomiast co do ilości luster... Stawiam tezę, że jeśli jakiś układ promieni wejściowych / wyjściowych ma rozwiązanie to jest ono jedyne (nie chodzi tylko o ilość luster ale także o ich ustawienie). Ciekawe czy ktoś to udowodni / obali :D

edited: Żeby było ciekawiej za znalezienie kontrprzykładu funduję nagrodę w postaci Prawdziwego Piwa na najbliższym grillu. Pod warunkiem, że sam wcześniej go nie znajdę...

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

Rogal

cct: Nie żebym się czepiał, ale Twój kontrprzykład wali się już na przypadku 2x2 :D

edited: A nie sorry, źle zrozumiałem. Słowo się rzekło, zgłoś się na grillu.

edited2: Co do minimalnej "lustralizacji" pudełka to na pewno dopóki istnieją 2 lustra takie, że "stykają" się na nich 2 takie same promienie to można te 2 lustra usunąć. Konfigurację taką, że już nie istnieją już 2 takie lustra nazwę minimalną.
Ciekawe, czy istnieją 2 konfiguracje minimalne, które są rozwiązaniem tego samego układu wejść/wyjść?
Jeśli nie, to to jest odpowiedź na pytanie o minimalną ilość luster. Bierzesz dowolne rozwiązanie i je zmniejszasz.

kafex

O ile dobrze zrozumialem :

4 4
L 1 D 4
L 2 D 3
L 3 D 2
L 4 D 1
G 1 P 4
G 2 P 3
G 3 P 2
G 4 P 1

takie wejscie ma conajmniej dwa rozwiązania jeżeli chodzi o układ i liczność luster...

r4ku

Ok. wiec na prośbę kg86 napisze algorytm na to zadanie, chyba najbardziej intuicyjny:

Przy/po wczytaniu danych sprawdzamy czy nie istnieje promień wchodzący z lewej, który musi iść do góry, lub promień wchodzący z góry który musi iść w lewo. Jeśli taka sytuacja wystąpi to piszemy „Nie” i kończymy. W przeciwnym wypadku przechodzimy do wstawiania luster.
Mamy tablice reprezentującą naszą plansze, w każdym polu pamiętamy 2 wartości: gdzie chce dotrzeć promień idący od góry, oraz gdzie promień idący od lewej. Do tego mamy drugą tablice gdzie będziemy wstawiać lustra.

Na początku wiemy gdzie chcą dotrzeć wszystkie promienie od góry w 1 wierszu, oraz wszystkie z lewej w pierwszej kolumnie. pole [1][1] ma określone obie wartości. Idziemy kolumnami w dół, zaczynając od pola [1][1]. Dla każdego pola sprawdzamy czy promień z lewej chce dojść do otworu w tym samym wierszu, oraz czy promień z góry chce dojść do otworu w tej samej kolumnie.

jeśli choć jedna z tych sytuacji wystąpi to nie możemy wstawić lustra i do tablicy luster wstawiamy ‘.’ Następnie podajemy promień dalej, czyli wartość promienia idącego z lewej podstawiamy jako wartość promienia idącego z lewej w polu w następnej kolumnie (w tym samym wierszu). To samo robimy z promieniem idącym od góry, czyli podstawiamy jako wartość promienia idącego z góry do następnego pola w następnym wierszu tej samej kolumny.

W przeciwnym wypadku wstawiamy lustro, zaznaczamy ten fakt w tablicy luster. W naszej tablicy kierujemy promienie tak jak odbiją się od lustra, czyli: dla następnego pola w tym samym wierszu jako wartość promienia idącego z lewej wpisujemy wartość promienia idącego od góry w bieżącym polu. Jako wartość promienia idącego z góry w następnym wierszu tej samej kolumny wpisujemy wartość promienia idącego z lewej w bieżącym polu.

Po przejściu wszystkich pól piszemy „Tak” i wypisujemy tablice luster 

W implementacji najłatwiej posłużyć się tablicą 3 wymiarową shortow [liczbaWierszy][liczbaKolumn][2];

A jeśli ktoś czuje usilną potrzebę oszczędzania pamięci to można to zrobić bez większych problemów w tablicy [liczbaWierszy][2][2] ‘obracając’ kolumny, bo w danym momencie przechodzimy jedną, a wartości aktualizujemy w drugiej, następnie z tej pierwszej już korzystać nie będziemy.

Mam nadzieje ze da się zrozumieć ten algorytm z mojego opisu :P w razie czego pytajcie

ps.
odnosnie dywagacji na temat ilosci luster: ten algorytm wstawi maksymalna liczbe luster, za to bardzo latwo udowodnić jego poprawność :)

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