Test Set 1

Dùng quy hoạch động. Định nghĩa \(f(x,y)\) là số kiến lớn nhất có thể tạo thành một chồng hợp lệ khi chỉ xét từ con thứ nhất đến con thứ \(x\), và tổng cân nặng của chồng không vượt quá \(y\).

Để tính \(f(x,y)\), xét hai trường hợp:

• Không đặt con thứ \(x\) ở đáy. Bỏ qua nó, nhận \(f(x-1,y)\).
• Đặt con thứ \(x\) ở đáy. Phần chồng phía trên chỉ được dùng \(x-1\) con đầu, có tổng cân nặng không quá cả \(6W_x\) lẫn \(y-W_x\). Giá trị là \(f(x-1,\min(6W_x,y-W_x))+1\). Chỉ xét trường hợp này khi \(y\ge W_x\).

Lấy giá trị lớn hơn của hai trường hợp, hoặc chỉ trường hợp đầu nếu \(y<W_x\). Đáp án là \(f(N,\infty)\). Có \(O(N)\) giá trị \(x\), \(O(\max W)\) giá trị \(y\), và mỗi chuyển trạng thái tốn \(O(1)\), nên thời gian là \(O(N\max W)\). Cũng có một công thức DP tương tự \(f'(x,y)\) xét các con từ \(x\) đến \(N\) thay vì từ 1 đến \(x\).

Test Set 2

Trước hết tìm một cận \(K\) cho đáp án lớn nhất. Khi cân nặng mỗi con bị chặn bởi \(10^9\), để tạo chồng có nhiều con nhất có thể, ta tham lam dùng con nhẹ nhất có thể ở đáy. Một dãy cân nặng cực hạn có dạng

Dừng ngay khi con tiếp theo bắt buộc phải nặng hơn \(10^9\). Một đoạn mã ngắn cho thấy \(K=139\), nhỏ hơn rất nhiều so với \(N\).

Định nghĩa \(g(x,y)\) là tổng cân nặng nhỏ nhất của một chồng đúng \(y\) con khi chỉ xét \(x\) con đầu, hoặc \(\infty\) nếu không thể tạo chồng đó.

Lại xét hai trường hợp:

• Không dùng con thứ \(x\) ở đáy: giá trị là \(g(x-1,y)\).
• Dùng con thứ \(x\) ở đáy: trước hết chồng \(y-1\) con phía trên nhẹ nhất có cân nặng \(g(x-1,y-1)\). Nếu \(g(x-1,y-1)\le6W_x\), cách đặt này hợp lệ và tổng là \(g(x-1,y-1)+W_x\).

Lấy giá trị nhỏ hơn của hai cách, hoặc chỉ cách đầu nếu điều kiện sức mang không thỏa. Đáp án là số \(S\) lớn nhất sao cho \(g(N,S)<\infty\).

Có \(O(N)\) giá trị \(x\), \(O(K)\) giá trị \(y\), và mỗi trạng thái tốn \(O(1)\); tổng thời gian \(O(NK)\). Có thể dùng một mảng \(K+1\) và cập nhật số kiến theo thứ tự giảm dần, nên bộ nhớ là \(O(K)\).

Nguồn

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