Phân tích: Elegant Diamond

Trong vòng đấu đầy khó khăn này, ngay cả bài toán đầu tiên cũng khá thử thách. Các ràng buộc tương đối nhỏ, nhưng có thể không rõ ràng về cách bắt đầu. Suy cho cùng, có rất nhiều cách để bạn có thể nâng cấp một viên kim cương!

Hãy bắt đầu với một câu hỏi đơn giản hơn: cho một vị trí \((c_x, c_y)\), liệu có thể nâng cấp (tức là mở rộng) viên kim cương đã cho thành một viên kim cương thanh lịch có tâm tại \((c_x, c_y)\) không? (Lưu ý rằng tâm này có thể nằm tại một con số, hoặc tại một khoảng trắng giữa các con số, tùy thuộc vào việc viên kim cương thanh lịch có độ dài cạnh chẵn hay lẻ.) Viên kim cương kết quả sẽ phải đối xứng qua các đường thẳng \(x = c_x\) và \(y = c_y\). Cụ thể, điều này có nghĩa là đối với mỗi \((x, y)\), các giá trị ở các vị trí \((x, y)\), \((2c_x - x, y)\), \((x, 2c_y - y)\), và \((2c_x - x, 2c_y - y)\) đều phải bằng nhau. Nếu viên kim cương ban đầu đã có hai giá trị khác nhau trong một trong các bộ bốn này, chúng ta không thể làm gì để thay đổi điều đó.

Ngược lại, nếu không có mâu thuẫn, viên kim cương luôn có thể được mở rộng thành một viên kim cương thanh lịch với tâm tại \((c_x, c_y)\). Đối với mỗi bộ bốn ở trên mà chúng ta đã có ít nhất một giá trị, chúng ta phải điền các giá trị còn lại cho bằng nhau. Sau đó, chúng ta chỉ cần bao quanh tất cả bằng một hình kim cương và điền tất cả các ô còn lại bằng số 0. Đây là một ví dụ:

  1
 2 3
5 6*6
 2 3
  1

Hãy thử mở rộng viên kim cương này thành một viên kim cương thanh lịch có tâm tại dấu *. Đầu tiên, chúng ta điền vào tất cả các bộ bốn, sau đó mở rộng thành một hình kim cương chuẩn bằng cách thêm các số 0:

                             0
  1           1 1           1 1
 2 3         2 3 2         2 3 2
5 6*6  -->  5 6*6 5  -->  5 6*6 5
 2 3         2 3 2         2 3 2
  1           1 1           1 1
                             0

Xong!

Đây rõ ràng là phần mở rộng nhỏ nhất với tâm đã cho, vì vậy tất cả những gì chúng ta cần làm là thử từng tâm khả thi và chọn tâm tạo ra viên kim cương thanh lịch nhỏ nhất có thể.

Tất nhiên, có rất nhiều tâm khả thi, nhưng không cần phải xem xét một tâm nằm hoàn toàn bên ngoài hộp bao quanh (bounding box) của viên kim cương ban đầu. Chúng ta luôn có thể di chuyển một tâm như vậy vào cạnh của hộp bao quanh mà không tạo ra bất kỳ sự không nhất quán nào, và điều đó sẽ dẫn đến một viên kim cương nhỏ hơn cuối cùng.

Tóm lại: chúng ta cần lặp qua tất cả các tâm khả thi nằm trong viên kim cương ban đầu, kiểm tra xem có tồn tại phần mở rộng thanh lịch với tâm đó không, và sau đó lấy giá trị nhỏ nhất trong số đó.

Độ phức tạp

Giải pháp được trình bày ở đây là \(O(n^4)\), đủ nhanh cho bài toán này. Các giải pháp nhanh hơn vẫn tồn tại, và bạn có thể thử tìm kiếm chúng.

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