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();
        }
    }
}

There has been much written about the merits and social responsibility of off-shoring programming tasks to India, China and various Eastern block countries. Websites like oDesk and eLance seems to get considerable coverage in the blogosphere since managers in charge of technical teams drool when they see hourly rates for seemingly well-skilled programmers at around 15 USD/hour - if you go with a provider that does hourly billing. As we all know this is considerably lower then the hourly rates you'd need to pony up to attract better-than-average programmers in San Francisco, New York, Sydney, Singapore or London, regardless of the current market conditions for local programming talent, so on the surface of things it may seem like a simple decision: retain a core architecture team of highly-competent engineers and architects in your Development HQ who do the high-level design, and outsource the lesser work to offshore freelancers or labor hire firms. Then sit back and watch your monthly cash burn rates tail off, your delivery schedules and engineering budgets gravitating back towards those quarterly projections you presented at the last board meeting, thus stretching your seed capital as far as possible.

But is it that simple? To quote a well-known technical response... "it depends"!

Yes the hourly labor rates will be cheaper but you are trying to minimize the total cost of the project. Thus cost savings will only materialize if:

1. the time required to do the assigned tasks to the required level of quality is close to the estimates given plus an overrun buffer (assuming a fixed-fee, fixed-deadline arrangement wasn't used); and
2. the individuals engaged to do the work are suitably skilled, motivated and communicative that there is a reasonable chance that (1) happens [good luck trying to negotiate penalty rates with Vladimir in the Ukraine in case he misses your deadline because his priorities suddenly switch to his impending doctoral thesis review at the 12th hour!]; and, most importantly,
3. a clear, unambiguous specification and/or regular guidance is available to the individuals engaged.

Some may scoff at this last point. "Of course we know clearly what we want to do!" I can hear you saying. Well consider that many development teams these days prefer Agile development methodologies where, unlike "waterfall" methodologies, the focus is more towards short-term objectives and proceeding in such a way that enables product changes throughout the development process to be more easily accommodated. That methodology didn't become popular because we all know exactly what we want and therefore never have to rework part of the specification document! Scope creep does happen, and in the world of Internet development even the best planned projects might need to be reviewed when a competing product or service appears unexpectedly on the market. 

That issue aside, these may not seem like large hurdles to overcome and if you have a very clear idea about the requirements for the particular task you are considering outsourcing then you can seriously contemplate if, at a strategic level, you should be outsourcing this piece of work or not. It would be prudent to consider the following issues:

1. Is this a critical piece of your system? And are you planning on supporting it in-house or will you rely on the original provider? Losing control of your "system smarts" is not a well proven strategy.
2. Is the project an add-on to your system that can be done without intimate knowledge of the system internals?
3. Will the external developers need access to all of your existing source code, and knowledge base, to be able to complete the assigned project? If so, are you willing to give access to this to 3rd parties before a certain level of trust is developed?

As you can see there are many factors to consider, and for some types of projects off-shoring can be a highly effective practice. But, as you probably already know, selective off-shoring is the answer. It's all about knowing which projects are good candidates for outsourcing !