Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
Nie ma to zbyt dużego sensu, ale że jest to pierwsze zadanie (w [B]), z którego da się wrzucić jakieś testy, to wrzucam swój niewielki :) (format chyba oczywisty)
35 11
15 13 14 16 20 13 11 15 10 11 12 9 11 7 9 10 11 6 10 15 7 6 5 7 9 3 5 3 2 5 3 1 3 5 6
2 5 3 2 6 3 7 6 7 8 5
Odp: 12
35 11
15 13 14 16 20 13 11 15 10 11 12 9 11 7 9 10 11 6 10 15 7 6 5 7 9 3 5 3 2 5 3 1 3 5 6
2 5 3 2 6 3 7 6 7 8 5
Odp: 12
@Przemysław: Jeśli krotka jest w A, to idąc z B do A dostaniemy 'ciepło'.
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.
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.
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.
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.
Czy ktoś opisałby w kilku słowach swoje rozwiązanie?
Akurat Google nie miało nic wspólnego z tym problemem. Przyznam, że winny jestem ja.
Ale ostatecznie jestem też zadowolony, bo gdyby nie przedłużyć sprawdzania rundy 3, poprzednia punktacja byłaby dla niektórych bardzo krzywdząca.
Dodatkowo, nie wiem jakim cudem udało Ci się powiązać rundę rozproszoną z problemami technicznymi. Wszystko do tej pory działa świetnie.
W każdym razie -- przepraszam za utrudnienia które spotkały Cię przy rozwiązywaniu zadań z rundy 3.
Ale ostatecznie jestem też zadowolony, bo gdyby nie przedłużyć sprawdzania rundy 3, poprzednia punktacja byłaby dla niektórych bardzo krzywdząca.
Dodatkowo, nie wiem jakim cudem udało Ci się powiązać rundę rozproszoną z problemami technicznymi. Wszystko do tej pory działa świetnie.
W każdym razie -- przepraszam za utrudnienia które spotkały Cię przy rozwiązywaniu zadań z rundy 3.
Zadania interaktywne pojawiały się tutaj zanim Google zostało sponsorem.
Widze ze Google nie tylko proces rekrutacyjny ma kulawy, ale takze gdy zabiera sie za organizacje konkursow, doklada swoje zadania rozproszone i interaktywne, to nagle sprawdzaczka przestaje dawac rade i na sprawdzenie jednej rundy potrzeba 9 godzin. Tymczasem na HackerRanku rekrutacja poprzez konkursy trwa caly rok, mozna sobie usiasc kiedy sie chce, porobic zadania i miec wynik w pare dni, a nie jeszcze jakies rozmowy telefoniczne z javowcami i dwudniowe onsite'y :D
z ciekawosci: jakie wyniki dla:
10
7 104
16 106
6 69
5 141
5 144
6 80
5 19
15 141
5 70
18 132
edit: no tak testy juz sa ;)
10
7 104
16 106
6 69
5 141
5 144
6 80
5 19
15 141
5 70
18 132
edit: no tak testy juz sa ;)
Chyba jest jakaś awaria maszynki. Chwilowo zgłoszenie się nie przetwarza, wisi na "Oczekuje".
Dostałem taki komunikat przy zgłoszeniu do zadania Grzyby po deszczu 2: "cc1plus.old_elf_loader: out of memory allocating 67108864 bytes after a total of 6017024 bytes". Czy to moja wina czy wina sprawdzaczki? (Ten kod ma jakieś 320 linijek, 8800 znaków). To wygląda, jakby kompilatorowi skończyła się pamięć, lecz nie za bardzo wiadomo, co z tym można zrobić (ani kod źródłowy, ani binarka nie przekraczają dozwolonych limitów na rozmiar)
Napisano, że "Limit czasu na jeden test: 20 sekund." Jaki to jest czas?
Czy to znaczy, że między początkiem uruchomienia programu oraz końcem wykonania ostatniej instancji musi być nie więcej 20 sekund czasu prawdziwego światu (clock time), lub czas procesorowy (CPU time) każdej instancji musi być nie więcej 20 sekund, czy co to oznacza?
Czy to znaczy, że między początkiem uruchomienia programu oraz końcem wykonania ostatniej instancji musi być nie więcej 20 sekund czasu prawdziwego światu (clock time), lub czas procesorowy (CPU time) każdej instancji musi być nie więcej 20 sekund, czy co to oznacza?
*wonszy