Phân tích: Blindfolded Bullseye

Nhóm test 1

Trong Nhóm test 1, bán kính vừa rất lớn vừa được biết trước. Thay \(R\) vào giới hạn của \(X\) và \(Y\) cho thấy tâm ẩn bị giới hạn trong hình vuông cạnh 10 nanômét, tâm tại gốc tọa độ. Do đó chỉ có \(11^2 = 121\) vị trí tâm! Ta chỉ cần ném vào từng vị trí và dừng ngay khi nhận CENTER.

Nhóm test 2

Trong Nhóm test 2, bán kính cũng lớn và đã biết, nhưng đủ nhỏ để hình vuông các tâm ứng viên có cạnh 101 nanômét. Vì thế có 10201 tâm khả dĩ, nhiều hơn rất nhiều số phi tiêu được phép dùng. Ta cần thu hẹp thêm.

Ta có thể tận dụng việc biết chính xác bán kính. Mỗi phi tiêu đều cung cấp một manh mối. Nếu ném vào \(p\) trúng, khoảng cách từ \(p\) đến tâm \(c\) không quá \(R\). Nếu ném vào \(q\) trượt, khoảng cách từ \(q\) đến \(c\) lớn hơn \(R\). Nếu \(p\) và \(q\) gần nhau, những điểm cách \(p\) không quá \(R\) nhưng cách \(q\) lớn hơn \(R\) tạo thành vùng lưỡi liềm hẹp có bề rộng bằng khoảng cách giữa \(p\) và \(q\). Giao vùng này với hình vuông khả năng ban đầu có thể cho miền đủ nhỏ của \(c\) để thử từng khả năng mà không hết phi tiêu.

Ta có thể tìm \(p\) và \(q\) gần nhau bằng cách tìm biên bia. Vì bia rất lớn, biên của nó phải gần biên tường. Xét các điểm \((x,0)\): mọi điểm có \(-10^9+101 \le x \le 10^9-101\) đều cách mọi tâm khả dĩ không quá \(R\), nên chắc chắn nằm trong đường tròn. Ta có thể thử mọi \(x\) ở một phía của đoạn được bảo đảm để tìm một điểm trúng và một điểm trượt cách nhau 1 nanômét. Mỗi phía chỉ có 101 điểm không được bảo đảm nằm trong đường tròn — chẳng hạn \([-10^9,-10^9+100]\) — nên cần nhiều nhất 101 phi tiêu.

Sau đó, tâm phải nằm trong dải lưỡi liềm rộng 1. Giao nó với hình vuông ứng viên \(101 \times 101\) còn nhiều nhất 202 ứng viên, vì không thể có quá 2 ứng viên chung một giá trị \(x\). Hơn nữa, với phần lớn \(x\), phép làm tròn bảo đảm có ít hơn 2, nên 199 phi tiêu còn lại đủ bao phủ mọi ứng viên.

Không cần hình học phức tạp để tìm ứng viên; hình vuông đủ nhỏ để duyệt mọi điểm và kiểm tra khoảng cách tới điểm trúng, điểm trượt nhằm xác định có phải ứng viên hay không.

Nhóm test 3

Với Nhóm test 3, ta có thể dùng cách hình học điển hình hơn. Để tìm tâm đường tròn, ta tìm 3 điểm trên biên rồi tính tâm. Vấn đề là độ chính xác chỉ đến từng nanômét, nên thường chỉ tìm được điểm gần biên chứ không chính xác trên biên; sai số tính toán có thể đáng kể. Có thể chặn sai số rồi kiểm tra cả tâm tính được lẫn các điểm lân cận. Phần toán để tính tâm, nhất là chặn sai số, có thể khó và tốn thời gian nhưng làm được. Hoặc có thể không chặn sai số, ném vào tâm tính được rồi đi xoắn ốc qua các điểm gần đó tới khi gặp tâm thật. Cách này cần tin rằng sẽ không hết lượt, nhưng là giả định hợp lý. May thay, có một cách liên quan đơn giản hơn và rõ ràng đúng hơn được mô tả dưới đây. Dĩ nhiên, ta vẫn phải tìm các điểm "gần biên" của đường tròn, cũng là điều cách đơn giản cần.

Không thể tìm điểm biên như Nhóm test 1, vì nếu bán kính không rất lớn, các điểm đó có thể cách biên tường rất xa. Ta dùng tìm kiếm nhị phân. Giả sử \((x_0,y_0)\) nằm trong bia. Với mọi \(x\) trong \([-10^9,x_0]\), các điểm \((x,y_0)\) gồm một đoạn (có thể rỗng) toàn trượt, rồi một đoạn toàn trúng. Điều tương tự đúng theo chiều ngược lại trên \([x_0,10^9]\). Tương tự, các điểm \((x_0,y)\) với \(y\) trong \([-10^9,y_0]\) hoặc \([y_0,10^9]\) cũng được nhóm theo trúng/trượt. Trên mỗi đoạn, tìm kiếm nhị phân cho điểm chuyển tiếp — một điểm ở biên đường tròn. Đây chính là cách ở Nhóm test 2, ngoại trừ ta cố định \(x_0=0\), vì bán kính đủ lớn để các điểm như \((0,0)\) chắc chắn trong bia và đoạn đủ nhỏ để quét toàn bộ.

Các phép tìm kiếm cho điểm trái nhất và phải nhất trong bia tại tung độ \(y_0\), cùng điểm trên nhất và dưới nhất tại hoành độ \(x_0\). Bia đối xứng qua đường ngang và dọc đi qua tâm. Vì vậy, hai điểm trái nhất, phải nhất tại một tung độ cố định đối xứng nhau và hoành độ tâm là trung điểm hai hoành độ. Tương tự, tung độ tâm là trung điểm tung độ của điểm trên nhất và dưới nhất trong bia tại một hoành độ cố định.

Còn lại là tìm một điểm trong bia. Vì diện tích bia chiếm phần đáng kể diện tích tường (ít nhất \(\pi/16\)), ta có thể ném ngẫu nhiên đến khi trúng (xác suất có thể hơi nhỏ hơn \(\pi/16\) do chỉ xét tọa độ nguyên nanômét, nhưng khác biệt không đáng kể). Xác suất trúng trong không quá 100 lần cho mọi trường hợp là cực kỳ cao. Cũng có cách tất định: chia tường thành các hình vuông cạnh A. Nếu tâm bia nằm trong một hình vuông, chắc chắn ít nhất một đỉnh của nó nằm trong bia. Vì thế, thử mọi đỉnh ấy (chỉ có 25, thậm chí có thể giảm thêm) sẽ tìm được điểm trúng.

Vậy cần một số phi tiêu nhỏ cố định (tối đa 100, tùy phương pháp) để tìm điểm trong bia; mỗi tìm kiếm nhị phân cần nhiều nhất \(31=\operatorname{ceil}(\log_2(2\times10^9+1))\). Tổng tối đa \(4\times31+100\), nhỏ hơn nhiều giới hạn 300. Trong phiên bản đầu, cần ít hơn một tìm kiếm nhị phân — 3 điểm biên đủ xác định tâm duy nhất — nên sau khi tìm tâm có sai số, có thể còn 150 phi tiêu để thăm dò lân cận. Nếu điểm ban đầu là một trong \((X-R,Y)\), \((X+R,Y)\), \((X,Y-R)\) hoặc \((X,Y+R)\), ta sẽ chỉ có hai điểm thay vì ba và không thể tìm tâm. Nếu tìm \((x_0,y_0)\) ngẫu nhiên, xác suất này không đáng kể. Nếu không, ta có thể phát hiện trường hợp đó, biết hai điểm đối nhau và tâm là trung điểm của chúng.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Vòng 1B — Blindfolded Bullseye.