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 =  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!