Subtask 1:

Có thể dễ dàng giải được bằng các thuật trâu bò như quay lui, vét cạn các kiểu. Mỗi gói kẹo có hai trạng thái là chọn và không chọn, nếu không chọn thì gói đó sẽ thuộc về _minhduc, còn chọn thì sẽ thuộc về Shiba. Ta xét tất cả các tổ hợp trạng thái và có độ phức tạp là \(O(2^𝑁)\).

Subtask 2:

Giải bằng quy hoạch động dạng Bài toán ba lô. Xét \(dp[i][j]\) với \(i\) là số gói kẹo Shiba lấy, \(j\) là tổng của tất cả các viên kẹo đó. Giờ \(dp[i][j]\) sẽ nhận một trong hai giá trị là \(0\) hoặc \(1\). Là \(1\) khi có một cách lấy kẹo sao cho i gói kẹo của Shiba có tổng số kẹo bằng \(j\), còn \(0\) là khi không có cách nào. Giả sử Shiba có \(i\) gói kẹo với tổng số kẹo là \(j\), thì công thức truy hồi như sau: \(𝑑𝑝[𝑖][𝑗] = 1\) khi tồn tại \(𝑑𝑝[𝑖 − 1][𝑗 − 𝑎𝑖] = 1\) với \(𝑎_𝑖 \le 𝑗\) hoặc \(𝑑𝑝[𝑖 − 1][𝑗] = 1 \ \ 𝑑𝑝[𝑖][𝑗] = 0\) trong các trường hợp còn lại.
Tức là nếu tồn tại một cách nhận được \(j\) viên kẹo với \(i-1\) gói kẹo thì sẽ tồn tại một cách để có \(𝑗 + 𝑎_𝑖\) viên kẹo với i gói kẹo.
Giờ về việc in ra kết quả, ta nhận xét kết quả luôn có dạng là tổng số kẹo của một bên nhỏ hơn \(sum/2\), ta sẽ giả sử là Shiba, vì Shiba luôn nhường nhịn bạn thân của mình. Thì số gọi kẹo của cả hai không thể đồng thời lớn hơn \(sum/2\) nên phải có một người nhỏ hơn hoặc bằng \(sum/2\), đặt bằng \(a\), thì ta có số kẹo của người còn lại là \(sum-a\), vậy kết quả là \(|(sum-a)-a| = |sum-2*a|\). Vậy ta chỉ cần tìm \(a\) lớn nhất sao cho \(a \le sum/2\) và \(dp[n][a] = 1\) thôi.
Độ phức tạp \(O(N \times sum)\)

Subtask 3:

Ý tưởng giống subtask 1, ngoài trừ việc thay vì chạy \(O(2%𝑁)\) thì ta phân dãy \(𝑁\) kẹo ra thành \(2\) tập hợp \(A\) và \(B\), và chạy \(O(2^{N/2})\) để sinh ra tất cả tổng các số kẹo. Với hai tập hợp tổng các số kẹo đó, ta lấy tập \(A\), và chặt nhị phân trên tập \(B\) sao cho \(a_i + b_i \le sum/2\).
Độ phức tạp là: \(O(2^{N/2} \times 2 \times log(2^{N/2}))\).

Subtask 4:

Ý tưởng giống subtask 2, nhưng với độ phức tạp của code subtask 2 thì chắc chắn sẽ TLE, do đó ta sẽ sử dụng kĩ thuật bit. Để ý, thay vì duyệt từ \(dp[i][1]\) đến \(dp[i][sum]\) (với sum là tổng số kẹo của tất cả gói kẹo) thì ta có thể nhìn nhận dãy \(dp[i]\) dưới dạng một dãy bit \(01010101…\) và chỉ cần thực hiện thao tác left shift và OR lên là xong. Cụ thể như sau:
\(𝑑𝑝[𝑖] = (𝑑𝑝[𝑖 − 1] ≪ 𝑎𝑖) | 𝑑𝑝[𝑖 − 1]\) với \(𝑎_𝑖 \le 𝑗\).
\(𝑑𝑝[𝑖 − 1] ≪ 𝑎_i\) thao tác này sẽ xê dịch tất cả các bit lên \(𝑎_𝑖\) bit, cũng có nghĩa là tất cả các bit \(1\) tại vị trí mới chính là các \(dp[i][j] = 1\) (trạng thái đạt được từ trạng thái \(dp[i-1][j-a_i]\)). Còn \(| 𝑑𝑝[𝑖 − 1]\) dùng để bổ sung thêm các trạng thái bằng \(1\) của bước trước đó. Ví dụ:
\(100 << 2 = 10000\)
\(10000 | 100 = 10100\)
Và \(10100\) chính là dãy bit thể hiện các trạng thái của \(𝑑𝑝[𝑖]\).
Cách in ra kết quả thì giống subtask 2. Còn về cách để thực hiện các thao tác như trên thì ta dùng cấu trúc dữ liệu bitset.
Sử dụng bit giúp code nhanh gấp \(32\) lần bởi đặc tính tốn ít dữ liệu và thao tác nhanh của bit.
Vậy độ phức tạp của code AC subtask này bằng subtask 2 nhưng chia \(32\).