Phân tích

Một cách thuận tiện để nhìn bài toán là dựng hệ tọa độ với người xem ở gốc và tâm mỗi cột còn lại tại tọa độ \((x,y)\), trong đó \(x,y\) là các số nguyên không âm nhỏ hơn \(N\).

Xét một cột có tâm \((x,y)\). Giả sử một cột khác có tâm \((a,b)\) cắt đoạn \([(0,0),(x,y)]\). Khi đó \((a,b)\) chắn ít nhất một nửa tầm nhìn tới \((x,y)\), tính từ đoạn thẳng về một phía. Xét cột có tâm \((x-a,y-b)\), tức cột đối xứng với cột kia qua trung điểm đoạn \([(0,0),(x,y)]\). Khoảng cách từ cột này đến đoạn thẳng là như nhau; nó nằm ở phía đối diện của đoạn so với \((a,b)\) nên chắn nửa tầm nhìn còn lại. Suy ra cột tâm \((x,y)\) nhìn thấy được từ gốc khi và chỉ khi đoạn \([(0,0),(x,y)]\) không cắt bất kỳ cột nào khác. Hình sau minh họa tình huống.

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_4980a56c.png

Giả sử cột tâm \((a,b)\) cắt đoạn \([(0,0),(x,y)]\). Rõ ràng \(a\le x\) và \(b\le y\). Hơn nữa, bình phương khoảng cách từ điểm đến đoạn thẳng là

Vì cột cắt đoạn thẳng, \(d^2\times10^6\le R\).

Từ biểu thức này, ta kiểm tra trong thời gian hằng số liệu một cột cho trước có chắn tầm nhìn đến cột khác hay không. Điều này lập tức cho lời giải \(O(N^4)\): với mỗi cột, kiểm tra mọi cột khác. Lời giải chỉ thiếu một chút để đủ nhanh cho Test Set nhỏ, nhưng có một cải tiến đơn giản. Thay vì thử mọi \((a,b)\) cho từng \((x,y)\), với mỗi \(a\) từ 0 đến \(x-1\), chỉ cần thử \(b=ay/x\) làm tròn xuống và lên — hai điểm có hoành độ đó hiển nhiên gần đoạn thẳng nhất. Độ phức tạp trở thành \(O(N^3)\), chắc chắn đủ nhanh cho Test Set nhỏ.

Test Set lớn cần thêm một chút công sức. Tiếp tục từ biểu thức

Nếu \(x\) và \(y\) không nguyên tố cùng nhau, chọn \(a=x/\gcd(x,y)\) và \(b=y/\gcd(x,y)\) tạo ra một cặp \((a,b)\) thỏa mọi điều kiện để che \((x,y)\). Điều này đúng như dự đoán vì \((a,b)\) rõ ràng che mọi cột \((ka,kb)\) với \(k>1\). Nếu \(x\) và \(y\) nguyên tố cùng nhau thì theo một phương trình Diophantine, tồn tại các số nguyên dương \(a,b\) sao cho \(|ay-bx|=1\). Vì \(|ay-bx|\) là số nguyên và trong các ràng buộc của ta nó chỉ có thể bằng 0 khi \(x,y\) không nguyên tố cùng nhau, cặp làm biểu thức bằng 1 cho khoảng cách nhỏ nhất.

Vì vậy, cột \((x,y)\) nhìn thấy được khi và chỉ khi \(x,y\) nguyên tố cùng nhau và

Nói cách khác, ta cần đếm các cặp số nguyên nguyên tố cùng nhau nằm trong một đường tròn bán kính \(10^6/R\) và một hình vuông kích thước \(N\times N\).

Nếu \(N\ge10^6/R\), hình vuông chứa đường tròn; vì vậy tiếp theo giả sử \(N\le10^6/R\le10^6\). Ta có thể đếm mọi điểm trong miền, trừ các bội của 2, 3, 5, ...; cộng lại các bội của \(2\times3=6\), \(2\times5=10\), \(3\times5=15\), ... đã bị trừ hai lần; rồi tiếp tục nguyên lý bù trừ cho mọi ước khả dĩ \(k\) từ 1 đến \(N\). Số điểm là bội của \(k\) phải được nhân với hàm Möbius của \(k\). Có thể tính hàm này cho mọi số từ 1 đến \(N\) bằng một biến thể nhỏ của sàng Eratosthenes, chạy trong thời gian tuyến tính.

Với mỗi \(k\), ta duyệt các giá trị khả dĩ của \(x\): \(k,2k,3k,\ldots\), rồi tìm miền giá trị \(y\). Có thể lấy giá trị nhỏ hơn giữa \(N\) và \(\sqrt{(10^6/R)^2-x^2}\), hoặc dùng tìm kiếm nhị phân, hoặc tìm kiếm tuyến tính. Giá trị \(y\) lớn nhất giảm khi \(x\) tăng, nên nếu bắt đầu từ giá trị đã xét cho \(x\) trước đó, toàn bộ tìm kiếm tuyến tính chỉ mất thời gian tuyến tính (thời gian khấu hao hằng số cho mỗi \(x\)). Tìm kiếm tuyến tính và nhị phân bảo đảm kết quả chính xác; dùng căn bậc hai cũng được vì các giá trị tương đối nhỏ.

Trong các phiên bản hiệu quả nhất, thời gian đếm cho một \(k\) là \(O(N/k)\). Vì \(\sum_{k=1}^N1/k\) xấp xỉ \(\log N\), tổng độ phức tạp là \(O(N\log N)\). Dùng tìm kiếm nhị phân để tìm miền \(y\) chỉ thêm một thừa số logarithm, thành \(O(N\log^2N)\). Cả hai đều đủ nhanh với \(N\) đến \(10^6\).

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - World Finals - Gallery of Pillars, kho Google Coding Competitions (Apache-2.0).