Loserinlife's blog

Knapsack queries
By Loserinlife, history, 11 months ago, In English

Given n objects the ith of each cost ai.

Given q queries in the form of s,a, b.

Count the number of subsets that contains a and b but sum of cost does not exceed s.

K is the sum of all Ai

N,Q,K<=4000

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

»
11 months ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

check trick number 3 probably something to do with this

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

    Did you mean trick 5 from that blog? Trick 3 has to do with finding possible subset sums — it doesn't work if you also need to count them. In contrast, trick 5 shows you how to remove elements from a knapsack, which seems exactly like what we would want to do.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      i was thinking that since k bounded to 4000 we can solve each query in k*root(k) which might work if we are given 2 seconds but yeah for counting it it doesnot work

      → Reply
»
11 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Notice that the number of subsets containing elements $$$a_i$$$ and $$$a_j$$$ with $$$\mathrm{sum} \le s$$$ is the same as the number of subsets of the set $$$\{a_1, a_2,\dots, a_n\}\setminus\{a_i, a_j\}$$$ with $$$\mathrm{sum} \le s - a_i - a_j$$$.

First, build an array such that $$$dp[i]$$$ is the number of subsets with $$$\mathrm{sum} = i$$$ for $$$i \in [1, k]$$$. This is a standard dp problem that can be solved in $$$O(nk)$$$.

Now for each query, we would like to remove those two elements from the dp array somehow efficiently. Turns out this is possible: you can remove a single element in $$$O(k)$$$ time. Check out trick 5 from this blog. After the elements have been removed, we have to calculate the sum of some prefix of the dp array. This can be naively done in $$$O(k)$$$. You can then add the two elemwnts back to the knapsack in $$$O(k)$$$ time.

This means that the total time complexity is $$$O(nk + qk) = O((n + q)k)$$$.

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

    I'm pretty sure that I saw this trick in a recent ABC contest on AtCoder.

    → Reply