Test Set 1

Vì giới hạn của Test Set 1 rất nhỏ, ta có thể dùng vét cạn để kiểm tra mọi hướng, điểm xuất phát và cách liên kết các lỗ. Tuy nhiên, có vô hạn hướng và điểm xuất phát. Hãy tìm cách chỉ làm việc với hữu hạn khả năng.

Trước hết, để bóng chạm nhiều hơn hai lỗ, một số cặp lỗ phải nằm trên các đường thẳng song song với hướng đã chọn. Nếu không, tốt nhất ta chỉ có thể liên kết hai lỗ; bóng sẽ đi qua chúng và không chạm lỗ nào khác.

Do đó, khi chọn hướng đánh ban đầu, ta chỉ cần xét những hướng song song với các đường nối từng cặp lỗ.

Ngoài ra, điểm xuất phát chính xác không quan trọng. Ta có thể quyết định lỗ sẽ đi vào đầu tiên; bất kể hướng đánh nào, ta đều có thể đặt bóng sao cho nó đi vào lỗ đó trước mọi lỗ khác. Chẳng hạn, vì các lỗ luôn có tọa độ nguyên đôi một khác nhau, ta có thể chọn điểm xuất phát cách lỗ \(0.1\) theo hướng ngược với hướng đánh.

Bây giờ, ta có thể thử mọi lỗ xuất phát và mọi cách liên kết — chẳng hạn bằng quay lui đệ quy — rồi chọn tổ hợp chạm được nhiều lỗ nhất. Như vậy đủ để vượt qua Test Set 1.

Test Set 2

Tạm giả sử ta đã chọn hướng đánh. Hãy tính đáp án lớn nhất có thể với quyết định đó.

Hãy hình dung các đường thẳng song song với hướng đã chọn và đi qua tất cả các lỗ. Mỗi lỗ nằm trên nhiều nhất một đường như vậy. Ta gọi một đường là đường lẻ nếu nó chứa số lẻ lỗ (nhưng nhiều hơn một), và là đường chẵn nếu nó chứa số chẵn lỗ (ít nhất hai). Nếu có những đường chỉ chứa một lỗ, ta gọi các lỗ đó là lỗ đơn lẻ.

Ta cũng xét các lỗ trên mỗi đường theo thứ tự dọc theo hướng đã chọn.

Lưu ý rằng:

• Ta không thể chạm nhiều hơn hai lỗ đơn lẻ: một lỗ ở đầu và một lỗ ở tận cuối hành trình của bóng.
• Trong trường hợp tốt nhất, ta sẽ chạm tất cả các lỗ không đơn lẻ.

Gọi \(C_{odd}\) là tổng số lỗ trên các đường lẻ, \(C_{even}\) là tổng số lỗ trên các đường chẵn và \(C_1\) là số lỗ đơn lẻ. Khi đó đáp án không vượt quá \(C_{odd}+C_{even}+\min(2,C_1)\).

Để chạm hai lỗ đơn lẻ, ta phải chạm một số chẵn lỗ ở giữa chúng. Lý do là lỗ đơn lẻ đầu tiên phải là đầu vào của một lỗ sâu, còn lỗ thứ hai phải là đầu ra của một lỗ sâu khác. Mọi lỗ bóng chạm ở giữa hai lỗ đầu và cuối phải được liên kết thành từng cặp bằng lỗ sâu, nên số lỗ phải chẵn. Vì thế, nếu số lỗ không đơn lẻ là số lẻ thì ta không thể chạm hai lỗ đơn lẻ; khi đó đáp án không vượt quá \(C_{odd}+C_{even}+\min(1,C_1)\).

Như ta sẽ thấy, các cận trên này thực sự đạt được, nên đáp án là:

• \(C_{odd}+C_{even}+\min(1,C_1)\) nếu \(C_{odd}+C_{even}\) lẻ.
• \(C_{odd}+C_{even}+\min(2,C_1)\) nếu \(C_{odd}+C_{even}\) chẵn.

Tính chẵn lẻ của \(C_{odd}+C_{even}\) giống tính chẵn lẻ của \(C_{odd}\), vì \(C_{even}\) luôn chẵn.

Hãy dựng cách liên kết cho trường hợp \(C_{odd}\) chẵn và \(C_1\) lớn hơn \(1\):

1. Nối một lỗ đơn lẻ với lỗ đầu tiên của một đường chẵn bất kỳ.
2. Nối các lỗ còn lại trên đường đó thành từng cặp liên tiếp (lỗ cuối cùng sẽ không được nối).
3. Nối lỗ cuối cùng trên đường đó với lỗ đầu tiên của một đường chẵn khác, rồi lặp bước 2 và 3 đến khi chỉ còn các đường lẻ chưa được sử dụng.
4. Nối lỗ cuối của đường chẵn cuối cùng với lỗ đầu của một đường lẻ bất kỳ.
5. Nối lỗ thứ hai của đường lẻ đó (A) với lỗ thứ hai của một đường lẻ khác (B).
6. Nối lỗ cuối của đường B với lỗ đầu của đường B.
7. Nối lỗ cuối của đường A với lỗ đầu của một đường lẻ khác.
8. Nối các lỗ còn lại của đường A thành từng cặp liên tiếp.
9. Nối các lỗ còn lại của đường B thành từng cặp liên tiếp.
10. Lặp các bước 5–9 đến khi mọi đường lẻ được sử dụng. Khi không còn đường lẻ nào, nối lỗ cuối của đường lẻ cuối cùng với một lỗ đơn lẻ chưa dùng.

Có thể dễ dàng điều chỉnh cách này cho các trường hợp khác, khi \(C_{odd}\) lẻ và/hoặc \(C_1\) nhỏ hơn \(2\).

Tóm lại, ta có thể tận dụng toàn bộ các đường lẻ và đường chẵn, cùng nhiều nhất hai lỗ đơn lẻ.

Để tính số lỗ trên mỗi đường đối với một hướng cho trước, ta có thể duyệt mọi cặp lỗ có thứ tự và tìm phương trình đường nối chúng dưới dạng \(y=mx+y_0\). Với mỗi \(m\), ta lưu số lần mỗi \(y_0\) xuất hiện. Số này bằng số cặp lỗ trên đường đó, và từ đó ta tính được số lỗ. Ta chỉ cần làm việc này một lần vì sẽ thu được số lượng cho mọi hướng cần xét.

Bây giờ, ta duyệt mọi hướng và tính đáp án cho từng hướng như trên bằng cách duyệt tất cả các đường song song với hướng hiện tại. Đáp án cuối cùng là giá trị lớn nhất trên mọi hướng.

Mặc dù có \(O(N^2)\) hướng và \(O(N)\) đường song song với một hướng, tổng số đường của tất cả các hướng là \(O(N^2)\), vì mỗi đường có thể song song với hai hướng (đối nhau). Vì vậy, tổng độ phức tạp thời gian của lời giải khi cài đặt tối ưu là \(O(N^2)\), dù các cài đặt chậm hơn cũng có thể vượt qua.

Dữ liệu kiểm thử

Chúng tôi khuyên bạn nên luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

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 2 — Wormhole in One.