# Code Jam 2008 Round 1A, Problem B: Milkshakes

Another day, another problem. Milkshakes it is! And it’s pretty straightforward:

You own a milkshake shop. There are N different flavors that you can prepare, and each flavor can be prepared “malted” or “unmalted. So, you can make 2N different types of milkshakes.

Each of your customers has a set of milkshake types that they like, and they will be satisfied if you have at least one of those types prepared. At most one of the types a customer likes will be a “malted” flavor.

You want to make N batches of milkshakes, so that:

• There is exactly one batch for each flavor of milkshake, and it is either malted or unmalted.
• For each customer, you make at least one milkshake type that they like.
• The minimum possible number of batches are malted.

Find whether it is possible to satisfy all your customers given these constraints, and if it is, what milkshake types you should make.

If it is possible to satisfy all your customers, there will be only one answer which minimizes the number of malted batches.

It is a classic Satisfiability problem, when you have a finite set of resources, receive several requests such as “want one of these” and have to decide which resource to hand to each request, in a way that every request gets attended. The “malted” can symbolize a cost-increasing modification of a resource, that we want to keep at minimum. In a case that two or more requests share a same need for a resource, they agree on sharing it, but only if the resource in on the same wanted state.

Being an NP-complete problem, there are conflicts of interest that we won’t be able to solve, and those we can inform as being “IMPOSSIBLE”. Python code as usual:

```for case in range(1,int(raw_input())+1): # For all test cases
shakes = int(raw_input()) * [0] # Get shake size and create unmalted list
customers = [] # Start empty customer list

for i in range(int(raw_input())): # For all customers
custList = map(int, raw_input().split(" ")) # Get the preferences
customer = []
for j in range(custList.pop(0)): # First value is number of shakes
flavor = custList.pop(0)-1 # First pair element is flavor index
malted = custList.pop(0) # Second element is malted preference
customer.append(flavor, malted) # Add preference to customer

customers.append(customer) # When done, add customer to list

impossible = False
solved = False
while not impossible and not solved: # While not finished
redo = False
for customer in customers: # Examine all customers
unsatisfied = []
for flavor, malt in customer: # Examine all their preferences
if shakes[flavor] == malt: # If satisfied, move to next customer
unsatisfied = []
break
else: # If unsatisfied, take note of it
unsatisfied.append([flavor, malt])

for flavor, malt in unsatisfied: # Check unsatisfied flavors
if malt == 1 and shakes[flavor] == 0: # Look for a possible malted preference
shakes[flavor] = 1 # Attend the malted preference
redo = True # Restart checking customers
break

if redo:
break

if len(unsatisfied) > 0: # If we've reached here, all insatisfactions are unmalted
impossible = True # Then we can't solve it
break

if not redo: # If we don't need to look into customers again
solved = True # Problem was solved (might still be impossible)

result = "IMPOSSIBLE" if impossible else " ".join(map(str, shakes)) # Decide result
print "Case #%d: %s" % (case, result) # Print the result
```

Validated, committed and pushed. 🙂 Another day, another problem. Cheers!

Advertisement