Phân tích: Treasure

Nhỏ nhất về mặt từ điển?

Bài toán này yêu cầu bạn mở các rương theo thứ tự nhỏ nhất về mặt từ điển. Như thể việc tìm ra bất kỳ cách nào để mở rương đã đủ khó rồi, chúng tôi lại bắt bạn tìm một cách cụ thể! Nếu bạn chưa từng thử các bài toán tương tự trước đây, phần này có vẻ đặc biệt khó khăn.

Tuy nhiên, đó là một "đòn tung hỏa mù". Giả sử bạn có thể trả lời câu hỏi đơn giản hơn sau đây: "Liệu có thể mở được tất cả các rương hay không?". Sau đó, bạn có thể sử dụng câu trả lời đó như một "hộp đen" để tìm cách mở nhỏ nhất về mặt từ điển. Kiểm tra xem bạn có chìa khóa để mở rương số 1 trước hay không, và liệu hộp đen có nói rằng có thể mở tất cả các rương còn lại sau khi làm như vậy hay không. Nếu câu trả lời cho cả hai câu hỏi là có, thì bạn chắc chắn nên bắt đầu bằng cách mở rương số 1. Ngược lại, bạn không còn cách nào khác ngoài việc thử một chiếc rương khác. Lặp lại logic này cho mọi chiếc rương tại mọi thời điểm, bạn có thể nhận được giải pháp nhỏ nhất về mặt từ điển.

Cách này không nhanh lắm, nhưng ở đây không có quá nhiều rương để lo lắng, vì vậy điều đó vẫn ổn. Và điều đó có nghĩa là, từ bây giờ, chúng ta có thể tập trung vào câu hỏi đơn giản hơn một chút: "Liệu có thể mở được tất cả các rương không?".

Đường đi Euler

Thật không may, ngay cả câu hỏi này vẫn còn khá khó!

Khi giải quyết một vấn đề thực sự hóc búa, đôi khi việc xem xét các trường hợp đặc biệt để xây dựng trực giác có thể hữu ích. Để đạt được mục tiêu đó, hãy giả sử rằng bạn bắt đầu với chính xác một chiếc chìa khóa, một chiếc rương trống và tất cả các rương còn lại cũng chứa chính xác một chiếc chìa khóa. Tại sao lại xem xét trường hợp này? Bạn sẽ thấy ngay!

Trong phiên bản này của bài toán, bạn sẽ luôn có chính xác một chiếc chìa khóa tại bất kỳ thời điểm nào. Khi bạn mở một chiếc rương loại A chứa một chiếc chìa khóa loại B, bạn đang chuyển từ chìa khóa loại A sang chìa khóa loại B. Điều này gợi ý rằng chúng ta có thể biểu diễn bài toán dưới dạng một đồ thị. Chúng ta sẽ có một đỉnh cho mỗi loại rương/chìa khóa, và đối với mỗi chiếc rương, chúng ta sẽ thêm một cạnh có hướng từ loại chìa khóa mở rương đến loại chìa khóa chứa bên trong rương.

Bạn bắt đầu với một chiếc chìa khóa duy nhất, sau đó bạn phải chọn một chiếc rương có loại khớp với nó, mang lại cho bạn một chiếc chìa khóa có thể thuộc loại khác. Từ đó, bạn phải chọn một chiếc rương của loại mới, và cứ tiếp tục như vậy, cuối cùng chọn mỗi chiếc rương chính xác một lần. Trong công thức đồ thị, bạn có thể coi đây là việc bắt đầu tại đỉnh tương ứng với chìa khóa bắt đầu của bạn, sau đó lặp lại việc đi theo các cạnh, sử dụng mỗi cạnh đúng một lần. Nói cách khác, bạn đang tìm một Đường đi Euler trên đồ thị!

Tin tốt ở đây là Đường đi Euler là một bài toán nổi tiếng và bạn có thể tra cứu trên internet cách để biết liệu nó có tồn tại hay không:

• Tối đa một đỉnh (cụ thể là đỉnh bắt đầu) có OutDegree - InDegree = 1.
• Tối đa một đỉnh có InDegree - OutDegree = 1.
• Tất cả các đỉnh khác có InDegree = OutDegree.
• Có đường đi từ đỉnh bắt đầu đến mọi đỉnh khác trong đồ thị.

Tin xấu là nếu trường hợp đặc biệt này đã khó như Đường đi Euler, thì bài toán đầy đủ sẽ còn khó hơn nữa!

Tổng quát hóa Đường đi Euler

Nếu bạn nảy ra quan sát trước đó, điều đầu tiên bạn có thể thử là giảm trực tiếp bài toán đầy đủ xuống các đường đi Euler. Thật không may, điều này có lẽ sẽ thất bại. Một khi bạn có nhiều chìa khóa trong một chiếc rương duy nhất, không có cấu trúc đồ thị nào để sử dụng. (Ít nhất là không có cấu trúc nào chúng tôi tìm thấy!)

Kế hoạch tốt hơn là chỉ tổng quát hóa các điều kiện cần thiết để một đường đi Euler tồn tại. Trên thực tế, những điều kiện đó có thể được mô tả rất tự nhiên theo thuật ngữ của rương và chìa khóa:

• Đối với mỗi loại, phải có ít nhất số lượng chìa khóa của loại đó bằng với số lượng rương của loại đó (tính cả chìa khóa ban đầu và chìa khóa trong rương).
• Phải có khả năng lấy được ít nhất một chiếc chìa khóa của bất kỳ loại đơn lẻ nào.

Hãy gọi một cấu hình rương/chìa khóa là liên thông nếu nó thỏa mãn điều kiện thứ hai, và tốt nếu nó thỏa mãn cả hai điều kiện. Hóa ra là có thể mở được tất cả các rương nếu và chỉ nếu cấu hình đó là tốt!

Và không quá khó để kiểm tra xem một cấu hình có tốt hay không - điều kiện thứ nhất chỉ là một phép đếm, và điều kiện thứ hai có thể được kiểm tra bằng Tìm kiếm theo chiều rộng (BFS) hoặc Tìm kiếm theo chiều sâu (DFS). Vì vậy, tất cả những gì còn lại cho một giải pháp hoàn chỉnh là thuyết phục bản thân rằng việc kiểm tra tính "tốt" thực sự tương đương với bài toán ban đầu:

Khẳng định: Có thể mở được tất cả các rương nếu và chỉ nếu cấu hình là tốt.

Chứng minh: Một chiều là dễ dàng. Nếu cấu hình không tốt, thì chúng ta sẽ không bao giờ có thể mở đủ các rương của một loại nào đó, hoặc vì không có đủ chìa khóa, hoặc vì chúng ta không bao giờ có thể chạm tới dù chỉ một trong những chiếc chìa khóa đó.

Đối với chiều ngược lại, hãy giả sử chúng ta có một cấu hình tốt. Không có gì chúng ta làm từ thời điểm này trở đi sẽ thay đổi việc liệu có đủ chìa khóa của mỗi loại hay không. Chúng ta sẽ chỉ ra rằng luôn có ít nhất một chiếc rương mà chúng ta có thể mở mà vẫn duy trì được tính chất liên thông. Cấu hình kết quả sau đó cũng sẽ tốt, vì vậy cũng sẽ có một chiếc rương chúng ta có thể mở ở đó để duy trì tính liên thông, và cứ tiếp tục như vậy. Lặp lại, chúng ta có thể tiếp tục mở các rương cho đến khi không còn gì.

Vì vậy, tất cả những gì chúng ta cần làm là chứng minh rằng có ít nhất một chiếc rương có thể được mở mà không làm mất tính liên thông. Chúng ta biết cấu hình ban đầu là liên thông. Đối với mỗi loại T, có một chuỗi các rương chúng ta có thể mở để lấy chìa khóa loại T. Nói chính xác hơn, tồn tại một chuỗi các loại \(T_1, T_2, \dots, T_n\), với các tính chất sau:

• Bạn đã có ít nhất một chìa khóa loại \(T_1\).
• \(T_n = T\).
• Đối với mỗi \(i\), có một chiếc rương loại \(T_i\) mà bạn có thể mở để lấy chìa khóa loại \(T_{i+1}\).

Giả sử bạn có một chiếc chìa khóa thuộc loại bất kỳ A. Nếu bạn đã có tất cả các chìa khóa loại A, thì bạn có thể mở tất cả các rương loại A, và làm như vậy chắc chắn sẽ không làm mất tính liên thông. Vì vậy trường hợp đó là dễ dàng.

Ngược lại, phải tồn tại một chiếc rương loại B nào đó chứa một chiếc chìa khóa loại A. Gọi \(T_1, T_2, \dots, T_{n-1}=B, T_n=A\) biểu thị một chuỗi các loại chìa khóa mà bạn có thể đi qua để lấy chìa khóa loại B và sau đó sử dụng nó để lấy một chiếc chìa khóa loại A khác. Như đã đề cập ở trên, chúng ta biết một chuỗi như vậy phải tồn tại. Chúng ta cũng có thể giả định rằng \(T_i \neq A\) với \(1 < i < n\). Nếu không, chúng ta chỉ cần cắt bỏ một phần của chuỗi để có một phương pháp nhanh hơn! Bây giờ chúng ta xem xét hai trường hợp:

• Giả sử rằng \(T_1 \neq A\). Khi đó bạn có thể sử dụng chìa khóa loại A của mình để mở bất cứ thứ gì bạn muốn, và chúng tôi khẳng định cấu hình kết quả vẫn sẽ liên thông.
  Để chứng minh điều này, hãy chọn một loại chìa khóa bất kỳ C (có thể bằng A). Trước khi mở bất kỳ chiếc rương nào, chúng ta biết có một chuỗi các loại chìa khóa \(S_1, S_2, \dots, S_m=C\) sẽ cho bạn một chiếc chìa khóa loại C. Nếu A không nằm trong danh sách này, thì việc mở một chiếc rương loại A không ảnh hưởng đến việc lấy chìa khóa loại C. Ngược lại, danh sách S và danh sách T giao nhau ở đâu đó, vì vậy chúng ta có thể gọi \(j\) là số nguyên lớn nhất sao cho \(S_j\) bằng một \(T_i\) nào đó. Sau đó, sau khi sử dụng chìa khóa A của mình, chúng ta vẫn có thể lấy được chìa khóa loại C theo cách sau: \(T_1, T_2, \dots, T_i=S_j, S_{j+1}, \dots S_m=C\).
  Vì điều này đúng với mọi C, chúng ta biết cấu hình vẫn liên thông!

• Giả sử rằng \(T_1 = A\). Trong trường hợp này, bạn nên sử dụng chìa khóa của mình để mở một chiếc rương loại \(T_2\). Bây giờ bạn vẫn có thể lấy được chìa khóa loại B, và phần còn lại của lập luận diễn ra chính xác như trước.

Do đó, bất kể điều gì xảy ra, bạn luôn có thể mở một chiếc rương mà không làm mất tính liên thông, và khẳng định đã được chứng minh!

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