Phân tích: Reordering Train Cars

Đây là một bài toán khá trực diện, nhưng vấn đề chính để giải đúng là phải liệt kê được tất cả các trường hợp không hợp lệ. Ý tưởng chính của giải pháp là nối một số chuỗi để tạo thành các nhóm rời nhau, sao cho mỗi nhóm chứa một tập hợp các chuỗi bắt buộc phải nối lại với nhau. Sau đó tính số cách tạo ra mỗi nhóm, và kết quả cuối cùng sẽ là giai thừa của số lượng các nhóm rời nhau nhân với số cách tạo ra từng nhóm.

Một trong những vấn đề chính dẫn đến nhiều lần nộp bài sai là việc kiểm tra xem tập hợp các chuỗi đã cho có không hợp lệ hay không. Hãy bắt đầu phân tích bằng cách xác định các trường hợp hợp lệ cần xử lý trước khi tạo nhóm.

Một mẹo nhỏ giúp ích rất nhiều trong quá trình kiểm tra là "nén" tất cả các chuỗi đã cho bằng cách loại bỏ các chữ cái trùng lặp liên tiếp. Ví dụ, nếu chuỗi là aabbccdddeaa, sau khi nén nó sẽ trở thành abcdea. Từ đây, chúng ta giả định tất cả các chuỗi đều đã được nén, ngay cả sau khi nối hai chuỗi ab và bc thì kết quả cũng tự động được nén thành abc thay vì abbc.

Quá trình kiểm tra tính hợp lệ

Đầu tiên, kiểm tra xem trong mỗi chuỗi có ký tự nào lặp lại ở hai vị trí khác nhau không. Ví dụ, ["aba", "abca", "adeab"] đều là các chuỗi không hợp lệ vì a bị lặp lại sau khi đã chuyển sang ký tự khác, trong khi ["ab", "abc", "adbe"] là các chuỗi hợp lệ.

Chúng ta tính toán trước một số thông tin để liệt kê các trường hợp không hợp lệ còn lại. Cần lưu trữ vị trí của mỗi ký tự c trong bảng chữ cái (từ 'a' đến 'z'). Ký tự c sẽ thuộc một trong các loại: (i) ký tự đầu tiên, (ii) ký tự cuối cùng, hoặc (iii) ký tự ở giữa của bất kỳ chuỗi nào có độ dài lớn hơn 1. Ngoài ra, cần đếm số lượng chuỗi chỉ gồm một ký tự duy nhất cho mỗi ký tự c.

Ví dụ, nếu danh sách các chuỗi đã nén là ["abc", "cdef", "a", "a", "gh"], các mảng tính toán trước sẽ là:

begin = {'a': 0, 'c': 1, 'g': 4}   -- (1)
end = {'c': 0, 'f': 1, 'h': 4}     -- (2)
middle = {'b': 0, 'd': 1, 'e': 1}  -- (3)
singleChars = {'a': 2}             -- (4)

Ghi chú:

1. begin[c]: chỉ số của chuỗi mà c là ký tự bắt đầu.
2. end[c]: chỉ số của chuỗi mà c là ký tự kết thúc.
3. middle[c]: chỉ số của chuỗi mà c nằm ở giữa. Lưu ý rằng cdef (chuỗi số 1) có hai ký tự ở giữa, trong khi gh (chuỗi số 4) không có ký tự ở giữa.
4. singleChars[c]: số lượng chuỗi chỉ gồm một ký tự c. Ví dụ, có 2 chuỗi chỉ gồm ký tự 'a'.

Trong khi tính toán các mảng trên, một tập hợp các chuỗi được coi là có khả năng hợp lệ nếu mỗi ký tự thỏa mãn một trong các điều kiện sau:

1. Nó xuất hiện ở giữa của duy nhất một chuỗi và không xuất hiện ở bất kỳ nơi nào khác (không là đầu, không là cuối, không là chuỗi đơn).
2. Nó xuất hiện tối đa một lần ở đầu một chuỗi, tối đa một lần ở cuối một chuỗi, và có thể xuất hiện bất kỳ số lần nào dưới dạng chuỗi đơn.

Ví dụ, các trường hợp sau là không hợp lệ:

• ["abc", "ade"]: ký tự 'a' vi phạm điều kiện 2 (xuất hiện ở đầu 2 chuỗi).
• ["bca", "dea"]: ký tự 'a' vi phạm điều kiện 2 (xuất hiện ở cuối 2 chuỗi).
• ["abc", "dbf"]: ký tự 'b' vi phạm điều kiện 2 (xuất hiện ở giữa một chuỗi và đầu một chuỗi khác).
• ["abc", "ead"]: ký tự 'a' vi phạm điều kiện 1.
• ["abc", "gcf"]: ký tự 'c' vi phạm điều kiện 1.
• ["a", "a", "bac"]: ký tự 'a' vi phạm điều kiện 1.

Tạo nhóm

Một nhóm là một tập hợp các chuỗi phải được nối lại để tạo thành một chuỗi hợp lệ. Ví dụ, ["ab", "bc"] là một nhóm vì chúng phải nối thành abc. Nếu có ["ab", "bc", "de", "xy", "yz"], ta có 3 nhóm rời nhau: ["ab", "bc"], ["de"], và ["xy", "yz"].

Đầu tiên, xử lý các chuỗi đơn. Mỗi loại ký tự c có singleChars[c] chuỗi đơn có thể được nhóm lại theo singleChars[c]! cách. Nhóm này sẽ được đại diện bởi một ký tự c duy nhất.

Khi tạo nhóm, lưu ý rằng chuỗi đầu tiên trong nhóm phải bắt đầu bằng một ký tự không phải là ký tự kết thúc của bất kỳ chuỗi nào khác. Ví dụ, với ["abc", "cde"], ta không thể bắt đầu nhóm bằng cde vì 'c' là ký tự kết thúc của abc.

Cách đếm số nhóm rời nhau:
Duyệt qua tất cả các chuỗi không phải chuỗi đơn mà bắt đầu bằng một ký tự không được dùng làm ký tự kết thúc của bất kỳ chuỗi nào khác. Dùng chuỗi này làm chuỗi bắt đầu của nhóm, sau đó nối với chuỗi bắt đầu bằng ký tự kết thúc của nó (sử dụng mảng begin), và tiếp tục cho đến khi không tìm thấy chuỗi nào để nối tiếp.

["cde", "mno", "abc", "opq", "xyz"]
From these strings we can form 3 disjoint groups as follows:
  1) "mno" + "opq" = "mnopq"
  2) "abc" + "cde" = "abcde"
  3) "xyz"

Sau khi đếm số nhóm từ các chuỗi phức tạp, bước cuối cùng là kết hợp các chuỗi đơn vào các nhóm này nếu có thể.

• Nếu một ký tự c có các chuỗi đơn và cũng xuất hiện trong các chuỗi phức tạp, các chuỗi đơn này phải được nối vào vị trí mà c xuất hiện (đầu hoặc cuối chuỗi phức tạp).
• Nếu một ký tự c chỉ có các chuỗi đơn và không xuất hiện trong bất kỳ chuỗi phức tạp nào, nó tạo thành một nhóm rời riêng biệt.

Số cách sắp xếp cuối cùng:
Giả sử có \(K\) nhóm rời nhau sau khi đã kết hợp tất cả các chuỗi có thể nối.
Số cách = (\(K! \times \prod (singleChars[c]!)\)) mod 1,000,000,007.

Lưu ý quan trọng: Sau khi nối các nhóm, cần kiểm tra lại một lần nữa xem chuỗi tổng hợp cuối cùng có hợp lệ không (các ký tự giống nhau phải đứng cạnh nhau) và có tạo thành chu trình hay không (ví dụ ["ab", "ba"]).

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