Tìm bàn cờ lớn nhất

Đầu tiên, chúng ta cần một cách nhanh chóng để tìm bàn cờ lớn nhất. Có một kỹ thuật quy hoạch động kinh điển như sau: Gọi larg[i][j] là kích thước của hình vuông lớn nhất có góc dưới bên phải tại ô \((i, j)\). Dễ dàng tính được larg[i][0] và larg[0][j] luôn bằng 1. Đối với bất kỳ ô nào khác, giá trị của larg[i][j] luôn ít nhất là 1, và nó chỉ lớn hơn nếu điều kiện sau được thỏa mãn:

  if (board[i - 1][j] != board[i][j] &&
      board[i][j - 1] != board[i][j] &&
      board[i - 1][j - 1] == board[i][j]) {
    larg[i][j] = 1 + min(larg[i - 1][j],
                         larg[i][j - 1],
                         larg[i - 1][j - 1]);
  }

Trong một lần quét duy nhất theo từng hàng với thời gian tuyến tính, chúng ta có thể tính toán giá trị của larg[][] cho tất cả các ô.

Tìm bàn cờ để loại bỏ

Khi đã có larg[][], việc tìm bàn cờ đầu tiên cần cắt ra rất dễ dàng. Góc dưới bên phải của nó nằm ở ô có giá trị lớn nhất trong larg[][]. Nếu có nhiều ô như vậy, chúng ta sử dụng quy tắc phân xử được mô tả trong đề bài và chọn ô xuất hiện đầu tiên theo thứ tự từ điển của \((i, j)\).

Chúng ta có thể thực hiện việc này trong thời gian tuyến tính bằng cách quét larg[][], nhưng vì sẽ phải thực hiện nhiều lần, tốt hơn là nên tạo một heap chứa các bộ ba có dạng:

  (-larg[i][j], i, j)

và lấy phần tử nhỏ nhất từ heap đó. Bằng cách này, chúng ta đang sắp xếp tất cả các ô theo kích thước giảm dần, sau đó theo hàng tăng dần, rồi đến cột tăng dần. Miễn là chúng ta có thể cập nhật heap này một cách hiệu quả sau khi cắt một bàn cờ, chúng ta luôn có thể lấy được phần tử nhỏ nhất trong thời gian \(O(\log(M \times N))\). Chúng ta cũng có thể sử dụng cây tìm kiếm nhị phân cân bằng thay vì heap.

Loại bỏ bàn cờ và cập nhật larg[][]

Hãy xem xét việc loại bỏ bàn cờ 6x6 đầu tiên từ ví dụ trong đề bài. Chúng ta nên cập nhật larg[][] như thế nào? Trước hết, chúng ta có thể lấp đầy hình vuông 6x6 các ô bằng 0 (hoặc một giá trị đánh dấu đã sử dụng) vì không còn bàn cờ nào có thể được lấy từ những vị trí đó. Nhưng đó không phải là tất cả. Có những ô khác có thể cần được cập nhật. Chúng ở đâu và có bao nhiêu ô như vậy?

Một cách ngây thơ, chúng ta có thể tính toán lại giá trị của tất cả các ô chưa bị đánh dấu trong larg[][] và tiếp tục. Nếu làm vậy, chúng ta sẽ có thuật toán \(O(M^2 \times N^2)\), quá chậm.

Tuy nhiên, lưu ý rằng chúng ta không cần cập nhật các hàng ở phía trên hoặc các cột ở phía bên trái của hình vuông 6x6 đã cắt. Bất kỳ bàn cờ hình vuông nào có góc dưới bên phải nằm trong các khu vực đó vẫn tồn tại và có thể được cắt ra sau. Các bàn cờ duy nhất chúng ta cần lo lắng là những bàn cờ chồng lấp với bàn cờ 6x6 vừa cắt. Ngoài ra, vì chúng ta vừa loại bỏ bàn cờ lớn nhất có thể, chúng ta chỉ cần quan tâm đến các bàn cờ còn lại có kích thước bằng 6 hoặc nhỏ hơn. Góc dưới bên phải của chúng có thể nằm ở đâu để chồng lấp với bàn cờ của chúng ta? Chúng phải nằm trong hình vuông \(12 \times 12\) có tâm tại \((i, j)\) -- góc dưới bên phải của bàn cờ vừa cắt.

Đó là một khu vực có kích thước \(4 \times 6^2\). Thực tế, bất cứ khi nào chúng ta loại bỏ một bàn cờ kích thước \(k \times k\), chúng ta chỉ cần cập nhật một vùng của larg[][] có kích thước tối đa \(2k \times 2k\). Vì mỗi ô chỉ có thể bị loại bỏ tối đa một lần, tổng công việc cập nhật chỉ tốn thời gian tuyến tính; chính xác là \(4 \times M \times N\) lần cập nhật.

Cập nhật heap

Mỗi khi cập nhật larg[][], chúng ta cũng phải cập nhật heap để tìm bàn cờ tiếp theo. Điều này có nghĩa là tìm và xóa một mục cũ, cũng như chèn một mục mới. Với các con trỏ từ các ô đến các phần tử trong heap, hoặc bằng cách sử dụng cây tìm kiếm nhị phân cân bằng, cả hai bước có thể được thực hiện trong thời gian \(O(\log(M \times N))\) cho mỗi lần cập nhật.

Tổng cộng, thuật toán này chạy trong thời gian \(O(N \times M \times \log(N \times M))\), hoàn toàn đủ nhanh cho các ràng buộc của bài toán.

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