Phân tích: Dây thừng

Bài toán này có thể được giải theo nhiều cách khác nhau! Dưới đây là tập hợp những lời giải khác nhau mà chúng tôi đã gặp. Nếu lời giải của bạn không có ở đây, chúng tôi rất muốn được nghe về nó! Hãy đến nhóm Code Jam của chúng tôi và chia sẻ ý tưởng bạn yêu thích.

Để thống nhất, sau đây là một vài thuật ngữ sẽ được dùng xuyên suốt:

• “Chơi \((x,y)\)” nghĩa là nối cây \(x\) ở bờ bắc với cây \(y\) ở bờ nam.
• “Chơi tham lam” nghĩa là xét tất cả lựa chọn có thể và chọn một nước tối đa hóa điểm của bạn trong lượt hiện tại. Đôi khi chúng ta sẽ chọn ngẫu nhiên, đôi khi sẽ chọn một nước cụ thể trong số đó. Lưu ý rằng bộ chấm chơi tham lam (và chọn nước đi ngẫu nhiên).

Các tỷ lệ phần trăm bên dưới là giá trị xấp xỉ (thu được bằng thực nghiệm) và được làm tròn đến số nguyên gần nhất.

Chơi tham lam

... bằng cách chọn ngẫu nhiên (\(28\%\))

Chúng ta chỉ chọn nước đi ngẫu nhiên giống như đối thủ sẽ làm. Đây không phải một chiến lược tốt!

... bằng cách chọn không ngẫu nhiên (\(55\%\))

Chiến lược này hiệu quả đáng ngạc nhiên so với độ đơn giản của nó. Chỉ cần chơi giống đối thủ, ngoại trừ việc thay vì chọn ngẫu nhiên, ta chọn nước đứng đầu theo thứ tự từ điển—tức là chọn \((x,y)\) làm nhỏ nhất \(x\), rồi nếu hòa thì làm nhỏ nhất \(y\). Để hiểu vì sao nó hoạt động tốt, hãy đọc chiến lược “Đẩy họ về phía Đông!”, vì hai chiến lược hiệu quả vì những lý do tương tự nhau.

... bằng cách chọn không ngẫu nhiên và khởi đầu ở vị trí tốt hơn

Chiến lược này giống chiến lược trước, nhưng thay vì bắt đầu tại \((1,1)\), ta chọn một vị trí khác. Kết quả thay đổi tùy theo vị trí khởi đầu chính xác, nhưng chỉ riêng \((1,3)\) đã đem lại xác suất thắng \(75\%\). Hãy đọc phần dưới để hiểu vì sao điều này có ảnh hưởng lớn đến xác suất tổng thể như vậy.

Phản chiếu

Thử lần đầu (\(64\%\))

Chiến lược này dựa trên một ý tưởng đơn giản: nếu đội đối phương chơi \((x,y)\) thì ta sẽ chơi \((y,x)\). Vì sao đây là một ý tưởng tốt? Bởi nếu họ vừa chơi \((x,y)\) và ghi \(\Delta\) điểm, thì trong lượt của mình ta sẽ ghi \(\Delta + 1\) điểm, vì ta cũng cắt sợi dây họ vừa đặt cùng với tất cả những sợi dây khác mà đối thủ vừa cắt.

Tuy nhiên, có hai vấn đề. Vấn đề thứ nhất là ta đi trước nên không thể phản chiếu họ. Ta giải quyết bằng cách chơi \((1,1)\) làm nước đầu tiên. Nước này không ảnh hưởng đến phần còn lại của ván đấu vì không sợi dây nào khác có thể cắt nó. Vấn đề thứ hai là phải làm gì khi họ chơi \((x,x)\)? Trong trường hợp này, ta chỉ cần chơi nước \((z,z)\) còn hợp lệ có điểm số cao nhất.

Giờ đây với khởi đầu tốt hơn (\(82\%\))

Chiến lược này giống phần trước, ngoại trừ nước đầu tiên của ta là \((10,10)\) thay vì \((1,1)\). Vì sao cách này tốt hơn? Hãy nghĩ về những trường hợp ta làm tốt trong phiên bản trước. Nếu \(x \neq y\), ta hơn họ một điểm. Trường hợp duy nhất họ có thể gỡ điểm so với ta là khi \(x = y\) (hoặc đó là lượt cuối của họ). Bằng cách chơi \((10,10)\), ta khuyến khích họ chơi các nước trên đường chéo từ sớm, nhờ đó ta giành được một lợi thế khá tốt. Qua thực nghiệm, 10 là giá trị tốt nhất. Bắt đầu bằng \((2,2)\) cho \(72\%\), còn bắt đầu bằng \((25,25)\) cho \(64\%\).

Đẩy về phía Đông!

Thử lần đầu (\(50\%\))

Sẽ hữu ích nếu hình dung chiến lược này gồm ba giai đoạn: Giai đoạn \(1\) sắp xếp các sợi dây theo một cách hợp lý (và hy vọng giúp ta kiếm được một số điểm). Giai đoạn \(2\) chơi tham lam (và hy vọng duy trì lợi thế từ Giai đoạn \(1\)). Giai đoạn \(3\) là lượt cuối cùng của đối thủ (hy vọng điểm họ ghi trong lượt này là nhỏ).

Chiến lược này được gọi là “Đẩy về phía Đông!” bởi mục tiêu chính của ta là khiến Giai đoạn \(3\) tệ nhất có thể đối với đối thủ, và cách làm là bảo đảm nước cuối của họ nằm xa về phía đông nhất có thể. Nếu nước cuối của họ là \((x,y)\) thì số điểm tối đa họ có thể ghi là \((100-x) + (100-y)\). Đặc biệt, nếu có thể đẩy họ đến tận phía đông thì họ sẽ ghi 0 điểm.

Trong lần thử đầu tiên, Giai đoạn \(1\) đơn giản là “từ bỏ” lượt đầu bằng cách chơi \((1,1)\). Giờ ta bước vào Giai đoạn \(2\) (lưu ý rằng hiện tại hai bên đang hòa). Giai đoạn \(2\) sẽ chơi tham lam, và khi hòa thì ưu tiên lấy các cây ở phía tây nhiều nhất có thể (chẳng hạn chọn \((x,y)\) làm nhỏ nhất \(x+y\)). Với cách bố trí này, Giai đoạn \(3\) thường sẽ lấy một cây khá xa về phía đông. (Tuyệt!)

Khởi đầu tốt hơn (\(73\%\))

Nếu bắt đầu Giai đoạn \(1\) bằng \((2,2)\), đối thủ sẽ chơi \((1,x)\) (hoặc \((x,1)\)), ghi một điểm. Sau đó ta chơi \((1,3)\) (hoặc \((3,1)\)), ghi hai điểm. Lúc này, ta bước vào Giai đoạn \(2\) với lợi thế một điểm và đối thủ chỉ có thể ghi nhiều nhất một điểm trong lượt kế tiếp. Điều này cải thiện đáng kể xác suất thắng của ta.

Khởi đầu tuyệt vời (\(92\%\))

Gọi \(z\) là một số nguyên gần 10 (chẳng hạn 9, 10 hoặc 11). Hãy bắt đầu Giai đoạn \(1\) bằng \((z,z)\). Trong một vài nước tiếp theo, nước đi của đối thủ thường sẽ là \((x,y)\), trong đó một trong \(x\) và \(y\) là “nhỏ” (\(\lt z\)), còn số kia là “lớn” (\(\gt z\)). Ta có thể tiếp tục khuyến khích đối thủ thực hiện các nước “nhỏ”/“lớn” này bằng cách chọn các nước “ngắn” (\((x,y)\) hoặc \((y,x)\), trong đó \(x \lt 10\) nhưng lớn nhất có thể, còn \(y \gt 10\) nhưng nhỏ nhất có thể). Ta sẽ tiếp tục thực hiện các nước “ngắn”, qua đó càng khuyến khích đối thủ thực hiện các nước “nhỏ”/“lớn”.

Giả sử \(z=10\). Sau khi ta đã đi \(10\) nước (và đối thủ đã đi \(9\) nước), lúc này ta sẽ dẫn khoảng \(5\) đến \(10\) điểm (vì ta ghi xấp xỉ \(0+2+\cdots+18\), còn họ ghi xấp xỉ \(1+3+5+\cdots+17\)). Giai đoạn \(2\) gồm 90 nước tham lam của mỗi bên, trong đó ta thường duy trì lợi thế \(5\)–\(10\) điểm. Sau đó, trong lượt cuối của đối thủ, ta hy vọng họ ghi ít hơn 5 điểm vì đã bị đẩy quá xa về phía đông.

Lưu ý rằng cách chọn mọi nước đi (ngoại trừ nước đầu tiên) là \((x,y)\) sao cho trước hết tối đa hóa điểm, rồi làm nhỏ nhất \(x+y\) như trên cũng hoạt động khá tốt, bởi các nước có điểm tối đa thường sẽ cắt sợi dây \((z,z)\) của ta. Cách này cũng đạt tỷ lệ thắng khoảng \(92\%\).

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 2021, Chung kết thế giới — Ropes.