Test Set 1

Hai nhận xét thu hẹp đáng kể bài toán:

• Không thể đặt dốc ở cột ngoài cùng trái hoặc phải, nên hai viên thả ở đó phải rơi thẳng xuống đáy. Nếu \(B_1=0\) hoặc \(B_C=0\), đáp án là IMPOSSIBLE. Phần sau sẽ cho thấy đây là trường hợp bất khả thi duy nhất.
• Khi \(C=5\) là lớn nhất và hai cột biên đều nhận ít nhất một viên, chỉ còn cách phân phối 3 viên vào 5 cột. Có 35 phân hoạch; loại các cặp đối xứng gương chỉ còn 19 trường hợp khác nhau. Với \(C\) nhỏ hơn còn ít hơn.

Vì Test Set hiển thị, có thể thử nghiệm ngoại tuyến bằng mô phỏng hoặc dựng tay bố cục cho mọi trường hợp. Tuy nhiên, cách tổng quát dưới đây tránh công việc đó.

Test Set 2

Xét đường đi của các viên. Khi hai đường gặp nhau, hai viên phải kết thúc trong cùng một cột. Do mẫu dốc \/ bị cấm, các đường không thể cắt xuyên qua nhau.

Vì thế, nếu cột trái nhất nhận đúng \(K\) viên thì đó bắt buộc là \(K\) viên xuất phát từ \(K\) cột trái nhất. Nếu một viên đến từ cột \(K+1\) chẳng hạn, đường của nó phải cắt mọi đường của \(K\) viên trái hơn, khiến cả \(K+1\) viên đều về cột trái nhất, mâu thuẫn.

Xem cột \(i\) vừa là nguồn của một viên, vừa là đích tiềm năng của \(B_i\) viên khi \(B_i>0\). Quét dãy \(B\) từ trái sang phải. Mỗi khi gặp \(B_i>0\), gán \(B_i\) cột nguồn chưa dùng nằm trái nhất cho đích \(i\). Ví dụ với

3 2 0 0 0 0 2 1

ta gán đoạn nguồn \([1,3]\) cho đích 1, \([4,5]\) cho đích 2, \([6,7]\) cho đích 7 và \([8,8]\) cho đích 8. Ánh xạ này bị bắt buộc bởi thứ tự không giao nhau.

Bắt đầu với một hàng trên cùng trống rồi thêm dốc và hàng khi cần. Với mỗi đoạn nguồn \([l,r]\) gán cho đích \(i\):

• Nếu \(l<i\), vẽ \(i-l\) dốc \, bắt đầu ở hàng trên cùng tại cột \(l\), rồi đi chéo xuống phải từng ô. Dòng dốc này bắt tất cả bi trong đoạn cần đi sang phải, nên không cần xử lý riêng từng viên.
• Nếu \(r>i\), tương tự vẽ \(r-i\) dốc / từ đầu mút phải, đi chéo xuống trái.
• Những nguồn đã ở đích không cần dốc.

Cuối cùng, nếu hàng dưới cùng hiện có dốc thì thêm một hàng trống bắt buộc. Không có nguy cơ tạo mẫu \/ trong một đoạn vì không vị trí đích nào gây ra mẫu ấy; các đoạn nguồn của các đích khác nhau không xen kẽ nhau.

Để chứng minh tối ưu, ánh xạ nguồn–đích đã được chứng minh là duy nhất. Gọi

Một viên lệch \(d\) cột cần ít nhất \(d\) hàng có dốc, vì mỗi hàng chỉ có thể tác động lên nó một lần và mỗi dốc chỉ dịch nó một cột. Do đó cần ít nhất \(h\) hàng dốc cộng một hàng cuối trống. Cấu trúc trên dùng đúng \(h+1\) hàng, nên tối thiểu. Trong ví dụ 3 2 0 0 0 0 2 1, đoạn nguồn \([4,5]\) được ánh xạ tới cột đích \(2\). Đầu mút xa nhất là cột \(5\), nên độ lệch là \(|5-2|=3\). Vì thế riêng viên bi từ cột \(5\) đã buộc đồ chơi phải có ít nhất \(3\) hàng dốc, cộng thêm hàng đáy trống bắt buộc. Cách dựng hiển thị đúng \(3\) hàng có dốc rồi một hàng trống, nên đạt cận dưới với dấu bằng và thực sự tối ưu.

Với ví dụ 3 2 0 0 0 0 2 1, cấu trúc tạo ra là:

.././\..
././....
../.....
........

Thuật toán tính các đoạn và \(h\) trong \(O(C)\); nếu lưu toàn bộ lưới thì thời gian và bộ nhớ đầu ra là \(O(C^2)\).

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2018, Round 2, bài Falling Balls; kho Google Coding Competitions (Apache-2.0).