Necessary and Sufficient

Round 1B kicks off with a problem called "Crop Triangles". You are given a grid of integer-valued coordinates and need to find out how many distinct triangles can be formed that have an integer-valued midpoint. The obvious answer that comes to mind - to construct every possible triangle and chceck it's midpoint - is not really feasible as the problem size increases. With n grid points, and 3 points needed for a triangle, the number of triangles to examine in the brute force approach is: ⁿC₃ = n(n-1)(n-2)/6  so when n = 100,000 , the upper limit of n in the large problem, the triangle count is approx. 1 x 10¹⁵. Ergo the brute force approach is not feasible as it has running time O(n³). So how can we reduce the search space? A little bit of number theory comes in very handy here...

We are told that: (i) all coordinate pairs are integer values, (ii) the midpoint of a triangle must be an integer value, and (iii) the x- and y-coordinates of the midpoint are the average of the x- and y-coordinates of the 3 vertices respectively. So in mathematical notation (focusing on just the x-coordinates):

 

 
The same logic applies to the y-coordinates, so we need only examine the coordinates mod 3 that I'm referring to herein as the "adjusted coordinates". Adjusting with a modulus 3 operation effectively reduces the x- and y-coordinates to values in the range [0,1,2]. The following matrix depicts this graphically.

Since the sum of the adjusted coordinates for the x-values, and the y-values must equal 0 (the last equation given above) we only need to group together either:

1. Three x-values that have the same mod 3 result since 3x0=0, 3x1=3, 3x2=6 and 0,3,6 are all multiples of 3; or
2. Three x-values where each value has a different mod 3 result, since 0 + 1 + 2 =3 is a multiple of 3.

Obviously the same logic applies to the y-values, so our approach is to create a 3x3 matrix representing the mod 3 adjusted values. We iterate over all the points given and increment the appropriate counters in the matrix after we do the mod 3 operation on both the x- and y-values. Then we can examine the resulting 3x3 matrix of counts and produce the final answer by adding the number of 3-point combinations that can be made:

1. by items within each cell;
2. by items across columns for each row. This entails taking one point from each column for a given row in the matrix;
3. by items across rows for each column. This entails taking one point from each row for a given column in the matrix;
4. by items across rows and columns taking, at most, one point from each row and column in the matrix;

Here's my C# code:

using System;
using System.IO;

namespace CropTriangles
{
    class Program
    {
        static void Main()
        {
            string basePath = @"";
            var infile = new StreamReader(basePath + "large.txt");
            var outfile = new StreamWriter(basePath + "output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                // read in the input data
                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);

                int treeCount = Int32.Parse(data[0]);
                long A = Int64.Parse(data[1]);
                long B = Int64.Parse(data[2]);
                long C = Int64.Parse(data[3]);
                long D = Int64.Parse(data[4]);

                long x = Int64.Parse(data[5]);
                long y = Int64.Parse(data[6]);
                long M = Int64.Parse(data[7]);

                long[,] bins = new long[3, 3];
                long answer = 0;

                bins[x%3, y%3]++;

                for(int i=1; i<treeCount; i++)
                {
                    checked
                    {
                        x = (A*x + B)%M;
                        y = (C*y + D)%M;

                        bins[x % 3, y % 3]++;
                    }
                }

                for(int i=0; i< 3; i++)
                    for(int j=0; j< 3; j++)
                        answer += (bins[i, j] * (bins[i, j] - 1) * (bins[i, j] - 2) / 6);

                // get column and row products
                for (int i = 0; i < 3; i++)
                {
                    answer += (bins[i,0] * bins[i,1] * bins[i,2]);
                    answer += (bins[0,i] * bins[1,i] * bins[2,i]);
                }

                // get 
                for (int i = 0; i < 3; i++)
                    for (int j = 0; j < 3; j++)
                        for (int k = 0; k < 3; k++)
                            if (i !=j & i!=k & j!=k)
                                answer += (bins[0,i] * bins[1,j] * bins[2,k]);

                // write out the results
                outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, answer));
            }

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

The "Numbers" problem in Round 1A is considerably more devious than either Minimum Scalar Product, or Milkshakes problems. The problem is stated simply but the solution requires some innovative thinking to get around a precision problem. The fact that the exponent n can be up 2 x 10⁹ and √5 is irrational means that sufficient precision will be lost resulting in incorrect answers, or a stack overflow.

How do we know √5 is irrational? It can easily be proved using Proof by Contradiction.... Assume √5 is rational. In this case, by definition, it can be expressed as a quotient of 2 integers:

From number theory, we know that the fundamental theorem of arithmetic says that every positive composite integer has a unique prime factorization.  This theorem also implies that you can't have both an even and odd number of prime factors. It is for this very reason that the theorem is also referred to as the Unique Factorization Theorem.

If a and b are in lowest terms (as supposed), their squares would each have an even number of prime factors. 5b² has one more prime factor than b², meaning it would have an odd number of prime factors. This contradiction forces the supposition wrong, so √5 cannot be rational. It is, therefore, irrational.

The irrationality of √5 is the heart of the precision problem. If it were an integer value then we could easily apply a modulus 1000 to interim calculations to truncate unnecessary precision and avoid overflow. So one strategy which helps remove the irrational component is the use of conjugates. Consider the following:

From (3) we note that  ω = r - ω'.  Now the problem becomes:

From this we can draw several observations. The first is that r is an integer, which is to be expected - that's why we introduced the conjugate in the first place. To see this you only need to examine the binomal expansion of the terms and you'll note that the even exponents of both √5 and -√5 produce integers, and the odd exponents of √5 and -√5 produce irrational components that cancel each other out since there is both a positive and negative value for each term.

The second observation is that (3 - √5) = (3 - 2.2306) < 1  which implies that ω' < 1. Since this term is less than 1 (and gets smaller as n gets larger) we can effectively ignore it since we are only interested in the first three digits in front of the decimal place. We have now reduced our problem to an integer calculation that won't run into any precision issues:

What is now needed is a way to calculate r:

We know the result is an integer but the irrational √5 component is still in the mix. The clue to solving this is given above in the binomial expansion of r. Looking at that it should be clear that the expansion of the first term in r, will produce a result in the following form:

Here the subscript n is used to denote the resulting co-efficients of the rational and irrational components when the original term, (3 + √5), is raised to the power n. When n equals 0 or 1 the values of the coefficients, x and y, are easy to determine. For n=0, the result must equal 1 so clearly x₀=1 and y₀=0. Since we know x₀, y₀ it might be worthwhile deriving a recursive solution for higher values of n. To do this we can multiply the nth power by the original term and examine the results:

Equation (5) tells us that the co-efficients for the (n+1)-th power are a linear combination of the co-efficients for the n-th power. Since we know x₀ and y₀ we can solve for any value of n by using recursion. That is, repeatedly substituting values into (5) to get the desired x_n and y_n values. Here is the general equation in matrix form:

The astute reader will notice that we've only dealt with the first term in equation (4) above. However, the second term in (4) merely involves swapping the sign of the y_n component and in fact when the 2 terms are added together the y_n coefficients cancel out the irrational component leaving only the rational component (as shown earlier). Consequently,

So an elegant way to solve do this matrix multiplication problem quickly is to use fast exponentiation which requires far fewer (log n) operations than simple multiplication repeated n times. The difference between these two approaches is considerable when when n is very large.

Finally, here's some C# code to do this:

using System;
using System.IO;

namespace GoogleCodeJam.Numbers
{
    class Program
    {
        static void Main()
        {
            string basePath = @"";
            StreamReader infile = new System.IO.StreamReader(basePath + "large.txt");
            StreamWriter outfile = new System.IO.StreamWriter(basePath + "output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                // read in the input data
                uint n = UInt32.Parse(infile.ReadLine());

                int[,] coeffs = new int[2, 2];
                coeffs[0, 0] = 3;
                coeffs[0, 1] = 5;
                coeffs[1, 0] = 1;
                coeffs[1, 1] = 3;

                int[,] result = MatrixPow(coeffs, (int)n); ;

                double answer = (2 * result[0,0] + 999) % 1000;

                // write out the results
                outfile.WriteLine("Case #{0}: {1}", caseNo, answer.ToString("000"));
            }

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

        // sqare matrix exponentiation (using fast exponentiation)
        static int[,] MatrixPow(int[,] a, int n)
        {
            if (n == 1)
                return a;

            if (n % 2 == 0)
                return MatrixPow(MatrixMultiply(2, a, a), n / 2);
            else
                return MatrixMultiply(2, MatrixPow(MatrixMultiply(2, a, a), n / 2), a);
        }

        // square matrix multiplication
        static int[,] MatrixMultiply(int size, int[,] m1, int[,] m2)
        {
            int[,] result = new int[size, size];

            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    result[i, j] = 0;
                    for (int k = 0; k < size; k++)
                    {
                        checked
                        {
                            result[i, j] += (m1[i, k] * m2[k, j]) % 1000;
                        }
                    }
                }
            }
            return result;
        }
    }
}

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