By shy_To_ask_from_main, history, 6 weeks ago,

Sam has recently started his own company known as Codage etoile. He cares a lot about his employees. Due to high work load, he buys some special types of energy boosters for his employees. There are N different types of energy boosters. Each energy booster provides the capacity Ci where Ci is the capacity of the ith booster. There are fi bottles of ith booster.

A person gets the cumulative capacity of all the boosters consumed. That is, if a person drinks 2 bottles, one of an energy booster with capacity 2 units and another of an energy booster with capacity 3 units, it will give him/her a cumulative capacity of 5 units. Sam wants to find the count of distinct capacities, between 1 to K (inclusive), which can be achieved on drinking these boosters. For sake of convenience, count of distinct capacities is labelled as 'CDC'.

Constraints:

$1 <= N <= 100$

$1 <= K <= 15*1e5$

$1 <= fi <= 1000,$ $where$ $1 <= i <= N$

$1 <= Ci <= 1e5,$ $where$ $1 <= i <= N$

Sample Input 1:

3 1 2 3 3 1 2 1 6

Sample Output 1: 6

I am not able to solve this problem, can someone please help.

• -16

 » 6 weeks ago, # |   +6 If anyone can solve this problem then please help me, I understand CF community doesn't like alts and interview stuff being done here but I don't know where else to ask and I am seriously confused how to pass this in time limit.
 » 6 weeks ago, # | ← Rev. 2 →   +3 We can also use the Trick 3 mentioned in this blog and the bitset knapsack optimization.Together both of them should probably work
 » 6 weeks ago, # |   +3 1) We make a simple knapsack dp and it works in O(N * f * K)2) We notice, that we don't need all fi different items. Instead of them we can use log(f) powers of 2. For example fi = 13 we will substitute with 1, 2, 4, 6. This will give us complexity of O(N * log(f) * K)3) We use bitset optimization and get O(N * log(f) * K / 64)
•  » » 6 weeks ago, # ^ |   0 how did you determine that for x=13 the elements 1,2,4,6 can be used to make any value <=13