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()) *  # 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 = 
else: # If unsatisfied, take note of it
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
if len(unsatisfied) > 0: # If we've reached here, all insatisfactions are unmalted
impossible = True # Then we can't solve it
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!