Test Set 1

Trong Test Set 1 chỉ có một quân vua. Có nhiều cách suy ra vị trí của nó; dưới đây là một cách dùng ba truy vấn và tương đối dễ hiểu.

Trước tiên, truy vấn \((-1000000,1000000)\), là góc trên bên trái của miền chứa quân vua, và gọi kết quả là \(A_1\). Giá trị này cho biết quân vua nằm trong vùng hình chữ J nào tính từ góc trên bên trái, như hình sau:

    0123...
    1123
    2223
    3333
    .   .
    .    .
    .     .

Tiếp theo, nếu chưa tình cờ tìm trúng quân vua, truy vấn

Đây là góc của vùng hình chữ J vừa xác định. Gọi kết quả là \(A_2\); nó cho biết quân vua cách góc đó bao xa trong vùng, nhưng ta chưa biết quân vua nằm bên trái hay phía trên góc.

Cuối cùng, nếu vẫn chưa tìm thấy quân vua, truy vấn

Nói cách khác, ta đoán quân vua nằm bên trái góc. Nếu kết quả bằng 0 thì đã tìm thấy quân vua. Nếu không, ta biết nó nằm phía trên góc, tại

Test Set 2

Khi có nhiều hơn một quân vua, không phải lúc nào cũng có thể xác định chính xác vị trí của từng quân. Ví dụ, ta không thể phân biệt trường hợp có hai vua tại \((+1,0)\) và \((-1,0)\) với trường hợp có hai vua tại \((0,+1)\) và \((0,-1)\). Vì thế, hẳn phải có cách trả lời yêu cầu chỉ với thông tin không đầy đủ về vị trí các quân vua.

Metric \(L^\infty\) của đề, tức lấy giá trị lớn nhất của hai độ chênh tọa độ tuyệt đối, hơi bất tiện nếu xử lý trực tiếp. Đó cũng là lý do lời giải Test Set 1 ở trên có tính khá đặc chế.

Chuyển sang tọa độ chéo

Chuyển sang tọa độ chéo sẽ làm bài toán đơn giản hơn. Nếu một điểm có tọa độ gốc \((x,y)\), đặt tọa độ chéo của nó là

Nếu tọa độ chéo của hai điểm là \((u_1,v_1)\) và \((u_2,v_2)\) thì khoảng cách giữa chúng là

Do đó, nếu các quân vua có tọa độ chéo \((u_i,v_i)\) với \(i=1,\ldots,N\), kết quả của truy vấn tại điểm \((u,v)\) là

Ta có thể xử lý riêng hai tổng này. Để tính tổng thứ nhất, cần biết các quân vua nằm trên những đường chéo dốc xuống về bên phải nào; để tính tổng thứ hai, cần biết chúng nằm trên những đường chéo dốc lên về bên trái nào.

Xác định các đường chéo

Xét điểm \((-2M,0)\). Điểm này đủ xa về bên trái để nếu truy vấn tại đó, tổng khoảng cách nhận được là tổng các độ chênh theo tọa độ \(x\). Nếu truy vấn \((-2M,1)\), ta nhận cùng một đáp án, trừ khi có một quân vua tại \((-M,-M)\); trong trường hợp đó, đáp án lớn hơn 1.

Tổng quát hơn, với số nguyên dương \(K\), đặt \(d(K)\) là hiệu giữa kết quả của truy vấn \((-2M,K)\) và kết quả của truy vấn \((-2M,K-1)\). Khi ấy \(d(K)\) bằng số quân vua nằm phía dưới đường chéo

Ta có thể dùng tìm kiếm nhị phân để tìm những vị trí mà \(d(K)\) thay đổi, đồng thời tìm độ lớn của từng thay đổi. Từ đó, xác định được những đường chéo dạng \(x+y=c\) có chứa vua và số vua nằm trên mỗi đường.

Tương tự, bằng cách truy vấn các điểm \((-2M,-K)\), ta xác định được số quân vua nằm trên các đường chéo theo hướng còn lại. Khi đã có dữ liệu này, ta có thể tính hai tổng ở trên và trả lời các yêu cầu của bộ chấm.

Dựa trên phân tích chính thức của Google Code Jam.