How to Solve ‘Chemicals’ in CodeFights

The Problem:

Abby is a researcher at a company that makes chemical solutions. Her boss left her with a difficult task late Friday afternoon, and waltzed off into the weekend.

Abby has a hazardous liquid that reacts with oxygen by exploding. Her task is to distribute the liquid between special containers. The company buys containers of specific sizes in bulk, so she has access to a lot of containers of each size.

Since the liquid is explosive, Abby needs to fill the containers full to the exact capacity. Preparing the containers is tricky, so Abby wants to use as few containers as possible. Given the totalAmount of liquid and the set of container sizes containers, find the total number of containers she will need.

If there’s no way to distribute the liquid as described above, return -1 instead.

Example

  • For totalAmount = 18 and containers = [1, 2, 5, 10],
    the output should be
    Chemicals(totalAmount, containers) = 4.Abby has access to containers with sizes 10, 5, 2, and 1, and will use one container of each size.
  • For totalAmount = 9 and containers = [1, 4, 6],
    the output should be
    Chemicals(totalAmount, containers) = 3.Abby can use two containers of size 4 and one container of size 1.

Input/Output

  • [time limit] 4000ms (py)
  • [input] integer totalAmountThe amount of chemicals.Guaranteed constraints:
    0 ≤ totalAmount < 5 · 104.
  • [input] array.integer containersA sorted array of distinct integers, denoting the container sizes.Guaranteed constraints:
    1 ≤ containers.length ≤ 15,
    0 ≤ containers[i] ≤ 1000.
  • [output] integerThe minimum number of containers needed to distribute the liquid. Return -1 if there’s no way to distribute the liquid.

The Solution:

def Chemicals(totalAmount, containers):
    totalAmount+=1
    d=[999999]*totalAmount
    d[0]=0
    for x in containers:
        if x <totalAmount:
            d[x]= 1
    for x in range(totalAmount):
        for y in containers:
            if x-y>0:
                d[x]= min(d[x],d[x-y]+1)
    if d[-1]==999999:
        return -1
    return d[-1]

The Explanation:

Knapsack Problem, you can search for this term and learn more about it. In essence, create an array d. Each element of d shows the best solution up to that index. The idea follows this:

If I can get maximum value of 90 at 10 weight, and I have an item with weight 2 and value 10, then, at the best case, I can have 100 value at 92.

Reversing this, we want to minimize our weight at a given value. And slightly modifying the problem, we want to minimize number of containers at a given value.

If I can use minimum 5 containers to store 90, and I have containers of size 5, then I can have minimum 6 containers for size 95.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s