Recently I came across a problem which resembles normal knapsack questions(items with weight, value) but this question has q offline queries. On each query, a left and right limit and x(maximum weight limit) will be given. So find maximum value of items between left item to right item while not exceeding weight of x. N <= 10000 & Q <= 50000 & X <= 2000, so naive won't be able to AC. I have heard of Mo's algorithm, and how to add and remove items, but I am unsure about removing items in knapsack. Can someone teach me or if not possible, suggest a new algorithm, thanks.
This problem can be solved by using Mo's algorithm, but the fastest time I could imagine is O(N * sqrt(n) * log(n)^2). It isn't very good.
That's fine, N is only 104...
Under N, I meant max(N, Q) or N + Q. And I was wrong, I forgot MAX_X / 64. So it's something like this O((N + Q) * sqrt(N) * log(something) ^ 2 * X / 64). Not fine :(
You can use divide&conquer technique,instead of Mo's(the same idea can be applied for both,but this works faster). Take a subsegment
[L,R]
, andmid=(L+R)/2
.Answer all queries withleft<=mid<=right
,and remove them, after this solve recursively for[L,mid]
and[mid+1,R]
.You can solve the queries by 2 separate "knapsacks".One for the left half,and one for the right half,like this:dp_left[i][j]
=maximum achievable value,if we take elements from the segment[i,mid]
with the sum of weights equal to j,with i between L and mid anddp_right[i][j]
=maximum achievable value,if we take elements from the segment[mid+1,i]
with weight,with sum of weights equal to j,and i betweenmid+1
andR
.For a query
[left,right]
,we just merge the values of the 2 dp tables inO(x)
.Thus,we achieveO(nlogn*x+q*x)
.