Phân tích

Để bắt đầu, hãy thử hình thức hóa các quy tắc tạo thành hoa văn của các viên gạch. Nếu tâm ở vị trí \((x, y)\), thì các viên gạch đỏ là những viên ở vị trí \((x', y')\) mà giá trị \(\max(|x - x'|, |y - y'|)\) là số lẻ, trong khi các viên gạch xanh là những viên mà giá trị này là số chẵn. Điều này là do công thức \(\max(|x - x'|, |y - y'|) = C\) với bất kỳ \(C\) nào mô tả một vành hình vuông bao quanh \((x, y)\), và các vành này thay đổi màu sắc theo tính chẵn lẻ của \(C\).

Đối với bài toán nhỏ (Test set 1), chúng ta có thể chứng minh rằng nếu tồn tại một giải pháp, thì tồn tại một giải pháp với \(|X| + |Y| < 202\). Do đó, chúng ta có thể kiểm tra tất cả các ứng viên cho tâm, với mỗi ứng viên kiểm tra xem tất cả các viên gạch có đúng màu hay không, và xuất ra ứng viên tốt nhất. Cách này tất nhiên sẽ không kịp thời gian cho dữ liệu lớn, vì chúng ta sẽ có hơn \(10^{30}\) tâm ứng viên cần kiểm tra.

Phân tích từng viên gạch

Bây giờ chúng ta có thể giả định rằng mình biết tính chẵn lẻ của \(x\) và \(y\). Chúng ta sẽ đơn giản kiểm tra tất cả bốn khả năng, tìm lựa chọn tốt nhất cho tâm cho mỗi trong bốn giả định, và sau đó chọn ra cái được chỉ định bởi các quy tắc phá vỡ sự cân bằng (hoặc xuất "Too damaged" nếu không có giả định nào dẫn đến việc tìm thấy một tâm khả thi cho hoa văn). Điều này giúp dễ dàng hơn trong việc phân tích thông tin thu được từ màu sắc của một viên gạch duy nhất. Giả sử viên gạch tại vị trí \((x', y')\) là màu đỏ. Điều này có nghĩa là \(\max(|x - x'|, |y - y'|)\) phải là số lẻ. Bây giờ, chúng ta đã biết tính chẵn lẻ của \(x, y, x'\) và \(y'\), vì vậy:

• Nếu cả \(x - x'\) và \(y - y'\) đều là số lẻ, thì bất kỳ lựa chọn tâm nào (thỏa mãn yêu cầu về tính chẵn lẻ của \(x\) và \(y\)) đều sẽ phù hợp với thông tin của chúng ta.
• Nếu cả \(x - x'\) và \(y - y'\) đều là số chẵn, thì không có giải pháp nào thỏa mãn các yêu cầu về tính chẵn lẻ.
• Nếu, chẳng hạn, \(x - x'\) là số lẻ, trong khi \(y - y'\) là số chẵn, chúng ta phải có \(|x - x'| \ge |y - y'|\).

Nếu có bất kỳ viên gạch nào thuộc loại thứ hai, chúng ta có thể ngay lập tức trả về "Too damaged" cho các giả định về tính chẵn lẻ này. Chúng ta có thể bỏ qua các viên gạch thuộc loại thứ nhất, và bây giờ chúng ta chỉ còn lại các viên gạch thuộc loại thứ ba.

Lưu ý rằng trong trường hợp thứ ba, vì tính chẵn lẻ của \(x - x'\) và \(y - y'\) khác nhau, nên việc chúng ta sử dụng bất đẳng thức không nghiêm ngặt là không quan trọng, vì trường hợp bằng nhau đã bị loại khỏi sự xem xét bởi các giả định về tính chẵn lẻ. Do đó, khi xem xét các vùng được xác định bởi các bất đẳng thức này, chúng ta có thể bỏ qua các vấn đề liên quan đến "điều gì xảy ra trên các cạnh của các vùng này", vì - theo lập luận trên - các cạnh nhất thiết sẽ bị loại khỏi sự xem xét bởi các giả định về tính chẵn lẻ.

Trường hợp thứ nhất và thứ hai rất dễ phân tích; mẹo là tìm xem liệu có tồn tại một giải pháp hay không (và nếu có, hãy tìm giải pháp tốt nhất) thỏa mãn tập hợp các điều kiện có dạng \(|x - x'| \ge/\le |y - y'|\) cho các \((x', y')\) khác nhau. Biến đổi điều kiện \(|x - x'| \ge |y - y'|\), chúng ta thấy nó tương đương với việc nói rằng một trong các điều sau đây phải giữ nguyên:

• \(x + y \ge x' + y'\) và \(x - y \ge x' - y'\), hoặc
• \(x + y \le x' + y'\) và \(x - y \le x' - y'\).

Chia mặt phẳng

Các đường thẳng \(x + y = x_i + y_i\) và \(x - y = x_i - y_i\) (là ranh giới của vùng thỏa mãn ràng buộc cho các viên gạch đầu vào) chia mặt phẳng thành tối đa \((N + 1)^2\) hình chữ nhật. Ý tưởng của thuật toán của chúng ta sẽ như sau:

• Lặp qua bốn bộ giả định về tính chẵn lẻ của tâm.
• Lặp qua tất cả các hình chữ nhật được tạo bởi các đường ranh giới, và với mỗi hình chữ nhật, hãy kiểm tra xem nó có thỏa mãn các ràng buộc được đặt ra bởi tất cả các viên gạch đầu vào hay không.
• Với mỗi hình chữ nhật thỏa mãn các ràng buộc, hãy tìm ứng viên tâm tốt nhất (theo các điều kiện phá vỡ sự cân bằng) bên trong nó (nếu có).
• Xuất ra ứng viên tâm tốt nhất trong tất cả các ứng viên đã tìm thấy.

Một sự thật thú vị là sẽ có tối đa \(N+1\) hình chữ nhật thỏa mãn các ràng buộc; vì vậy chúng ta không cần lo lắng quá nhiều về hiệu suất của giai đoạn "tìm điểm tối ưu trong hình chữ nhật" (miễn là nó độc lập với kích thước của hình chữ nhật). Cách tiếp cận thô sơ cho giai đoạn thứ hai là \(O(N^3)\) (với mỗi hình chữ nhật kiểm tra tất cả các viên gạch), với \(N\) lên đến 1000 và 50 bộ test, có nguy cơ quá chậm, vì vậy chúng ta sẽ cần tăng tốc nó một chút.

Có nhiều cách để cắt giảm thời gian chạy của giai đoạn kiểm tra ràng buộc cho các hình chữ nhật. Một cách mẫu là xử lý các hình chữ nhật "theo từng hàng", như sau: Lấy tập hợp các hình chữ nhật với \(A \le x+y \le B\), với \(A\) và \(B\) là hai giá trị ranh giới liền kề. Đối với mỗi viên gạch đầu vào (trong số những viên đặt ra bất kỳ ràng buộc nào lên vị trí tâm), chúng ta có hai khu vực thỏa mãn ràng buộc; nhưng chỉ một trong số chúng tương thích với \(A \le x+y \le B\), bởi vì một trong các khu vực thỏa mãn ràng buộc \(x+y \ge C\), trong khi khu vực kia có \(x+y \le C\). Điều này có nghĩa là chúng ta biết khu vực nào là khu vực thú vị cho hàng này; vì vậy chúng ta có được một ràng buộc trên \(x - y\) phải được thỏa mãn bởi tất cả các hình chữ nhật trong hàng này. Điều này sẽ có dạng \(x - y \le D\), hoặc \(x - y \ge D\). Chúng ta lấy giá trị lớn nhất của các cận dưới, giá trị lớn nhất của các cận trên, và thu được một hình chữ nhật mà chúng ta phải kiểm tra. Thuật toán này chạy trong thời gian \(O(N^2)\), sẽ đủ nhanh một cách dễ dàng.

Một thuật toán nâng cao hơn (sử dụng kỹ thuật sweep line) có thể được sử dụng để đạt được thời gian chạy \(O(N \log N)\). Chúng ta sẽ không mô tả nó (vì nó không cần thiết để có được một chương trình đủ nhanh với các ràng buộc đã cho), nhưng chúng tôi khuyến khích người đọc tự tìm hiểu.

Tìm điểm tốt nhất trong một hình chữ nhật

Đây là phần của bài toán có vẻ gây ra nhiều khó khăn nhất cho các thí sinh. Có hai trường hợp cần xem xét ở đây. Hãy giả sử hình chữ nhật của chúng ta được xác định bởi \(A \le x+y \le B\) và \(C \le x-y \le D\).

Hãy định nghĩa:
\(g(k, l) = \min(|k|, |l|)\) nếu \(k\) và \(l\) cùng dấu, ngược lại bằng \(0\).

Nếu \(g(A, B) = 0\) và \(g(C, D) = 0\), thì điểm \((0, 0)\) nằm trong hình chữ nhật của chúng ta. Trong trường hợp này, chỉ cần kiểm tra vùng lân cận gần của gốc tọa độ là đủ. Cụ thể:

• Nếu cả \(x\) và \(y\) được cho là chẵn, \((0, 0)\) rõ ràng là giải pháp tối ưu.
• Nếu cả \(x\) và \(y\) được cho là lẻ, thì bốn điểm tốt nhất, theo thứ tự, là \((1, 1), (1, -1), (-1, 1)\) và \((-1, -1)\). Nếu \(B \ge 2\) chúng ta có thể lấy \((1, 1)\) và xong. Ngược lại, nếu \(D \ge 2\), chúng ta lấy \((1, -1)\); và cứ thế. Nếu cả bốn điểm đều không khả thi, hình chữ nhật không chứa điểm nào thỏa mãn các ràng buộc về tính chẵn lẻ.
• Nếu, chẳng hạn, \(x\) được cho là lẻ, trong khi \(y\) chẵn, tám ứng viên đầu tiên là \((1, 0), (-1, 0), (3, 0), (1, 2), (1, -2), (-1, 2), (-1, -2), (-3, 0)\). Một lần nữa, người ta có thể kiểm tra rằng nếu không có điểm nào trong số đó khả thi, hình chữ nhật không chứa điểm nào thỏa mãn các ràng buộc về tính chẵn lẻ. Điều tương tự cũng xảy ra khi \(x\) chẵn và \(y\) lẻ.

Do đó, nếu \((0, 0)\) nằm trong hình chữ nhật, chúng ta có thể kiểm tra một số lượng hằng số các điểm và lấy điểm khả thi tốt nhất trong số đó.

Khi \((0, 0)\) không nằm trong hình chữ nhật, trước tiên chúng ta tìm khoảng cách Manhattan nhỏ nhất của bất kỳ điểm nào trong hình chữ nhật. Nó bằng \(M := \max(g(A, B), g(C, D))\). Vì tất cả các ranh giới đều có tính chẵn lẻ không đồng nhất với các giả định về tính chẵn lẻ, khoảng cách Manhattan nhỏ nhất mà chúng ta có thể hy vọng là \(M + 1\). Bây giờ chúng ta có một khoảng các điểm có khoảng cách Manhattan \(M + 1\) trong hình chữ nhật của mình, điểm tốt nhất trong số đó là điểm có tọa độ \(X\) cao nhất (trong số những điểm thỏa mãn các điều kiện về tính chẵn lẻ). Một trường hợp đặc biệt cuối cùng cần xử lý ở đây là khi khoảng đó chỉ chứa một điểm và nó có tính chẵn lẻ sai - trong trường hợp này chúng ta cần xem xét khoảng cách \(M + 3\) (việc chứng minh rằng không bao giờ cần xem xét \(M + 5\) được để lại như một bài tập).

Cũng có thể giải bài toán này theo một số cách khác. Một cách khá tiêu chuẩn là xác định một số "điểm nghi ngờ" trong một hình chữ nhật (vùng lân cận của \((0, 0)\), vùng lân cận của các góc, và vùng lân cận của các nơi mà các trục tọa độ cắt các cạnh của hình chữ nhật) và kiểm tra tất cả chúng, lấy giải pháp tốt nhất.

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