Để đơn giản hơn ,ta tạm thời sẽ được phép chọn một hộp rỗng (không có quả bóng nào) (làm xong thì mình trừ \(1\) để bỏ trường hợp hộp rỗng này đi là được). Tiến hành chặt nhị phân kết quả, với mỗi giá trị \(N\) cần phải kiểm tra xem có thể tạo ra \(N\) hộp bóng phân biệt hay không, tương đương với bài toán chọn ra \(N\) điểm \((x, y)\) (\(x, y\) không âm) sao cho tổng các \(x\) không quá \(A\) và tổng các y không quá \(B\).

Có một chiến thuật tham lam đơn giản như sau: chọn ra hai tham số dương \(p, q\) và lấy \(N\) điểm có tổng \((px + qy)\) nhỏ nhất được điểm \((X, Y)\) với \(X\) là tổng hoành độ, \(Y\) là tổng tung độ của các điểm được chọn. Gọi \(f(p, q)\) là điểm nhận được từ hai tham số dương \(p, q\) (tức là \(f(p, q) = (X, Y)\)).

Với mỗi cặp tham số \((p, q)\) có thể có nhiều điểm \((X, Y)\) thỏa mãn (với các điểm có \((px + qy)\) bằng nhau có thể có nhiều cách chọn).

Vẽ các điểm \(f(p, q)\) với mọi cặp tham số dương \(p, q\) lên mặt phẳng, gọi bao lồi dưới của các điểm này là \(U\). Ta có thể chọn ra \(N\) điểm sao cho tổng hoành độ không quá \(A\) và tổng tung độ không quá \(B\) khi và chỉ khi điểm \((A, B)\) thuộc biên hoặc ở trên \(U\). Chứng minh: Giả sử ta có thể chọn được mà điểm \((A, B)\) nằm ở dưới \(U\) thì phải có một cặp tham số dương \(p, q\) sao cho \(f(p, q) = (x, y)\) và \(x\le A,y\le B\), từ đó ta có điểm \((x, y)\) nằm dưới \(U\) (vô lí).

Ta sẽ tìm hai điểm liên tiếp nhau trong \(U\) mà “kẹp” hoành độ \(A\) rồi kiểm tra xem điểm \((A, B)\) có nằm trên \(U\) hay không. Xét các điểm trong \(U\) theo hoành độ tăng dần dễ thấy tỉ lệ \(\frac{p}{q}\) của các điểm giảm dần nên có thể chặt nhị phân được.

Vậy ta giải quyết bài toán như sau:

• Đầu tiên chặt nhị phân số điểm có thể chọn \(N\).
• Với mỗi \(N\) ta chặt nhị phân tỉ lệ \((p, q)\) (khi cài đặt chỉ cần xét các cặp \(p, q\) thỏa \(p+q={10}^{10}+19\) cho dễ), gọi \(f(p, q) = (X, Y)\). Chia mặt phần thành \(4\) phần bởi \(2\) đường thẳng \(x = X\) và \(y = Y\). Nếu \((A, B)\) thuộc phần phải trên thì chắc chắn thỏa mãn, nếu \((A, B)\) thuộc phần trái dưới thì chắc chắn không thỏa mãn, nếu thuộc hai phần còn lại chúng ta tiếp tục chặt nhị phân.
• Với mỗi cặp \((p, q)\) chúng ta chặt nhị phân để tìm giá trị \(z\) nhỏ nhất sao cho số điểm điểm thỏa mãn \(px + qy \le z\) không bé hơn \(N\) và tính tổng \((X, Y)\) của những điểm đó.

Tóm lại lời giải này ta cần sử dụng ba chặt nhị phân lồng nhau 😊

Tổng độ phức tạp cho lời giải này là \(O(M^{1/3} \times log^3M)\) với \(M = max(A,B)\).