Phân tích

Tập dữ liệu nhỏ (Small Input)

Đối với một bài toán như thế này, việc suy nghĩ qua một vài trường hợp có thể hữu ích. Hãy xem xét hai ví dụ đầu tiên từ đề bài:

   2 2 2 2 2
   2 1 1 1 2    2 1 2
   2 1 2 1 2    1 1 1
   2 1 1 1 2    2 1 2
   2 2 2 2 2

Tất cả cỏ cần được cắt xuống độ cao 1 hoặc 2. Do đó, chúng ta có thể bắt đầu bằng cách cắt toàn bộ bãi cỏ xuống độ cao 2. Câu hỏi còn lại là nên cắt những hàng nào và cột nào xuống độ cao 1. Lưu ý rằng nếu chúng ta cắt một hàng (hoặc cột) xuống độ cao 1, tất cả các ô trong hàng hoặc cột đó sẽ có độ cao 1 trong hoa văn cuối cùng vì chúng ta không thể làm cỏ mọc lại.

Trong ví dụ bên trái, tại một thời điểm nào đó chúng ta phải thực hiện một đường cắt với máy cắt cỏ ở độ cao 1. Nếu không, chúng ta sẽ không bao giờ có được bất kỳ phần cỏ nào thấp như vậy. Tuy nhiên, không có nơi nào an toàn để thực hiện một đường cắt như thế. Mọi hàng và mọi cột đều có ít nhất một ô mà chúng ta muốn độ cao cỏ cuối cùng là 2, vì vậy chúng ta không bao giờ có thể chạy máy cắt cỏ qua hàng hoặc cột đó khi ở độ cao 1. Hoa văn này là không thể.

Trong ví dụ thứ hai, chúng ta cũng phải thực hiện một số đường cắt với máy cắt cỏ ở độ cao 1. Tuy nhiên, trong trường hợp này, có hai vị trí mà chúng ta có thể thực hiện đường cắt đó một cách an toàn: hàng ở giữa và cột ở giữa. Nếu chúng ta thực hiện cả hai, chúng ta sẽ có được hoa văn mong muốn.

Nói một cách tổng quát hơn, có một số hàng và cột chúng ta không thể cắt xuống độ cao 1. Bằng cách tránh các hàng và cột đó, chúng ta đảm bảo không có gì bị cắt quá thấp. Việc còn lại là kiểm tra xem có còn khả năng làm cho tất cả cỏ thấp đủ mức yêu cầu hay không. Nếu mục tiêu duy nhất của chúng ta là làm cho cỏ thấp xuống, chúng ta nên thực hiện tất cả các đường cắt có thể!

Điều này gợi ý hướng tiếp cận sau:

• Xác định những hàng và cột nào an toàn để cắt ở độ cao 1 (nghĩa là hoa văn không có ô nào có độ cao > 1 trong hàng hoặc cột đó).
• Thực hiện một đường cắt trên mỗi hàng và cột này ở độ cao 1.
• Kiểm tra xem chúng ta đã làm cho mọi ô thấp đủ mức yêu cầu chưa. Nếu có, hoa văn là khả thi. Ngược lại, nó không khả thi.

Tập dữ liệu lớn (Large Input)

Đối với tập dữ liệu lớn, chúng ta có thể sử dụng chiến lược gần như tương tự. Bạn chỉ cần suy nghĩ kỹ xem điều đó có nghĩa là gì!

Chúng ta có thể cắt bất kỳ hàng hoặc cột nào ở độ cao bằng với độ cao tối đa xuất hiện trong hàng (hoặc cột) đó. Miễn là chúng ta tuân theo quy tắc này, chúng ta sẽ không bao giờ cắt một ô quá thấp, và sau đó như trên, chúng ta chỉ cần cố gắng làm cho mọi thứ thấp đủ mức. Vì mục đích đó, chúng ta muốn sử dụng tất cả các đường cắt có thể. Thuật toán đầy đủ là:

• Lặp qua mọi hàng và tìm độ cao lớn nhất mà hoa văn có trong hàng này. Thực hiện cắt hàng ở độ cao này.
• Làm điều tương tự cho mọi cột.
• Xuất "YES" nếu việc này đạt được hoa văn mong muốn, và "NO" nếu không.

Độ phức tạp

Độ phức tạp của thuật toán này là \(O(N \cdot M)\) cho mỗi bộ test, vì chúng ta chỉ cần duyệt qua các hàng và cột để tìm giá trị lớn nhất, sau đó kiểm tra lại từng ô \(a_{i,j}\). Với \(N, M \le 100\), cách tiếp cận này hoàn toàn nằm trong giới hạn thời gian.

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