Блог пользователя Loserinlife

Knapsack queries
Автор Loserinlife, история, 5 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
5 месяцев назад, # |
← Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

check trick number 3 probably something to do with this

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      5 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      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

      → Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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)$$$.

→ Ответить