Dana jest trójwymiarowa tablica $H$ o wymiarach $n\times n \times n$ lub $n \times n \times 1$ lub $n \times 1 \times 1$, w której zapisano dodatnie liczby całkowite. Możemy zadać $q$ pytań o zawartość pojedynczych komórek tablicy. Wszystkie komórki poza tablicą mają wartość 0.
Znaleźć lokalne maksimum, czyli komórkę, w której wartość jest nie mniejsza niż wartości w 6 sąsiadach tej komórki.
Tablica ma rozmiar $n \times 1 \times 1$, zatem jest de facto jednowymiarowa. Możemy zastosować tutaj wyszukiwanie binarne.
Zakładamy, że pozycja szukanej komórki jest w przedziale $[x_1,x_2]$ oraz że komórki na zewnątrz przedziału (czyli $x_1-1$ oraz $x_2+1$) mają wartości mniejsze niż maksimum w przedziale.
Następnie pytamy się o liczby z dwóch środkowych komórek przedziału, czyli dla $x_m = (x_1+x_2) / 2$ oraz $x_m+1$. Jeśli $H[x_m] \geq H[x_m+1]$, to wiemy, że możemy się teraz ograniczyć do przedziału $[x_1,x_m]$, bo na pewno będzie w nim istniało lokalne maksimum: idąc z $x_m$ nie możemy ciągle zwiększać wartości, bo w końcu trafimy na granicę przedziału, która z założenie ma mniejszą wartość niż $H[x_m]$. (Zauważmy, że w $[x_m+1,x_2]$ lokalne maksimum nie musi istnieć, bo idąc w prawo możemy ciągle zmniejszać wartości.)
Z kolei gdy $H[x_m] < H[x_m+1]$, to ograniczamy się teraz do przedziału $[x_m+1,x_2]$. Zatem za każdym razem zmniejszamy wielkość przedziału dwukrotnie, więc zadamy $2 \log n$ pytań.
Dla podzadania 1 mamy $2 \log 10^6 \approx 40$, co jest wystarczające.
int n1,n2,n3,q; map<tuple<int,int,int>,int> memo; int ask(int x, int y, int z) { if (x <= 0 || x > n1 || y <= 0 || y > n2 || z <= 0 || z > n3) return 0; auto key = make_tuple(x, y, z); if (memo.find(key) != memo.end()) { return memo[key]; } printf("? %d %d %d\n", x, y, z); fflush(stdout); int h; scanf("%d",&h); return memo[key] = h; } void answer(int x, int y, int z) { printf("! %d %d %d\n", x, y, z); exit(0); } int ask(int x) { return ask(x, 1, 1); } int answer(int x) { answer(x, 1, 1); } int main() { scanf("%d%d%d%d",&n1,&n2,&n3,&q); assert(n2 == 1 && n3 == 1); int x1=1, x2=n1; while (x2 != x1) { int mid = (x2+x1) / 2; int hl = ask(mid), hr = ask(mid+1); if (hl >= hr) { x2 = mid; } else { x1 = mid+1; } } answer(x1); }
Dla podzadania 2 potrzebujemy zadać nie więcej niż 35 pytań. Użyjemy tutaj techniki znanej jako metoda złotego podziału.
W przedziale $[x_1,x_2]$ zapytamy się o komórki $x_L$ i $x_R$ (przy czym $x_1 < x_L < x_R < x_2$). Jeśli $H[x_L] \geq H[x_R]$, to wiemy, że możemy się ograniczyć do przedziału $[x_1,x_R-1]$, a w przeciwnym przypadku do przedziału $[x_L+1,x_2]$. Jednak w obu przypadkach w mniejszym przedziale będziemy już mieli zadane jedno pytanie. Spróbujmy tak dobrać pozycje komórek, o które pytamy w dużym przedziale, żeby w mniejszym przedziale analogiczne pytanie dotyczyło komórki, którą już znamy.
Dla uproszczenia rozważań niech oryginalny przedział ma długość 1 i chcemy dobrać długość $s<1$ dla mniejszego przedziału. Sytuacja wygląda więc tak:
1-s 2s-1 1-s |---------|-----|---------| x1 xL xR x2
Chcemy, żeby punkt $x_L$, czyli lewe pytanie z przedziału $[x_1,x_2]$, stał się prawym pytaniem z przedziału $[x_1,x_R-1]$. Musi zatem być spełnione $$\frac{s}{1} = \frac{1-s}{s}.$$ Dostajemy zatem równanie kwadratowe $s^2+s-1=0$ i jego dodatnie rozwiązanie to $s = (\sqrt{5}-1)/2$.
Zatem zadamy teraz około $\log_{s} 10^6 \approx 29$ pytań.
Ponieważ powyższe obliczenia zakładają, że możemy zadawać pytania w dowolnych punktach rzeczywistych, to przy implementacji warto zapamiętać pytania, które zadaliśmy i zaokrąglać wyniki do tej liczby całkowitej, dla której zadaliśmy już pytanie. Ponadto, pod koniec algorytmu, dla krótkiego przedziału, bezpiecznie przełączyć się na zwykłe wyszukiwanie binarne:
bool inmemo(int x) { auto key = make_tuple(x, 1, 1); return memo.find(key) != memo.end(); } int adjust(int x) { if (inmemo(x)) return x; else if (inmemo(x-1)) return x-1; else if (inmemo(x+1)) return x+1; else return x; } int main() { scanf("%d%d%d%d",&n1,&n2,&n3,&q); assert(n2 == 1 && n3 == 1); int x1=1, x2=n1; while (x2-x1 > 20) { const double s = (sqrt(5)-1)/2.; int pl = adjust(s*x1 + (1-s)*x2); int pr = adjust((1-s)*x1 + s*x2); int hl = ask(pl), hr = ask(pr); if (hl >= hr) { x2 = pr-1; } else { x1 = pl+1; } } while (x2 != x1) { int mid = (x2+x1) / 2; int hl = ask(mid), hr = ask(mid+1); if (hl >= hr) { x2 = mid; } else { x1 = mid+1; } } answer(x1); }
Spróbujemy ugólnić wyszukiwanie binarne na tablicę kwadratową $n \times n \times 1$. Założenie będzie takie, że pozycja szukanej komórki jest w prostokącie $[x_1,x_2] \times [y_1,y_2]$ oraz, że komórki brzegowe (te na zewnątrz prostokąta, sąsiadujące z komórkami w prostokącie) mają wartości mniejsze niż maksimum w prostokącie. Oznaczmy przez $H_b$ maksymalną wartość dla komórek brzegowych.
Ponadto, będziemy utrzymywać pozycję pewnej komórki $(x_o,y_o)$ w prostokącie, której wartość $H_o = H[x_o,y_o]$ jest większa od $H_b$.
Na początku oczywiście $[x_1,x_2] \times [y_1,y_2]$ jest całym prostokątem, $H_b = 0$, a pole $(x_o,y_o)$ jest dowolne.
Będziemy dzielić prostokąt na połowy, na zmianę prostymi poziomymi i pionowymi. Dla podziału poziomego sprawdzamy wartości na wszystkich komórkach na linii $y_m = (y_1+y_2)/2$. Wybieramy też z tej linii komórkę $(x_m,y_m)$ o największej wartości $H_m = H[x_m,y_m]$.
Jeśli $H_o > H_m$, to komórka $(x_o,y_o)$ nie leży na linii $y_m$ i możemy ograniczyć się do tej połowy prostokąta, która zawiera to pole, czyli albo do prostokąta $[x_1,x_2] \times [y_1,y_m-1]$, albo do prostokąta $[x_1,x_2] \times [y_m+1,y_2]$. Bo wartości komórek brzegowych w mniejszym prostokącie będą co najwyżej równe $\max(H_b,H_m) < H_o$.
W przeciwnym wypadku lewy i dolny sąsiad komórki $(x_m,y_m)$ mają wartości nie większe niż $H_m$, zatem zadamy jeszcze pytania o górnego i dolnego sąsiada, czyli komórki $(x_m,y_m-1)$ i $(x_m,y_m+1)$. Jeśli obie mają wartości nie większe niż $H_m$, to możemy zwrócić jako odpowiedź komórkę $(x_m,y_m)$.
A jeśli pierwsza z nich ma wartość większą, czyli $H[x_m,y_m-1] > H_m$, to możemy ograniczyć się do prostokąta $[x_1,x_2] \times [y_1,y_m-1]$, oraz przyjąć $(x_o, y_o) = (x_m,y_m-1)$. Analogicznie jeśli druga z nich ma wartość większą.
Kod może wyglądać następująco:
int main() { scanf("%d%d%d%d",&n1,&n2,&n3,&q); assert(n3 == 1); int x1=1, x2=n1, y1=1, y2=n2; bool horiz = 1; int xo, yo, ho=-1; while (x2 != x1 || y2 != y1) { int xm, ym, hm=-1; if (horiz) { int ymid = (y1+y2)/2; for (int x=x1; x<=x2; ++x) { int h = ask(x, ymid); if (h > hm) { hm = h; xm = x; } } if (ho > hm) { assert(yo != ymid); if (yo < ymid) { y2 = ymid-1; } else { y1 = ymid+1; } } else { if (int ha = ask(xm, ymid-1); ha > hm) { y2 = ymid-1; xo = xm; yo = ymid-1; ho = ha; } else if (int ha = ask(xm, ymid+1); ha > hm) { y1 = ymid+1; xo = xm; yo = ymid+1; ho = ha; } else { answer(xm, ymid); } } } else { // vert int xmid = (x1+x2)/2; for (int y=y1; y<=y2; ++y) { int h = ask(xmid, y); if (h > hm) { hm = h; ym = y; } } if (ho > hm) { assert(xo != xmid); if (xo < xmid) { x2 = xmid-1; } else { x1 = xmid+1; } } else { if (int ha = ask(xmid-1, ym); ha > hm) { x2 = xmid-1; xo = xmid-1; yo = ym; ho = ha; } else if (int ha = ask(xmid+1, ym); ha > hm) { x1 = xmid+1; xo = xmid+1; yo = ym; ho = ha; } else { answer(xmid, ym); } } } horiz ^= 1; } answer(x1, y1); }
Zatem startujemy z prostokąta o wymiarach $n \times n$. W pierwszym kroku dzielimy go prostą poziomą, zadając co najwyżej $n + 2$ pytania, a następnie prostą pionową, zadając co najwyżej $n/2 + 2$ pytania. Po tych krokach wymiary prostokąta zmniejszają się do $n/2 \times n/2$.
Tak więc liczba zadanych przez nas pytań wyraża się rekurencją $$T(n) \leq 3/2 n + 4 + T(n/2) \leq 3 n + 4 \log n.$$ Zatem algorytm ten rozwiąże podzadania 3 i 4.
Tutaj już skorzystamy z tego, że program sprawdzający nie jest adaptatywny, zatem możemy spróbować jakiegoś rozwiązania randomizowanego.
Taki bardzo prosty program mógłby sprawdzić $q$ losowych komórek i wypisać tę o największej wartości. Inny prosty pomysł to zacząć w losowej komórce, a następnie sprawdzić jej 6 sąsiadów i, jeśli ta komórka nie jest dobrą odpowiedzią, przejść do jej sąsiada o większej wartości. Możemy wykonać do $q/6$ kroków takiego spaceru.
W pesymistycznym przypadku te pomysły się nie sprawdzą, ale ich połączenie radzi sobie całkiem nieźle. A konkretnie: najpierw sprawdzamy $q/2$ losowych komórek. Następnie wybieramy spośród nich tę o największej wartości i wykonujemy spacer o co najwyżej $q/12$ krokach. Jeśli wybrana komórka była wśród $q/12$ komórek o największych wartościach w tablicy, to taki spacer na pewno zakończy się znalezieniem lokalnego maksimum.
Jakie jest zatem prawdopodobieństwo, że żadna z $q/2$ losowych komórek nie należy do zbioru $q/12$ komórek o największych wartościach? To jest $$\Big(1 - \frac{q}{12} \frac{1}{n^3}\Big)^{q/2}$$ Dla wartości $n$ i $q$ z podzadania 6 daje to prawdopodobieństwo porażki około $0{,}00055$, co jest wystarczająco mało, by takie rozwiązanie zaliczyło testy:
const int MX[] = {-1,1,0,0,0,0}, MY[] = {0,0,-1,1,0,0}, MZ[] = {0,0,0,0,-1,1}; int main() { scanf("%d%d%d%d",&n1,&n2,&n3,&q); int mx,my,mz, mh=-1; REP(i,q/2) { int x = rand()%n1 + 1, y = rand()%n2 + 1, z = rand()%n3 + 1; int h = ask(x, y, z); if (h > mh) { mx = x; my = y; mz = z; mh = h; } } REP(i,q/2) { int ok = 1; REP(mo,6) { int nx = mx + MX[mo], ny = my + MY[mo], nz = mz + MZ[mo]; int h = ask(nx, ny, nz); if (h > mh) { mx = nx; my = ny; mz = nz; mh = h; ok = 0; break; } } if (ok) { answer(mx, my, mz); } } }