Phân tích

Tiếp cận bài toán

Thoạt nhìn, dường như không thể đạt được số lần đoán đúng mà bài yêu cầu. Nếu chỉ chọn ngẫu nhiên hai chiếc bút mà không viết gì, xác suất thành công là \(46.666\ldots\%\). Mỗi khi viết, lượng mực còn lại chỉ giảm xuống, có vẻ như càng khiến mục tiêu khó đạt hơn. Thế nhưng Bộ kiểm thử 3 lại yêu cầu thành công trong \(63.6\%\) số trường hợp. Ta có thể bắt đầu tiến tới con số đó bằng cách nào?

Nói chung có ba hướng khác nhau. Hướng thứ nhất là giải bài trong đầu hoặc trên giấy, giống cách giải phần lớn bài toán thuật toán: tìm những bài toán con nhỏ hơn có thể giải được, rồi cố gắng tổng quát hóa lời giải của chúng cho toàn bộ bài toán.

Hướng thứ hai thiên về thực nghiệm hơn: vì công cụ kiểm thử cục bộ bao quát toàn bộ bài toán (nghĩa là nó không có đầu vào ẩn), ta có thể dùng công cụ này để thử ngay các ý tưởng. Nhờ vậy, ta nhanh chóng nhận ra những ý tưởng triển vọng hơn và còn có thể tinh chỉnh chúng để đạt hiệu năng tối ưu. Cũng có thể sửa công cụ kiểm thử cục bộ cho thuận tiện hơn khi thử nghiệm; chẳng hạn, sửa giao thức tương tác để mỗi lần chỉ chấm một trường hợp kiểm thử.

Hướng thứ ba bắt đầu bằng việc cài đặt một lời giải quy hoạch động có thể xem là vét cạn kèm ghi nhớ. Trong mỗi trường hợp kiểm thử, trạng thái được xác định hoàn toàn bởi lượng mực ta đã tiêu ở từng bút và những bút đã biết là hết mực. Các phép chuyển tương ứng với thao tác cơ bản sẵn có: thử tiêu một đơn vị mực từ một bút. Hơn nữa, có thể gộp thành một những trạng thái chỉ khác nhau bởi một hoán vị các bút, vì trong chiến lược tối ưu chúng có cùng xác suất thành công. Cuối cùng, mỗi khi quyết định ngừng viết và chọn hai bút, ta phải tính được xác suất thành công; có thể làm điều này bằng cách xét mọi hoán vị hoặc dùng một chút tổ hợp (nhanh hơn đôi chút). Cách này chậm đến mức vô vọng với \(N=15\). Tuy nhiên, ta có thể chạy nó cho các giá trị \(N\) nhỏ để lấy cảm hứng: in ra các chuỗi tương tác xảy ra với nhiều hoán vị đầu vào, rồi tổng quát hóa hiện tượng quan sát được thành một thuật toán dùng được cho \(N\) lớn hơn.

Bộ kiểm thử 1

Làm thế nào tìm được một bài toán con nhỏ mà việc viết thực sự giúp tăng xác suất thành công? Giả sử chỉ có ba bút còn lần lượt \(1\), \(9\) và \(10\) đơn vị mực. Nếu chọn ngẫu nhiên hai bút, xác suất để tổng mực của chúng ít nhất là \(15\) chỉ bằng \(1/3\): \(9+10\ge15\), nhưng \(1+9<15\) và \(1+10<15\). Trái lại, nếu trước tiên viết \(2\) đơn vị bằng mỗi bút, ta sẽ biết bút nào vốn có \(1\) đơn vị vì nó không thể viết đủ \(2\) đơn vị. Do đó, ta biết hai bút còn lại đang có \(7\) và \(8\) đơn vị mực, có thể chọn chúng và thành công với xác suất \(1\)!

Ta tổng quát hóa cách này cho bài toán ban đầu như thế nào? Chọn một số \(K\) rồi viết \(K\) đơn vị bằng mỗi bút. Khi đó, ta biết danh tính các bút \(0,1,\ldots,K-1\) để tránh mang chúng tới Nam Cực. Tuy nhiên, các bút còn lại sẽ có \(0,1,\ldots,N-K\) đơn vị mực, có vẻ rõ ràng còn tệ hơn trạng thái ban đầu. Nhưng ta có thể thêm một tối ưu nhỏ: dừng viết ngay khi đã tìm thấy tất cả bút thuộc tập \(0,1,\ldots,K-1\). Ví dụ, nếu cả hai bút cuối đều có ít nhất \(K\) đơn vị lúc đầu, ta sẽ dừng trước khi tới chúng. Vì thế, tại thời điểm nhận diện đủ các bút \(0,1,\ldots,K-1\) và dừng viết, ta hoàn toàn chưa chạm vào hai bút ấy. Ta biết lượng mực của cả hai đều thuộc tập \(K,K+1,\ldots,N\), nên chọn chúng cho xác suất thành công cao hơn nhiều. Dĩ nhiên, điều này không phải lúc nào cũng xảy ra; đôi khi chỉ có một hoặc không có bút nào chưa bị chạm tới. Trong trường hợp đó, nếu có bút chưa bị chạm tới thì chọn nó, rồi bổ sung một bút ngẫu nhiên trong số những bút đã viết thành công \(K\) đơn vị.

Chạy chiến lược này với công cụ kiểm thử cục bộ cho nhiều giá trị \(K\) cho thấy khi \(K=3\), nó thành công trong khoảng \(56.5\%\) tổng số trường hợp, đủ để qua Bộ kiểm thử 1. Ta gọi chiến lược này là fixed-K.

Chắc chắn còn nhiều cách khác để qua Bộ kiểm thử 1, chẳng hạn các bản cài đặt kém chính xác hơn của những lời giải cho Bộ kiểm thử 2 và 3 được trình bày bên dưới.

Bộ kiểm thử 2

Làm sao cải thiện thêm? Cách hiện tại có hai điểm kém hiệu quả. Điểm thứ nhất là ta vẫn tiếp tục viết \(K\) đơn vị bằng mỗi bút ngay cả khi đã tìm ra bút ban đầu có \(K-1\) đơn vị. Vì lúc này chỉ còn tìm \(0,1,\ldots,K-2\), với mỗi bút tiếp theo chỉ cần viết \(K-1\) đơn vị là đủ. Tổng quát hơn, nếu \(X\) là bút đầy nhất trong tập \(0,1,\ldots,K-1\) mà ta chưa nhận diện, ta chỉ cần viết \(X+1\) đơn vị bằng bút kế tiếp. Sau khi nhận diện đủ các bút trong tập \(0,1,\ldots,K-1\), ta dừng viết và mang tới Nam Cực hai bút không thuộc tập này đã viết ít đơn vị nhất. Ta gọi cải tiến này là viết cẩn thận (careful writing).

Hóa ra viết cẩn thận với \(K=4\) làm xác suất tăng đáng kể lên \(61.9\%\), đủ để qua Bộ kiểm thử 2!

Điểm kém hiệu quả thứ hai là trong số những bút được xác định có ít nhất \(K\) đơn vị, ta mang hai chiếc tới Nam Cực còn tất cả những chiếc khác đều vô dụng. Chẳng hạn, cuối cùng ta không bao giờ mang chiếc nào ngoài \(K+2\) bút cuối tới Nam Cực! Do đó, ta có thể bắt đầu bằng cách viết cho tới khi cạn \(N-K-2\) bút đầu tiên mà vẫn giữ nguyên xác suất thành công. Nếu dùng thông tin thu được từ các bút ấy để đưa ra những quyết định có khả năng tốt hơn, ta còn có thể tăng xác suất thành công!

Cụ thể, ban đầu hãy viết bằng bút thứ nhất cho tới khi nó cạn (và nhờ đó biết lượng mực ban đầu của nó). Sau đó viết cạn bút thứ hai, rồi cứ tiếp tục như vậy. Theo cách này, ta luôn biết chính xác những bút nào còn lại. Tại một thời điểm nào đó, ta phải quyết định ngừng thu thập thông tin và chuyển sang chiến lược fixed-K. Thông tin đã thu thập cho phép chọn giá trị \(K\) tối ưu, và giá trị đó có thể khác nhau ở các nhánh khác nhau.

Điều này dẫn tới một quy hoạch động có \(2^N\) trạng thái: mỗi trạng thái được xác định bởi tập các bút còn lại sau khi ta đã viết cạn một số bút. Ở mỗi trạng thái, ta xét hoặc viết bút kế tiếp cho tới khi cạn, hoặc thử chiến lược fixed-K với từng giá trị \(K\). Lưu ý rằng chỉ cần chạy quy hoạch động một lần trước khi bắt đầu tương tác, rồi dùng kết quả của nó để giải mọi trường hợp kiểm thử.

Ta gọi cải tiến này của chiến lược fixed-K là khám phá bút (pen exploration). Hóa ra khám phá bút cho phép thành công trong khoảng \(62.7\%\) tổng số trường hợp, cũng đủ để qua Bộ kiểm thử 2. Chúng tôi tin rằng còn nhiều cách khác để qua bộ này.

Bộ kiểm thử 3

Còn Bộ kiểm thử 3 thì sao? Có lẽ bạn đã đoán ra: ta thực sự có thể kết hợp viết cẩn thận với khám phá bút! Lời giải thu được thành công trong khoảng \(63.7\%\) tổng số trường hợp. Con số này sát ngưỡng Bộ kiểm thử 3, nên lời giải có thể không qua ngay lần đầu do kém may mắn, nhưng chắc chắn sẽ qua sau vài lần thử.

Dù vậy, đây không phải cách duy nhất để giải Bộ kiểm thử 3. Quan sát kỹ lời giải viết cẩn thận, ta thấy có thể đạt đúng cùng một kết quả bằng cách đi từ dưới lên thay vì đi từ trái sang phải. Cụ thể, trước tiên lần lượt viết một đơn vị bằng mỗi bút theo thứ tự trái sang phải cho tới khi gặp một bút không viết được; ta kết luận đó là bút ban đầu có \(0\) đơn vị. Sau đó, lại đi từ trái sang phải và bảo đảm mỗi bút tiếp theo đã viết tổng cộng hai đơn vị (tức là viết thêm một đơn vị ở những bút đã viết một đơn vị, hoặc viết hai đơn vị ở những bút chưa bị chạm tới trong lượt trước), cho tới khi tìm được bút ban đầu có \(1\) đơn vị. Tiếp tục tương tự cho tới khi tìm được các bút \(0,1,\ldots,K-1\) như trước. Tại thời điểm này, lượng đã viết bằng từng bút sẽ đúng bằng lượng đã viết trong cách viết cẩn thận ban đầu.

Tuy nhiên, cách diễn đạt này cho phép cải thiện phương pháp: ta không còn phải chọn trước \(K\)! Thay vào đó, sau khi tìm được mỗi bút \(X\), ta quyết định hoặc tiếp tục tìm bút \(X+1\) theo cách trên, hoặc dừng và trả về hai bút cho tới lúc đó đã viết ít nhất. Ta gọi cải tiến này là dừng sớm (early stopping). Để quyết định tiếp tục hay trả về, ta có thể cài đặt một số heuristic, hoặc thực sự tính xác suất thành công bằng quy hoạch động mà trạng thái là lượng đã viết của từng bút tại thời điểm đã tìm được các bút \(0,1,\ldots,X\). Quy hoạch động này chỉ có \(32301\) trạng thái khi \(N=15\), nên có thể tính nhanh.

Viết cẩn thận kết hợp dừng sớm thành công trong khoảng \(64.2\%\) tổng số trường hợp nếu đưa ra các quyết định tối ưu do quy hoạch động nói trên tính được, nhờ đó qua Bộ kiểm thử 3 với biên an toàn thoải mái hơn. Một lần nữa, chúng tôi tin rằng còn nhiều cách khác cho Bộ kiểm thử 3.

Lời giải tối hậu

Cả ba cải tiến — viết cẩn thận, khám phá bút và dừng sớm — có thể được kết hợp trong một lời giải. Đây là quy hoạch động mà trạng thái một lần nữa là lượng đã viết bằng từng bút; ở mỗi trạng thái, ta xét ba lựa chọn:

1. Viết bằng bút còn lại ngoài cùng bên trái (nghĩa là chưa biết bút đó đã cạn) cho tới khi nó cạn.
2. Viết bằng tất cả bút theo thứ tự trái sang phải để tìm bút nhỏ nhất còn lại.
3. Trả về hai bút ngoài cùng bên phải chưa bị viết cạn.

Trong lời giải này, việc tính xác suất thành công của lựa chọn thứ ba rất dễ, vì mỗi bút còn lại có thể nằm ở bất kỳ vị trí khả dụng nào. Điều đó có nghĩa mọi cặp bút còn lại đều có cùng xác suất trở thành hai bút ta mang tới Nam Cực. Do đó, nếu hai bút được mang đi đã viết \(X\) và \(Y\) đơn vị, xác suất thành công đơn giản là số cặp bút còn lại có lượng mực ban đầu \(A\) và \(B\) thỏa \(A+B\ge N+X+Y\), chia cho tổng số cặp bút còn lại.

Quy hoạch động này có \(1343425\) trạng thái khi \(N=15\); vì vậy, nếu cài đặt cẩn thận, nó có thể chạy kịp thời gian ngay cả trên PyPy. Xác suất thành công của nó vào khoảng \(64.4\%\), dư sức qua Bộ kiểm thử 3.

Hơn nữa, chúng tôi đã so sánh xác suất thành công của cách này với xác suất tối ưu (được tính bằng phép vét cạn có ghi nhớ nói trên, sau rất nhiều thời gian chờ), và hóa ra với mọi \(N\le15\), lời giải này thực sự tối ưu. Vì vậy, chúng tôi nghi ngờ rằng nó cũng tối ưu với các giá trị \(N\) lớn hơn. Chúng tôi chưa có chứng minh cho điều đó, nhưng sẽ rất muốn được biết nếu bạn có một chứng minh! Dĩ nhiên, cả lời giải này lẫn chứng minh của nó đều không cần thiết để qua tất cả bộ kiểm thử của bài.

Ràng buộc và bộ chấm

Cuối cùng, hãy cùng chia sẻ một số cân nhắc đã được dùng khi chuẩn bị ràng buộc và bộ chấm cho bài này. Do bản chất ngẫu nhiên, tỷ lệ trường hợp giải thành công sẽ thay đổi đối với mỗi lời giải. Cụ thể hơn, nhờ Định lý giới hạn trung tâm, ta biết rằng với một lời giải có xác suất thành công \(P\) được chạy trên \(T\) trường hợp kiểm thử, tỷ lệ trường hợp giải thành công sẽ xấp xỉ phân phối chuẩn với trung bình \(P\) và độ lệch chuẩn \(\sqrt{P\times(1-P)/T}\). Vì thế, trong Bộ kiểm thử 1 và 2, độ lệch chuẩn vào khoảng \(0.35\%\); trong Bộ kiểm thử 3, nó vào khoảng \(0.15\%\).

Xét xác suất một mẫu từ phân phối chuẩn lệch khỏi trung bình một số lần độ lệch chuẩn nhất định, trên thực tế ta có thể xem như kết quả sẽ không bao giờ cách trung bình quá, chẳng hạn, năm độ lệch chuẩn. Điều này tạo ra một cửa sổ khoảng \(\pm1.75\%\) trong Bộ kiểm thử 1 và 2, và khoảng \(\pm0.75\%\) trong Bộ kiểm thử 3. Khi xác suất của một lời giải nằm ngoài cửa sổ này, nó sẽ luôn qua hoặc luôn trượt; còn trong cửa sổ, kết quả phụ thuộc vào may mắn ở một mức độ nào đó.

Cửa sổ may rủi này là không thể tránh khỏi, và kích thước của nó hầu như không phụ thuộc vào tỷ lệ thành công bắt buộc mà chỉ phụ thuộc vào số trường hợp kiểm thử \(T\). Vì vậy, không thể loại bỏ hoàn toàn tình huống tỷ lệ thành công của một lời giải rơi vào cửa sổ may rủi; khi đó có thể phải nộp cùng một lời giải nhiều lần mới được chấp nhận, và số lần cần thiết tùy thuộc vào may mắn. Tăng \(T\) sẽ thu hẹp cửa sổ, nhưng nếu tăng quá nhiều thì lời giải phải cực kỳ hiệu quả và một số cách tiếp cận có thể bị loại bỏ. Do đó, chúng tôi quyết định điểm đánh đổi tốt nhất cho Bộ kiểm thử 1 và 2 nằm quanh \(T=20000\), để những cách tiếp cận kém hiệu quả hơn vẫn có thể qua hai bộ này. Với Bộ kiểm thử 3, chúng tôi cho rằng điểm đánh đổi tốt nhất nằm quanh \(T=100000\): con số này phân tách tốt hơn các lời giải tối ưu hoặc gần tối ưu khỏi phần còn lại và thu hẹp cửa sổ may rủi, nhưng vẫn không đẩy giới hạn thời gian tới mức phi thực tế.

Chúng tôi chọn các tỷ lệ thành công bắt buộc như sau:

• Với Bộ kiểm thử 1, ngưỡng được chọn sao cho chiến lược fixed-K nằm ngoài cửa sổ may rủi và luôn qua.
• Với Bộ kiểm thử 2, ngưỡng được chọn sao cho cả viết cẩn thận lẫn khám phá bút đều nằm ngoài cửa sổ may rủi và luôn qua.
• Với Bộ kiểm thử 3, ngưỡng được chọn sao cho lời giải tối hậu gồm cả ba cải tiến nằm ngoài cửa sổ may rủi và luôn qua; trong khi các lời giải dùng viết cẩn thận kết hợp với một trong hai cải tiến dừng sớm hoặc khám phá bút nằm trong cửa sổ, nên có thể phải nộp nhiều lần nhưng không quá nhiều. Nếu hạ ngưỡng của bộ này thêm nữa, khám phá bút không kết hợp viết cẩn thận sẽ lọt vào cửa sổ may rủi. Tổng quát hơn, nếu dùng heuristic không chính xác thay vì quy hoạch động chính xác để quyết định dừng sớm, ta có cả một dải liên tục các lời giải, và một số lời giải trong đó chắc chắn sẽ rơi vào cửa sổ may rủi.

Một tính chất đặc biệt khác của bài này là bộ chấm không tất định, trong khi ở các bài tương tác thông thường, tính ngẫu nhiên trong mỗi bộ kiểm thử được cố định từ trước và việc nộp cùng một mã tất định luôn cho cùng một kết quả. Điều này là cần thiết để ngăn những cách tiếp cận trước tiên dùng vài lần nộp nhằm học một ít thông tin về các bộ kiểm thử, chẳng hạn cố ý làm lời giải nhận Sai, Lỗi khi chạy, Quá thời gian hoặc Quá bộ nhớ để truyền ngược hai bit thông tin. Thông tin ấy sau đó có thể được dùng để đạt xác suất thành công cao hơn.

Để thấy lượng thông tin nhỏ này có thể giúp đáng kể ra sao, hãy xét một lời giải có xác suất thành công thấp hơn mức bắt buộc năm độ lệch chuẩn. Với cách đơn giản là “nộp lại cùng mã”, trung bình sẽ cần hơn \(3\) triệu lần thử mới được chấp nhận, rõ ràng là không thực tế. Tuy nhiên, thay vào đó có thể làm như sau: nộp một lời giải chỉ viết bằng mọi bút cho tới khi chúng cạn, qua đó biết toàn bộ bộ kiểm thử. Sau đó, lời giải chạy cách dưới tối ưu vài triệu lần với các seed ngẫu nhiên khác nhau; theo lập luận trên, quá trình này sẽ tìm được một seed mà với nó, lời giải dưới tối ưu thực sự đạt tỷ lệ thành công bắt buộc. Bây giờ lời giải chỉ cần truyền ngược \(20\)–\(30\) bit tạo thành seed này; ngay cả với tốc độ hai bit mỗi lần nộp cũng chỉ cần \(10\)–\(15\) lần, hoàn toàn có thể thực hiện trong thời gian một vòng thi. Cuối cùng, chỉ việc nộp lời giải dưới tối ưu với seed ấy được ghi cứng và vượt qua bài.

Chúng tôi hy vọng phần này đem lại một chút hiểu biết về lý do bài toán được thiết kế như vậy, đồng thời xin lỗi vì vẫn còn khả năng thí sinh bị ảnh hưởng tiêu cực bởi cửa sổ may rủi hoặc tính không tất định của bộ chấm.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Vòng 3 — Pen Testing.