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!