Phân tích: Crime House

Ta được cho nhật ký ghi lại các tội phạm vào và rời một ngôi nhà qua cửa trước trong một ngày. Đầu ngày có thể đã có tội phạm ở trong nhà. Ngôi nhà có thể có những lối vào hoặc lối ra khác ngoài cửa trước, và tội phạm có thể đeo mặt nạ khi vào hoặc ra. Nhiệm vụ là xác định liệu nhật ký có thể xảy ra khi ngôi nhà chỉ có một cửa, tức chỉ có cửa trước, hay không; nếu có, phải tìm số người ít nhất có thể còn trong nhà vào cuối ngày.

Xây dựng trực giác

Trước khi trình bày lời giải, hãy xây dựng một ít trực giác. Giả sử ta có một nhật ký mà không tội phạm nào đeo mặt nạ, tức không có sự kiện E 0 hoặc L 0. Khi đó, lời giải là mô phỏng nhật ký từ đầu đến cuối: mô phỏng việc các tội phạm vào và rời nhà qua đúng một cửa, rồi kiểm tra mô phỏng có hợp lệ không. Thay vì hỏi khi nào mô phỏng hợp lệ, hãy xét lúc nó không hợp lệ. Nếu gặp lệnh E X với \(X>0\) trong khi \(X\) đã ở trong nhà, mô phỏng không hợp lệ, vì một người không thể vào hai lần mà chưa rời đi. Tương tự, nếu gặp L X khi \(X\) không ở trong nhà, mô phỏng không hợp lệ. Tuy nhiên, nếu đây là lần đầu tiên gặp lệnh L X, ta có thể coi \(X\) đã ở trong nhà từ đầu ngày, nên sự kiện đó vẫn hợp lệ.

Điều làm bài toán phức tạp là sự hiện diện của những tội phạm đeo mặt nạ. Ta sẽ xử lý bằng một chiến lược tham lam. Trước hết, giả sử có \(S\) tội phạm ở trong nhà vào đầu ngày. Sau đó mô phỏng từ đầu tới cuối như trên, nhưng mỗi khi gặp một tội phạm đeo mặt nạ, ta cố gắng gán cho người đó một mã tội phạm theo cách tham lam. Cách gán sẽ được trình bày sau; trước hết cần định nghĩa vài thuật ngữ dùng trong bản phân tích.

Các thuật ngữ

Ta gọi nhật ký là hàng đợi sự kiện; đó là một dãy các sự kiện E 0, L 0, E X hoặc L X, trong đó \(X>0\). Trong mô phỏng, ta duyệt hàng đợi từ đầu đến cuối. Giả sử đang ở chỉ số \(i\) trong hàng đợi sự kiện; hàng đợi sự kiện hiện tại là dãy con bắt đầu từ chỉ số \(i\) và kéo dài tới cuối hàng đợi. Trong suốt mô phỏng, ta còn duy trì tập mã số của những tội phạm đang ở trong nhà, gọi là INSIDE. Thuật ngữ cuối cùng là sự kiện đã biết tiếp theo của một mã tội phạm cụ thể khác 0. Để minh họa, giả sử hàng đợi hiện tại cùng các chỉ số vị trí là:

0: ‘E 0’
1: ‘E 0’
2: ‘E 5’
3: ‘L 1’
4: ‘E 1’
5: ‘L 1’
6: ‘E 1’
7: ‘L 5’
8: ‘E 2’

Có ba mã tội phạm không đeo mặt nạ: 1, 2 và 5; lưu ý rằng ta không xét những tội phạm đeo mặt nạ. Tội phạm 1 xuất hiện bốn lần trong hàng đợi hiện tại, ở các chỉ số 3, 4, 5 và 6. Sự kiện đã biết tiếp theo của người 1 được định nghĩa là L 1 ở chỉ số 3, vì đây là lần sớm nhất trong bốn sự kiện. Tương tự, người 2 xuất hiện một lần ở chỉ số 8, nên sự kiện đã biết tiếp theo là E 2 ở chỉ số 8. Người 5 xuất hiện hai lần ở chỉ số 2 và 7, nên sự kiện đã biết tiếp theo là E 5 ở chỉ số 2.

Chiến lược tham lam

Bây giờ xét lời giải tham lam. Trước hết, giả sử ban đầu đã có \(S\) tội phạm trong nhà. Ta mô phỏng sự hiện diện của họ bằng cách thêm \(S\) sự kiện E 0 vào đầu hàng đợi. Để việc mô phỏng đơn giản hơn, ta giả vờ rằng tất cả tội phạm đều rời đi vào cuối ngày. Vì thế, thêm \(T\) sự kiện L 0 vào cuối hàng đợi sao cho tổng số sự kiện E bằng tổng số sự kiện L. Sau đó, mô phỏng hàng đợi thu được để kiểm tra tính hợp lệ, đồng thời gán mã số cho những tội phạm đeo mặt nạ nếu có thể. Nếu mô phỏng hợp lệ, đáp án của hàng đợi này là \(T\), tức số tội phạm còn lại trong nhà vào cuối ngày. Cách tìm \(S\), và do đó tìm \(T\) tương ứng, sẽ được trình bày sau.

Ta mô phỏng từ đầu tới cuối. Nếu xử lý thành công tất cả sự kiện, hàng đợi hợp lệ. Tại mỗi thời điểm có một hàng đợi sự kiện hiện tại như đã định nghĩa. Ở đầu mô phỏng, tập INSIDE rỗng. Sau đây là cách xử lý bốn khả năng cho sự kiện đầu tiên của hàng đợi hiện tại: E X, L X, E 0 và L 0, với \(X>0\).

Trường hợp E X

Trong trường hợp này, người \(X\) đang vào nhà. Sự kiện chỉ hợp lệ nếu \(X\) chưa ở trong nhà, điều có thể kiểm tra bằng việc \(X\) không thuộc tập INSIDE. Nếu đúng, đây là một sự kiện hợp lệ; nếu không, sự kiện và toàn bộ mô phỏng đều không hợp lệ, nên ta kết thúc mô phỏng. Khi E X hợp lệ, phải cập nhật INSIDE bằng cách thêm \(X\) vào tập.

Trường hợp L X

Trong trường hợp này, người \(X\) đang rời nhà. Sự kiện chỉ hợp lệ nếu \(X\) đang ở trong nhà, tức \(X\) thuộc tập INSIDE. Nếu đúng, đây là sự kiện hợp lệ; nếu không, sự kiện và toàn bộ mô phỏng đều không hợp lệ, nên ta kết thúc mô phỏng. Khi L X hợp lệ, phải cập nhật INSIDE bằng cách xóa \(X\) khỏi tập.

Trường hợp E 0

Trong trường hợp này, một tội phạm đeo mặt nạ đang vào nhà. Mục tiêu là gán một mã số cho người đó. Nếu gán được, người này đi vào nhà, và ta thêm mã đã gán vào tập INSIDE. Câu hỏi còn lại là nên gán mã nào. Có hai trường hợp cần xét.

Trường hợp E 0 (a)

Trước hết, xét tập những tội phạm đã biết, tức không đeo mặt nạ, xuất hiện trong hàng đợi hiện tại và hiện không ở trong nhà, tức không thuộc INSIDE. Trong số họ, chỉ xét những người có sự kiện đã biết tiếp theo là rời nhà, tức L X đối với người \(X\). Những người này phải rời nhà ở một thời điểm nào đó, nhưng ta chưa biết họ đã vào lúc nào. Tất cả họ phải đi vào bằng những sự kiện E 0 xảy ra trước lúc họ rời đi. Nếu tồn tại người như vậy, ta tham lam chọn người sẽ rời sớm nhất, nhằm dành nhiều thời gian nhất để đưa những người còn lại vào nhà. Tại sao lựa chọn tham lam này đúng? Xét hai người như vậy là 1 và 2. Dãy sự kiện có dạng:

‘E 0’ ... ‘L 1’ ... ‘L 2’

Dấu ... biểu thị những sự kiện khác trong hàng đợi đã được lược khỏi hình minh họa để tránh rườm rà. Để hàng đợi hợp lệ, phải có thêm một E 0 ghép với các sự kiện L 1 và L 2, vì cả 1 lẫn 2 hiện đều không thuộc INSIDE. Có hai khả năng:

‘E 0’ ... ‘E 0’ ... ‘L 1’ ... ‘L 2’

hoặc:

‘E 0’ ... ‘L 1’ ... ‘E 0’ ... ‘L 2’

Trong cả hai tình huống, gán tội phạm đeo mặt nạ đang vào ở sự kiện đầu tiên thành người 1 đều đúng. Nhưng nếu gán người đó thành người 2, khả năng thứ hai ở trên sẽ không hợp lệ, vì L 1 không thể ghép với một E 0 xảy ra sau nó. Do đó, chọn người 1 có lợi hơn. Lập luận này mở rộng cho trường hợp có nhiều hơn hai người.

Trường hợp E 0 (b)

Nếu không có người nào thỏa trường hợp E 0 (a), ta đơn giản tạo một người mới chưa từng xuất hiện ở trạng thái không đeo mặt nạ; chẳng hạn, gán một số rất lớn như một triệu và bảo đảm mỗi người mới nhận một mã duy nhất. Tại sao phải tạo người mới? Phương án khác là chọn một người đang ở ngoài nhà nhưng có sự kiện đã biết tiếp theo là vào nhà. Giả sử đó là người 5; khi ấy dãy có dạng:

‘E 0’ ... ‘E 5’

Để người 5 có thể là người đi vào ở sự kiện đầu, dãy phải có dạng:

‘E 0’ ... ‘L 0’ ... ‘E 5’

Trong tình huống đó, cho người 1.000.000 đi vào cũng tốt như cho người 5 đi vào. Nhưng nếu không có L 0 giữa E 0 và E 5, người 1.000.000 vẫn có thể rời nhà về sau nếu có một L 0, còn người 5 bị buộc phải vào nhà rồi lại vào thêm lần nữa, khiến mô phỏng không hợp lệ. Vì vậy, trong trường hợp này, tạo một người mới với mã duy nhất là lựa chọn tốt hơn.

Trường hợp L 0

Trong trường hợp này, một tội phạm đeo mặt nạ đang rời nhà. Cũng như với E 0, mục tiêu là gán cho người đó một mã số. Sau khi gán mã \(X\), nếu có thể, phải cập nhật INSIDE bằng cách xóa \(X\) khỏi tập. Nếu gặp L 0 khi INSIDE rỗng thì mô phỏng không hợp lệ. Khi có tội phạm trong INSIDE, cần xét ba trường hợp.

Trường hợp L 0 (a)

Xét tất cả tội phạm đang ở trong nhà và có sự kiện đã biết tiếp theo là họ vào nhà. Theo cùng lập luận như trường hợp E 0 (a), chọn người sẽ vào sớm nhất. Nếu gán được như vậy, không cần xét bất kỳ trường hợp L 0 nào khác.

Trường hợp L 0 (b)

Nếu trường hợp trước không có ứng viên, xét tất cả tội phạm đang ở trong nhà. Nếu có người không còn sự kiện đã biết tiếp theo nào với ngôi nhà, dù là E X hay L X, hãy cho người đó rời đi. Người đó phải rời đi vào một lúc nào đó nhưng không bị ràng buộc về thứ tự; cho họ rời tốt hơn là cho một người có sự kiện đã biết tiếp theo là rời nhà. Nếu chọn được một người như vậy, không cần xét trường hợp cuối.

Trường hợp L 0 (c)

Nếu cả hai trường hợp trước đều không áp dụng được, ta chỉ còn những người đang ở trong nhà và có sự kiện đã biết tiếp theo là rời nhà. Khi đó, tham lam chọn người sẽ rời muộn nhất, để có số cơ hội lớn nhất cho người được chọn đi vào nhà trở lại bằng một sự kiện E 0. Tại sao lựa chọn này đúng? Xét hai ứng viên là 1 và 2; dãy sự kiện có dạng:

‘L 0’ ... ‘L 1’ ... ‘L 2’

Để dãy hợp lệ, phải có thêm một E 0. Có hai khả năng:

‘L 0’ ... ‘E 0’ ... ‘L 1’ ... ‘L 2’

và:

‘L 0’ ... ‘L 1’ ... ‘E 0’ ... ‘L 2’

Trong cả hai tình huống, gán người đeo mặt nạ đang rời ở L 0 thành người 2 đều đúng; nhưng chọn người 1 sẽ không đúng ở khả năng thứ hai. Do đó, chọn người 2 cho L 0 có lợi hơn. Lập luận này mở rộng cho trường hợp có nhiều hơn hai người.

Như vậy đã xét xong bốn trường hợp có thể xảy ra với sự kiện đầu tiên của hàng đợi hiện tại. Như đã nói, nếu sự kiện đầu tiên bị xác định là không hợp lệ trong các trường hợp trên, cả mô phỏng không hợp lệ. Nếu gán được một mã tội phạm, ta chuyển tới sự kiện tiếp theo, thu được một hàng đợi hiện tại mới và tiếp tục mô phỏng. Nếu đi tới cuối hàng đợi, hàng đợi sự kiện là hợp lệ.

Chọn \(S\) tội phạm ban đầu ở trong nhà

Ở trên ta giả sử có \(S\) tội phạm ban đầu ở trong nhà, nhưng cần chọn giá trị nào cho \(S\)? Có thể thử mọi giá trị từ 0 đến \(N\), trong đó \(N\) là kích thước hàng đợi. Tuy nhiên, thử từng giá trị vẫn có thể chậm với dữ liệu lớn. Ta có thể dùng tìm kiếm nhị phân để nhanh hơn. Có nhiều người hơn trong nhà, tức \(S\) lớn hơn, đem lại nhiều khả năng hơn để mô phỏng thành công: \(S\) lớn hơn tạo thêm các E 0 ở đầu và các L 0 ở cuối để sử dụng. Hơn nữa, nếu mô phỏng hợp lệ với \(S=i\), nó cũng hợp lệ với \(S=i+1\), bởi ta chỉ thêm một E 0 ở đầu và một L 0 tương ứng ở cuối; hai sự kiện mới này có thể ghép với nhau trong mô phỏng vốn đã hợp lệ cho \(S=i\). Vì vậy, với các giá trị \(S\) nhỏ, mô phỏng có thể không hợp lệ, tức cho giá trị false; nhưng từ một ngưỡng nào đó, mô phỏng bắt đầu hợp lệ và luôn cho true. Hàm boolean cho biết mô phỏng hợp lệ hay không trên miền \(S=0,\ldots,N\) do đó là một hàm boolean đơn điệu. Với hàm đơn điệu, có thể dùng tìm kiếm nhị phân để tìm nhanh hơn.

Cuối cùng, đúng như đề bài quy định, nếu không tìm được mô phỏng hợp lệ với bất kỳ giá trị \(S\) nào, ta in CRIME TIME làm đáp án.

Bản chính thức khuyến nghị người đọc luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Dựa trên phân tích chính thức của Google Code Jam 2014, Vòng 3.