Phân tích

Ta có thể bắt đầu bằng cách mô hình hóa bài toán thành một đồ thị, trong đó mỗi ô của ma trận đầu vào biểu diễn một đỉnh. Các ô kề nhau theo cạnh và có cùng nhãn được nối bằng cạnh; ngoài ra, ta có thể tùy ý thêm các cạnh nối những ô kề nhau theo đường chéo và có cùng nhãn. Mục tiêu là thu được đúng hai thành phần liên thông.

Test Set 1

Có thể giải Test Set 1 bằng quy hoạch động, duyệt lần lượt qua các cột. Khi xét cột thứ \(i\) từ trái sang phải, ta có thể tóm tắt trạng thái của các kết nối đã thêm trong ma trận con \(S\) gồm các cột từ \(1\) đến \(i\) bằng cách ghi lại: (1) cho đến thời điểm hiện tại, ta đã gặp ít nhất một ô của từng nhãn A và B hay chưa; và (2) với hai ô bất kỳ trên cột thứ \(i\) có cùng nhãn nhưng không kề nhau theo cạnh, chúng có được nối với nhau bởi một đường đi trong \(S\) hay không. Sau đó, ta có thể vét cạn mọi cách nối tại mỗi trong số tối đa \(3\) góc ô nằm giữa cột \(i\) và cột \(i + 1\) (Test Set 1 có nhiều nhất \(4\) hàng). Mỗi góc có \(3\) lựa chọn: \, / hoặc không nối; tuy nhiên, có thể giảm số lựa chọn bằng nhận xét rằng nếu có ít nhất một kết nối hợp lệ thì dùng một kết nối luôn là tối ưu, nhờ đó mỗi góc chỉ còn nhiều nhất \(2\) lựa chọn. Nếu tại bất kỳ thời điểm nào ta phát hiện một thành phần A cô lập mới không thể nối với các ô A đã gặp trước đó thì ta đã thất bại; điều tương tự cũng đúng với B. Nếu hoàn tất quá trình, ta có thể chạy lượt thứ hai để dựng lại một cách chọn các kết nối theo đường chéo đã dẫn đến lời giải.

Ý tưởng tưởng chừng đơn giản này có một số chi tiết kỹ thuật mà phần phân tích không trình bày ở đây. Có thể đơn giản hóa một số chi tiết bằng cách bắt đầu và kết thúc quá trình tại những cột chứa cả A lẫn B, đồng thời tiền xử lý để kiểm tra xem có cột ngoài cùng bên trái hoặc ngoài cùng bên phải nào chỉ chứa một loại nhưng đã làm loại còn lại bị chia cắt hay không.

Độ phức tạp thời gian tổng thể của lời giải này là hàm mũ theo \(R\), vì ở mỗi trạng thái ta thử mọi tổ hợp trên \(O(R)\) góc và lưu trạng thái liên thông của \(O(R)\) ô, đồng thời là tuyến tính theo \(C\); công thức chính xác phụ thuộc vào cách xử lý các chi tiết kỹ thuật. Miễn là cơ số của thừa số hàm mũ không quá lớn, lời giải đủ nhanh để vượt qua giới hạn.

Test Set 2

Nhận xét then chốt là: sau khi ta quyết định thêm một số cạnh (các kết nối kề theo đường chéo), hai ô \(c\) và \(d\) có cùng nhãn \(X\) sẽ bị tách rời bất kể mọi quyết định về sau khi và chỉ khi một trong hai điều kiện sau đúng:

1. Trong đồ thị có một chu trình gồm các ô mang nhãn \(Y \ne X\), sao cho một trong hai ô \(c\), \(d\) nằm bên trong chu trình và ô còn lại nằm bên ngoài.
2. Trong đồ thị có một đường đi gồm các ô mang nhãn \(Y \ne X\), trong đó ô đầu và ô cuối của đường đi đều là ô biên của ma trận, còn \(c\) và \(d\) nằm ở hai phía đối diện của đường đi.

Gọi \(G\) là đồ thị khi chưa thêm cạnh chéo nào và \(H\) là đồ thị cuối cùng sau khi đã thêm tất cả các cạnh. Xét đường biên của ma trận. Giả sử trên đó có hai ô \(c\) và \(d\) mang nhãn \(X\) nhưng không liên thông trong \(G\). Vì chúng không liên thông trong \(G\), khi đi quanh đường biên sẽ có hai ô \(e\) và \(f\) mang nhãn \(Y \ne X\), sao cho \(e\) nằm giữa \(c\) và \(d\) theo chiều kim đồng hồ, còn \(f\) nằm giữa \(c\) và \(d\) theo chiều ngược kim đồng hồ. Điều đó có nghĩa là trong \(H\), cả \(c\) với \(d\) lẫn \(e\) với \(f\) đều không thể được nối bằng một đường đi chỉ gồm các ô biên. Do đó, nếu \(c\) và \(d\) liên thông trong \(H\) thì đường đi nối chúng sẽ chia cắt \(e\) và \(f\), và ngược lại. Vì vậy, theo điều kiện thứ hai, nếu trên đường biên có hai ô cùng nhãn nhưng không liên thông trong \(G\) thì bộ test đó là vô nghiệm.

Lưu ý rằng không bao giờ có lý do để tạo một cạnh từ quan hệ kề theo đường chéo nhằm nối hai ô vốn đã liên thông. Theo đoạn trên, nếu một bộ test có lời giải thì mọi ô biên có cùng nhãn đã liên thông trong \(G\). Vì thế, nếu một thuật toán không bao giờ thêm cạnh chéo nối hai ô vốn đã liên thông, nó sẽ không bao giờ tạo ra một đường đi giữa hai ô biên. Ngoài ra, nếu ta không bao giờ nối những ô vốn đã liên thông thì mọi chu trình trong \(H\) đều là chu trình đã tồn tại trong \(G\). Do đó, một lần nữa, nếu cuối cùng ta rơi vào tình trạng không liên thông thì bộ test hẳn đã vô nghiệm ngay từ đầu, trước khi ta thêm bất kỳ kết nối nào.

Các nhận xét này trực tiếp gợi ra thuật toán sau: xét từng quan hệ kề theo đường chéo và tạo một cạnh khi và chỉ khi cạnh đó nối hai ô trước đó chưa liên thông. Nếu cả hai lựa chọn đều dùng được, ta có thể chọn tùy ý, vì ta đã chứng minh rằng chỉ riêng việc không nối những ô vốn đã liên thông cũng đủ bảo đảm thuật toán không tạo ra một đồ thị \(H\) có nhiều hơn \(2\) thành phần liên thông trong trường hợp tồn tại một cách khác tạo ra đúng \(2\) thành phần. Sau quá trình này, hãy kiểm tra xem có đúng \(2\) thành phần liên thông hay có nhiều hơn \(2\), rồi in kết quả.

Nếu cài đặt thuật toán trên bằng cấu trúc hợp-tìm (union-find) để duy trì các thành phần liên thông, ta cần \(O(R \times C)\) phép kiểm tra hai ô có liên thông hay không và \(O(R \times C)\) phép nối. Vì union-find hỗ trợ cả hai thao tác với thời gian khấu hao gần như hằng số, độ phức tạp thời gian tổng thể của thuật toán là gần tuyến tính.

Một thuật toán tương đương là trước tiên tính các thành phần liên thông của \(G\), sau đó dùng các đường đi ngắn nhất để nối hai thành phần bất kỳ có cùng nhãn cho đến khi không thể nối thêm. Vì đường đi ngắn nhất không thể tạo ra chu trình mới, một lập luận tương tự như trên chứng minh rằng lời giải này cũng đúng. Có thể cài đặt lời giải này trong thời gian tuyến tính nếu tái sử dụng đồ thị cây đường đi tối thiểu bộ phận cho mỗi kết nối mới cần thực hiện.

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