SSL-OI Summer Camp Miscellaneous Problem LOJ#6089 Little Y's Backpack Counting Problem Square Root Decomposition

LOJ #6089

This problem is a miscellaneous problem from the first night of the training camp. Due to my nature of loving to procrastinate, I only came to write the solution in the second week of the training camp.

Prerequisite Knowledge

Multiple Knapsack: Optimized with monotonic queue, achieving $O(NM)$ complexity.

Integer Partition: The number of ways to form $n$ integers from $k$ integers (with/without repetition), $O(NK)$ complexity DP.

Problem Statement

Backpack size is $n$, number of items is $n$, the weight of the $i$-th item is $i$, and the quantity is $i$.

Question: What is the number of ways to fill the backpack?

Correct Solution

For items greater than $\sqrt{N}$, it is equivalent to having no quantity limit. We use integer partition (with repetition) to find the answer.

For items less than $\sqrt{N}$, we use multiple knapsack to find the answer. Since the number of items is $\sqrt{N}$ and the backpack size is $N$, the complexity is $O(N\sqrt{N})$.