Necessary and Sufficient

Following on from the Minimum Scalar Product problem in Round 1A, I next attempted the Milkshakes problem. This problem initially had me perplexed. You could solve the problem using brute force by generating a list of all possible permutations of the N flavours (malted or unmalted) and then assessing if any of these candidate solutions from the solution space was feasible, and from all the feasible solutions pick the one that had the least number of malted batches made. That would require evaluating 2^N candidate solutions which is NOT computationally practical given the range for N (1 < N < 2000).

I must admit I did check through a few reference books to get ideas on this one. From my studies in Operations Research I had a suspicion that this was similar to a boolean satisfiability problem and found reference to it in  this book on page 38 and 48. That told me that Cooke's Theorem had proved this to be NP-Complete. I know Google gives out challenging problems but I very much doubt they'd be evil enough to give out an NP-Complete problem to solve! Hence I kept looking for a solution. The problem was subtlety different from that problem in that each customer could have at most 1 malted flavour preference. That's the opening we need...

Intuition should tell us that we can improve drastically on the brute-force approach by adopting a greedy-like algorithm whereby we start with the best case scenario - no malted flavour batches made - and assess if this candidate solution is feasible (in that it satisfies all of the customers flavour preferences). If it is feasible then we know it will be optimal. If it is not feasible we need to amend our candidate solution such that it is closer to being feasible, and then start the process over.

In summary, our approach to solving the milkshakes problem is as follows:

1. Set first candidate solution to be all flavours made as unmalted
2. Check if current candidate solution is feasible. If it is then exit. The current solution will be optimal.
3. If current candidate solution is not feasible, and the unsatisfied customer has a malted flavour preference then change the candidate solution to make that flavour as malted rather than unmalted, and return to Step 2. NB: it should be noted that the customer who caused us to amend our candidate solution is now satisfied and can be removed from the list of customers to check on subsequent passes.
4. If current candidate solution is not feasible, and the unsatisfied customer has no malted flavour preference then it means that they had unmalted preferences that we were forced to make as malted to satisfy other customers. This implies that we cannot change our current candidate solution in such a way so as to satisfy the customer and hence no feasible solution exists. In this case exit and mark the problem as "Impossible".

Here's my C# code to do that:

using System;
using System.Collections.Generic;
using System.IO;

namespace GoogleCodeJam.MilkShakes
{
    class Program
    {
        public class Customer
        {
            private List<int> _likesUnmalted;   // a list of the customers preferences
            private int? _likesMalted = null;   // the index of the malted flavour they list

            public Customer(List<int> likesIndices, int? maltedIndex)
            {
                _likesUnmalted = likesIndices;
                _likesMalted = maltedIndex;
            }

            public int? LikesMaltedIndex
            {
                get {return _likesMalted;}

            }

            public bool IsSatisfied(bool[] batchMaltedFlags)
            {
                if (this.LikesMaltedIndex != null && (batchMaltedFlags[(this.LikesMaltedIndex ?? 0) - 1]))
                {
                    return true;
                }

                foreach (int i in _likesUnmalted)
                {
                    if (!batchMaltedFlags[i-1])
                    {
                        return true;
                    }
                }
                return false;
            }
        }

        static void Main()
        {
            StreamReader infile = new System.IO.StreamReader("input.txt");
            StreamWriter outfile = new System.IO.StreamWriter("output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                bool IsImpossible = false;

                int flavours = Int32.Parse(infile.ReadLine());
                bool[] isBatchMalted = new bool[flavours];

                int custCount = Int32.Parse(infile.ReadLine());
                List<Customer> customers = new List<Customer>();
                for (int i = 0; i < custCount; i++ )
                {
                    string[] data=(infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                    int flavoursLiked = Int32.Parse(data[0]); // number of flavours liked

                    List<int> likes = new List<int>();
                    int? likesMaltedIndex = null;

                    for (int j = 0; j < flavoursLiked; j++)
                    {
                        if (Int32.Parse(data[j * 2 + 2]) == 1)
                        {
                            likesMaltedIndex = Int32.Parse(data[j * 2 + 1]);
                        }
                        else
                        {
                            likes.Add(Int32.Parse(data[j * 2 + 1]));
                        }
                    }
                    customers.Add(new Customer(likes,likesMaltedIndex));
                }

                // for initial solution assume we only make unmalted flavours
                // and check for feasibility
                for (int i = 0; i < isBatchMalted.Length; i++ )
                {
                    isBatchMalted[i] = false;
                }

                bool madeMalted;

                do
                {
                    madeMalted = false;
                    foreach (Customer c in customers.ToArray())
                    {
                        if (!c.IsSatisfied(isBatchMalted))   // this customer isn't happy
                        {
                            if (c.LikesMaltedIndex == null)
                            {
                                // they must be unsatisfied because none of their prefered
                                // MALTED flavours have been made
                                IsImpossible = true;
                                break;
                            }
                            else
                            {
                                // they have a malted-preference so we MUST make that flavour
                                // as a malt rather than an unmalted 
                                madeMalted=madeMalted || !isBatchMalted[(c.LikesMaltedIndex ?? 0) - 1];

                                isBatchMalted[(c.LikesMaltedIndex ?? 0) - 1] = true;

                                // since this customer is now satisfied we can remove them
                                customers.Remove(c);
                            }
                        }
                    }
                } while (madeMalted);

                // write out the results
                if (IsImpossible)
                {
                    outfile.WriteLine(String.Format("Case #{0}: IMPOSSIBLE", caseNo));
                    //outfile.WriteLine();
                }
                else
                {
                    outfile.Write(String.Format("Case #{0}:", caseNo));
                    foreach (bool b in isBatchMalted)
                    {
                        outfile.Write(" " + (b ? 1 : 0));
                    }
                    outfile.WriteLine();
                }
            }

            infile.Close();
            outfile.Flush();
            outfile.Close();
        }
    }
}