English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: Ciepło-zimno - rozwiazanie
Czy ktoś opisałby w kilku słowach swoje rozwiązanie?
Org napisał że jeszcze dzisiaj będzie omówienie ale przy takiej ilości pomyłek i odchyłek od regulaminu w tym roku można się spodziewać wszystkiego. Może te testy w dziale pliki są już tym omówieniem.
Sprawdzam punkty typu A=(0,r/2,r/2,r/2,...) i B=(r,r/2,r/2,...). Wiem, że odległość w wymiarach poza pierwszym nie przekroczy r/2, zaś któryś z tych punktów będzie miał odległość w pierwszym wymiarze >= r/2. Jeśli zrobię zapytania kolejno o A,B,A to wiem dokładnie czy odległości są < czy > czy = (przy jednym wiadomo tylko czy <=). Jeśli A<B to pierwsza współrzędna leży w przedziale 0-r/2, jeśli A>B to w r/2-r. Jeśli A=B to gdzieś na środku, gdzie dokładnie to zależy od parzystości r. Skoro umiem z r zrobić r/2 to umiem zrobić wyszukiwanie binarne.
Mam równoległobok opisany ograniczeniami na każdej wspolrzędnej x_i \in [d_i, g_i], czyli i-ta wspolrzedna zawiera się pomiedzy (d)olnym a (g)órnym ograniczeniem. Startowy to oczywisćie [0,r] wymiar razy. Krotka jest gdzieś w nim (może być na brzegu).
Niech j bedzie wymiarem o największej rozpiętości (oznaczmy ją s).
Jak napsiała Anna, bierzemy wtedy punkty
A = [ (d_1+g_1)/2,(d_2+g_2)/2, .. d_i,... (d_n+g_n)/2 ]
B = [ (d_1+g_1)/2,(d_2+g_2)/2, .. g_i,... (d_n+g_n)/2 ]
Przechodzę (ignorując czy ciepło czy zimno) do punktu A,
potem do B. Jeśli było cieplej, mogę przesunąć d_i o s/2+1,
Jeśli cieplej nie było (wiec B jest wyżej lub na tym samym poziomie) mogę przesunąć g_i o s/2.
Istotny jest tu warunek, że inne wymiary są nie większe.
Że jest to poprawny warunek (że jeśli mamy dane wynik pomiaru i tak przesuniemy, nie zgubimy krotki ze środka) można zobaczyć rysując sobie mały kwadraty (dla obu możliwych parzystości).
Procedura z grubsza połowi nam prostopadłościan póki największy rozmiar >=2 (ma co najmniej trzy punkty).
Po jej zakończeniu (w z grubsza 2*log_2(10^9)~=60 ruchach na wymiar) mamy koteczkę, której rozmiary w poszczególnych osiach są 0 lub 1. 0 oznacza, że wyznaczoną tę współrzędną. 1 oznacza, że mamy dwa punkty, i jest to przypadek kłopotliwy (wystarczy wyobrazić sobie poszukiwania w d wymiarowej kostce o takim rozmiarze - 2^d-1 punktów jest na tej samej wysokości, jeden - rozwiązanie, jest niżej). Musimy wziąć dodatkowy trzeci punkt oczko poza kostką i wykonać kilka testów (u mnie max 3 testy = 4 kroki). Trzeba zwrócić uwagę, by ten dodatkowy punkt nie wyszedł poza obszar gry.
http://pastebin.com/PkuhFCmz
Jak ktoś zobaczy max_element(tablica) niech się nie wzdryga. I tak w każdym kroku robione są inne operacje w czasie liniowym od wymiaru, choćby przygotowanie tablic ze wspolrzednymi do testów, a po zastąpieniu tego przez kopiec czasy spadły o kilka procent.
Niech j bedzie wymiarem o największej rozpiętości (oznaczmy ją s).
Jak napsiała Anna, bierzemy wtedy punkty
A = [ (d_1+g_1)/2,(d_2+g_2)/2, .. d_i,... (d_n+g_n)/2 ]
B = [ (d_1+g_1)/2,(d_2+g_2)/2, .. g_i,... (d_n+g_n)/2 ]
Przechodzę (ignorując czy ciepło czy zimno) do punktu A,
potem do B. Jeśli było cieplej, mogę przesunąć d_i o s/2+1,
Jeśli cieplej nie było (wiec B jest wyżej lub na tym samym poziomie) mogę przesunąć g_i o s/2.
Istotny jest tu warunek, że inne wymiary są nie większe.
Że jest to poprawny warunek (że jeśli mamy dane wynik pomiaru i tak przesuniemy, nie zgubimy krotki ze środka) można zobaczyć rysując sobie mały kwadraty (dla obu możliwych parzystości).
Procedura z grubsza połowi nam prostopadłościan póki największy rozmiar >=2 (ma co najmniej trzy punkty).
Po jej zakończeniu (w z grubsza 2*log_2(10^9)~=60 ruchach na wymiar) mamy koteczkę, której rozmiary w poszczególnych osiach są 0 lub 1. 0 oznacza, że wyznaczoną tę współrzędną. 1 oznacza, że mamy dwa punkty, i jest to przypadek kłopotliwy (wystarczy wyobrazić sobie poszukiwania w d wymiarowej kostce o takim rozmiarze - 2^d-1 punktów jest na tej samej wysokości, jeden - rozwiązanie, jest niżej). Musimy wziąć dodatkowy trzeci punkt oczko poza kostką i wykonać kilka testów (u mnie max 3 testy = 4 kroki). Trzeba zwrócić uwagę, by ten dodatkowy punkt nie wyszedł poza obszar gry.
http://pastebin.com/PkuhFCmz
Jak ktoś zobaczy max_element(tablica) niech się nie wzdryga. I tak w każdym kroku robione są inne operacje w czasie liniowym od wymiaru, choćby przygotowanie tablic ze wspolrzednymi do testów, a po zastąpieniu tego przez kopiec czasy spadły o kilka procent.
Mam pytanie, co do rozwiązania Ani.
Załóżmy, że krotka jest w A. Z algorytmu wychodzi, że A=B (trzy razy odp. będzie, że nie będzie ciepło), a napisałaś, że pierwsza współrzędna leży gdzieś na środku, podczas gdy wynosi ona 0.
Załóżmy, że krotka jest w A. Z algorytmu wychodzi, że A=B (trzy razy odp. będzie, że nie będzie ciepło), a napisałaś, że pierwsza współrzędna leży gdzieś na środku, podczas gdy wynosi ona 0.
@Przemysław: Jeśli krotka jest w A, to idąc z B do A dostaniemy 'ciepło'.
Właśnie sobie uświadomiłem, że źle zrozumiałem treść. Biblioteka porównuje aktualną pozycję z poprzednim zapytaniem, a nie z najlepszą wartością znalezioną do tej pory.
Oczywiście organizatorzy okazali się niezwykle pomocni w wyprowadzeniu mnie z błędu...
Ehh, a mogłem się zapytać o to na forum. Przy takim założeniu zadanie jest nierozwiązywalne, bez użycia wykładniczej liczby zapytań.
Oczywiście organizatorzy okazali się niezwykle pomocni w wyprowadzeniu mnie z błędu...
Ehh, a mogłem się zapytać o to na forum. Przy takim założeniu zadanie jest nierozwiązywalne, bez użycia wykładniczej liczby zapytań.
Czy Wasze rozwiązania poradziłyby sobie z poniższymi wartościami na wejściu?
r = 2
d = 500
k 50000
Punkt szukany obojętny.
r = 2
d = 500
k 50000
Punkt szukany obojętny.
@Przemysław
Postaram się stanąć w ich obronie.
"Po podaniu swojej lokalizacji, Entek dostaje od Krotki komunikat „ciepło”
albo „zimno” – Krotka informuje
go, czy przybliżył się do jej pozycji od miejsca POPRZEDNIEGO kontaktu."
Zatem "Odpowiedź znajduje się w treści zadania" idealnie pasuje.
Postaram się stanąć w ich obronie.
"Po podaniu swojej lokalizacji, Entek dostaje od Krotki komunikat „ciepło”
albo „zimno” – Krotka informuje
go, czy przybliżył się do jej pozycji od miejsca POPRZEDNIEGO kontaktu."
Zatem "Odpowiedź znajduje się w treści zadania" idealnie pasuje.
@Rafał: Tak. r=2, dane losowe (cielib generujący: http://pastebin.com/pJrSNy9k), z kilku uruchomień najgorzej wyszło 2066 zapytań. Ciut ponad 4 na wymiar. Rozwiązanie przed chwilą wklejałem.
@Szczygieł: u mnie 1332 ^^
Co do r=2, też na początku myślałem, że się nie da, ale w porę się zorientowałem, że r=2 oznacza, że są tak naprawdę 3 punkty na każdym brzegu hiperkostki (0,1,2).
Co do r=2, też na początku myślałem, że się nie da, ale w porę się zorientowałem, że r=2 oznacza, że są tak naprawdę 3 punkty na każdym brzegu hiperkostki (0,1,2).