Tag Archives: 2008

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!

Code Jam 2008 Round 1A, Problem A: Minimum Scalar Product

1 Reply

Hey there, since things are getting a little more calm, I can focus once more to solve some nice Code Jam problems. And here we go, from the first official tournament round: Problem A: Minimum Scalar Product. It says:

You are given two vectors v₁=(x₁,x₂,…,x_n) and v₂=(y₁,y₂,…,y_n). The scalar product of these vectors is a single number, calculated as x₁y₁+x₂y₂+…+x_ny_n.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

There’s a catch on the text, that made me quite confused. In case you didn’t notice, it’s that damn TWO PERMUTATIONS part. Despite getting the sample results right, when the bigger test cases came, I wasn’t able to get the smallest results right! Because, guess why, I was only doing two value permutations, because to me, the text says so!

Anyway, took a look into the results and saw that participants were simply not considering this limitation and outputting the minimum possible value anyway and to hell with it. If Google thinks this would be the correct approach, who am I to judge! 😀 Just sort both arrays, invert one of them, iterate calculating the MSP and you’re done! Python code, as usual:

for case in range(1,int(raw_input())+1): # For all test cases
  size = int(raw_input())                # Since we're informed, save array size
  x = map(int, raw_input().split(" "))   # Get all X parameters
  y = map(int, raw_input().split(" "))   # Get all Y parameters

  x.sort()                               # Sort both vectors
  y.sort()                               # And sort-reverse Y
  y.reverse()                            # So we can match the bigger/smaller values

  msp = 0
  for i in range(size):                  # For all the array's len
    msp += x[i]*y[i]                     # Sum "forward" on X and "backwards" on Y

  print "Case #%d: %d" % (case, msp)     # Print the sum

And that’s it! Quick and easy, despite the text hiccup. Githubbin’ it. See you!

Automalia: done it is!

Tag Archives: 2008

Floating point precision, bad numbers

Code Jam 2008 Round 1A, Problem B: Milkshakes

Code Jam 2008 Round 1A, Problem A: Minimum Scalar Product