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