Lựa chọn trung vị

Vì bốn phần tư được tạo bởi hai đường thẳng phải chứa cùng một số lượng mỏ vàng, mỗi đường thẳng trong hai đường thẳng đó phải chia tập hợp điểm thành hai nửa. Do đó, nếu chúng ta biết độ nghiêng của hai đường thẳng (được cho dưới dạng, ví dụ, góc có hướng mà đường thẳng thứ nhất tạo với trục hoành), chúng ta có thể đặt mỗi đường thẳng ở bất kỳ vị trí nào sao cho nó chia đôi các điểm (ví dụ, bằng cách sắp xếp các điểm theo giá trị tích có hướng với hướng của đường thẳng). Hãy bắt đầu bằng cách chọn bất kỳ góc \(\alpha\) nào làm góc ban đầu và vẽ hai đường thẳng theo quy trình trên.

Giả sử phần tư thứ nhất chứa \(X\) điểm. Phần tư thứ hai chứa \(2N - X\), vì phải có \(2N\) điểm phía trên đường màu đỏ. Phần tư thứ ba sẽ lại chứa \(X\) điểm (vì có \(2N\) điểm bên phải đường màu xanh lá cây), và phần tư thứ tư sẽ chứa \(2N - X\). Vì vậy, nếu \(X = N\), hai đường thẳng của chúng ta là một lời giải đúng. Tuy nhiên, điều này không nhất thiết phải đúng, như chúng ta có thể thấy trong hình trên.

Xoay các đường thẳng

Nếu góc \(\alpha\) chúng ta chọn tình cờ không phải là một lời giải đúng cho bài toán, chúng ta sẽ thử xoay các đường thẳng (bằng cách tăng \(\alpha\)) cho đến khi nó trở nên hợp lệ.

Hãy xem xét điều gì xảy ra khi chúng ta xoay các đường thẳng. Tại một thời điểm nào đó, một hoặc cả hai đường thẳng sẽ xoay đến một vị trí mà thay vì chia tập hợp một cách gọn gàng thành hai nửa, "đường chia" đi qua hai mỏ vàng, với \(2N-1\) mỏ vàng ở mỗi bên (lưu ý rằng chúng ta đang tận dụng thực tế là không có ba điểm nào thẳng hàng, vì vậy chúng ta biết đường thẳng đi qua chính xác hai điểm, chứ không phải, chẳng hạn, bốn điểm). Chúng ta sẽ gọi thời điểm mà có hai điểm trên ít nhất một trong các đường chia là một "điểm gián đoạn". Sau khi chúng ta xoay thêm một chút nữa, các đường thẳng lại chia tập hợp một cách gọn gàng.

Chúng ta sẽ chứng minh trong giây lát rằng tại bất kỳ điểm gián đoạn nào, \(X\) thay đổi tối đa là 1 (nó cũng có thể giữ nguyên). Tuy nhiên, hãy chú ý rằng khi chúng ta tăng \(\alpha\) thêm 90 độ, đường màu đỏ và màu xanh lá cây sẽ đổi chỗ cho nhau, điều đó có nghĩa là phần tư thứ nhất (cũng đã xoay 90 độ) bây giờ chứa \(2N-X\) điểm. Do đó, ở đâu đó ở giữa, \(X\) phải bằng đúng \(N\)!

Điểm gián đoạn

Hãy phân tích điều gì đã xảy ra sau điểm gián đoạn. Rõ ràng, chỉ những điểm nằm trên các đường phân chia mới có thể thay đổi phần tư tại điểm gián đoạn. Một trong các điểm nằm trên đường màu đỏ chuyển từ một trong các phần tư (1, 2) sang một trong các phần tư (4, 3), và điểm kia chuyển theo hướng ngược lại. Do đó, nếu điểm gián đoạn chỉ có các điểm trên một đường thẳng, \(X\) thay đổi tối đa là một.

Chúng ta sẽ thấy rằng ngay cả khi có các điểm trên cả hai đường thẳng tại điểm gián đoạn, \(X\) vẫn sẽ chỉ thay đổi một đơn vị. Các điểm trên đường màu đỏ đi từ các phần tư (1, 4) sang các phần tư (2, 3). Vì vậy, để \(X\) tăng thêm hai, chẳng hạn, chúng ta phải có một điểm từ 2 sang 3 và một điểm từ 4 sang 1 trên đường màu đỏ, trong khi một điểm từ 4 sang 3 và một điểm từ 2 sang 1 trên đường màu xanh lá cây. Tuy nhiên, đường màu đỏ (và cả đường màu xanh lá cây cũng vậy, nhưng hiện tại đường màu đỏ mới quan trọng) đang xoay theo chiều kim đồng hồ - do đó, điểm nằm bên trái hơn sẽ đi xuống, và điểm nằm bên phải hơn sẽ đi lên — vì vậy tình huống mô tả ở trên là không thể xảy ra.

Tìm lời giải

Bây giờ chúng ta có thể sử dụng tìm kiếm nhị phân để tìm lời giải cho bài toán. Bắt đầu với một góc \(\alpha\) tùy ý làm biên trái, và \(\alpha + 90\) độ làm biên phải, giả sử rằng đối với biên trái \(X\) nhỏ hơn \(N\) (nếu nó bằng, chúng ta đã xong, và nếu nó lớn hơn, hãy lấy \(\alpha + 90\) làm biên trái và \(\alpha + 180\) làm biên phải). Chúng ta biết ở đâu đó giữa hai biên có một điểm mà tại đó \(X = N\). Vì vậy, chúng ta chọn một góc ở giữa biên trái và biên phải, và kiểm tra xem \(X\) lớn như thế nào đối với góc trung bình này. Nếu nó bằng \(N\), chúng ta đã xong. Nếu nó nhỏ hơn, góc trung bình là biên trái mới của chúng ta, nếu nó lớn hơn, đó là biên phải mới. Tiếp tục cho đến khi thành công.

Một lần lặp, với cách cài đặt tiêu chuẩn, mất thời gian \(O(N \log N)\) - sắp xếp các điểm hai lần, gán mỗi điểm vào phần tư thích hợp, tìm \(X\). Nếu ai đó quan tâm đủ (không cần thiết trong bài toán này), nó có thể được thực hiện trong thời gian \(O(N)\), sử dụng thuật toán nhanh hơn để tìm các giá trị trung vị (hoặc là thuật toán ngẫu nhiên, như quicksort nhưng chỉ đệ quy vào nửa lớn hơn, hoặc thậm chí là thuật toán xác định với thuật toán median of medians).

Câu hỏi then chốt là "cần bao nhiêu lần lặp của thuật toán tìm kiếm nhị phân để tìm thấy góc chúng ta đang tìm?". Điều này phụ thuộc vào kích thước của khoảng các góc mà chúng ta sẽ cố gắng trúng vào. Khoảng này sẽ chiếm không gian giữa hai điểm gián đoạn nào đó, và mỗi điểm gián đoạn được xác định bởi một đường thẳng nối hai trong số các điểm đầu vào - do đó, kích thước của khoảng có thể được biểu diễn dưới dạng một góc giữa hai đường thẳng, mỗi đường thẳng đi qua hai điểm có tọa độ nguyên không lớn hơn \(10^6\). Một góc như vậy có thể ở mức \(10^{-12}\), điều đó có nghĩa là chúng ta sẽ cần khoảng 40 bước tìm kiếm nhị phân. Do đó, thuật toán của chúng ta sẽ dễ dàng chạy kịp thời gian.

Vấn đề về độ chính xác

Có ba loại vấn đề về độ chính xác có thể gặp phải khi giải bài toán này.

Thứ nhất, có thể xảy ra trường hợp một trong các đường thẳng chúng ta chọn tình cờ là một điểm gián đoạn. Điều này có thể được xử lý (bằng cách chọn một góc trung bình hơi lệch sang trái hoặc phải - sau cùng thì chỉ có hữu hạn các điểm gián đoạn), hoặc tránh bằng cách chọn một góc ngẫu nhiên để bắt đầu - vì có hữu hạn các điểm gián đoạn, nên rất ít khả năng trúng phải một điểm. Cũng có thể chọn các góc xác định để tránh các điểm gián đoạn.

Thứ hai, khoảng các góc mà chúng ta đang cố gắng tìm có thể khá nhỏ, và vì vậy chúng ta sẽ cần nhiều lần lặp tìm kiếm nhị phân. Điều này có nghĩa là chúng ta cần sử dụng các số có độ chính xác tương đối cao để xử lý các đại lượng liên quan. Tuy nhiên, đây là một vấn đề khá phổ biến trong các bài toán hình học và không gây ngạc nhiên cho bất kỳ ai.

Thứ ba, có những giới hạn về độ chính xác mà chúng ta có thể xuất kết quả, và trình chấm cho bài toán sẽ kiểm tra xem các giá trị đầu ra có chính xác hay không. Vì có độ chính xác hữu hạn của đầu ra, sẽ có một số việc làm tròn xảy ra. Điều này có nghĩa là nếu chúng ta không may mắn, và góc đã chọn của chúng ta tình cờ rất gần với biên của khoảng "tốt", việc làm tròn có thể đẩy nó ra khỏi khoảng. Có hai điều chúng ta có thể làm để giảm thiểu điều này. Đầu tiên, chúng ta có thể thêm một vài bước tìm kiếm nhị phân nữa để tìm thêm một vài điểm trong khoảng tốt, và sau đó chọn cho câu trả lời của mình một điểm mà chúng ta biết là tương đối xa so với cạnh. Thứ hai, chúng ta nên sử dụng tất cả độ chính xác mà chúng ta được phép trong đầu vào. Đặc biệt, khi chúng ta biết đường thẳng mình muốn vẽ, chúng ta nên chọn điểm thứ hai mà chúng ta xuất ra (điểm khác với giao điểm) càng xa giao điểm càng tốt trong giới hạn của đầu ra, để giảm thiểu sai số trong góc của đường thẳng do việc làm tròn.

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