muffins's blog

Question about Mo's algorithm with knapsack
By muffins, history, 6 years ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's fine, N is only 104...

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 :(

      → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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], and mid=(L+R)/2.Answer all queries with left<=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 and dp_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 between mid+1 and R.

For a query [left,right],we just merge the values of the 2 dp tables in O(x).Thus,we achieve O(nlogn*x+q*x).

→ Reply