Programming Team:  Mt Lebanon Programming Contest (2005 Fretterd Cup)
Mt Lebanon HS 2004-5
David Kosbie

Link to the Programming Team Home Page.

Contest Winner:  Di Ye


Contest Rules:

Questions, Answers, and Sample Solutions follow.  Please note that sample solutions are not necessarily the best solutions (and, in fact, there are no guarantees that they are even entirely correct!).


class Contest {

// Problem 1:  Define a "palinprime" as a palindromic number
// that is also prime.  How many palinprimes are less than 10 million?

// Problem 2:  To within one-millionth (0.0000001), find the three
// real roots of the polynomial:  g(x) = x^3 - 11519*x^2 + 4.36E7*x - 5.43E10?

// Problem 3:  If the 0th row of Pascal's Triangle is "1" and
// the 1st row is "1 1" and the 2nd row is "1 2 1", what is the average
// of the numbers in the 19th row?

// Problem 4:  Create a finite projective plane of order 2.  This
// is a 7x7 matrix of 1's and 0's such that:
//    a) each row contains exactly 3 ones
//    b) each column contains exactly 3 ones
//    c) each pair of columns share exactly 1 one in common
//    d) each pair of rows share exactly 1 one in common
// We will add one last requirement:  when viewed as a binary number,
// each row must be greater than the row above it.

// Problem 5:  Consider the integral points (also known as "lattice points")
// in the first quadrant (including the positive x and y axes).  Though it
// may be counterintuitive, it turns out that there are just as many of
// these points as there are positive integers!  To see this, we can number
// the points along the diagonals as follows:
// 1:  (0,0)
// 2:  (0,1)
// 3:  (1,0)
// 4:  (0,2)
// 5:  (1,1)
// 6:  (2,0)
// 7:  (0,3)
//...
// What is the 1234th point in this list, where (0,0) is the first point?

// Problem 6:  Consider the following expression:
//    10 + 17 + 26 + 145 + 16 + 22 + 18 + 7 + 202 + 103 + 2 + 24
// Rewrite this expression, replacing as many plus (+) signs with
// minus (-) signs as necessary so that the expression evaluates to zero (0).

// Problem 7:  The following expression can almost be used to find
// the day of week for any given calendar date:
//
//        int dayOfWeek = (day + 2*month + (int)(0.6*(month + 1)) + year +
//                                         (int)(year/4) + (int)(year/100) + (int)(year/400))%7;
//
// Unfortunately, the expression has an error in it!  Fix the error
// and use this to determine on what day of the week June 17, 3017 will fall.

// Problem N:  TIE-BREAKER.  This question will only be used as a tie-breaker.
// The Gettysburg Address begins:
// "Four score and seven years ago our fathers brought forth on this continent,
// a new nation, conceived in Liberty, and dedicated to the proposition that
// all men are created equal."  Write the smallest possible word search
// that you can which includes all these words horizontally, vertically,
// or diagonally.  There is no timer on this question, and preference is
// given to the word search with the smallest overall area (width times height).

// Answers:
// 1. 781 palinprimes in [ 0 , 10,000,000 ]
// 2.  z1 =~ 4707.272286199033
//     z2 =~ 3659.961672820011
//     z3 =~ 3151.766040980956
// 3. 26214.4
// 4. answers vary
// 5. (8,41)
// 6. 10 - 17 + 26 - 145 + 16 - 22 + 18 - 7 + 202 - 103 - 2 + 24
// 7. Tuesday
// N. answers vary

        //////////////////////////////////////////////////
        // Problem 1:  Define a "palinprime" as a palindromic number
        // that is also prime.  How many palinprimes are less than 10 million?
        //////////////////////////////////////////////////

        static int MAX_INDEX = 10000000;

        private boolean isPrime[] = new boolean[MAX_INDEX+1];

        void loadPrimes() {
                int i;
                for (i=2; i<=MAX_INDEX; i++) isPrime[i] = true;
                for (i=2; i<=MAX_INDEX; i++)
                        if (isPrime[i])
                                for (int j=i+i; j<=MAX_INDEX; j += i)
                                        isPrime[j] = false;
        }

        public boolean isPalindrome(int i) {
                int reverse = 0, original = i;
                while (i > 0) {
                        int digit = i % 10;
                        reverse = 10* reverse + digit;
                        i = i / 10;
                }
                return (reverse == original);
        }

        public void p1() {
                int palinprimeCount = 0;
                for (int i=0; i<=MAX_INDEX; i++)
                        if (isPrime[i] && isPalindrome(i))
                                palinprimeCount++;
                System.out.println(palinprimeCount);
        }

        //////////////////////////////////////////////////
        // Problem 2:  To within one-millionth (0.0000001), find the three
        // real roots of the polynomial:  g(x) = x^3 - 11519*x^2 + 4.36E7*x - 5.43E10?
        //////////////////////////////////////////////////

        double a3 = 1, a2 = -11519, a1 = 4.36E7, a0 = -5.43E10;

        double g(double x) { return a3*x*x*x + a2*x*x + a1*x + a0; }

        void p(double z) { System.out.println("g(" + z + ") = " + g(z)); }

        double findZero(double lo, double hi) {
                // use binary search to find zero to the required tolerance
                // note: g(lo) and g(hi) must be of differing signs
                boolean loNegative = (g(lo) < 0), loPositive = !loNegative;
                double mid = 0;
                while (hi - lo > 0.00000001) {
                        mid = (lo + hi) / 2;
                        if ((loNegative && g(mid) < 0) ||
                            (loPositive && g(mid) > 0))
                            lo = mid;
                        else
                                hi = mid;
                }
                return mid;
        }

        double findZero(double nearZero) {
                // find a distance delta such that g(lo = x-delta) and g(hi = x+delta)
                // have differing signs
                double lo, hi, delta = 0.01;
                while (true) {
                        lo = nearZero - delta;
                        hi = nearZero + delta;
                        if ((g(lo) < 0) != (g(hi) < 0))
                                // they differ in signs, so we're done
                                break;
                        delta *= 2;
                }
                return findZero(lo,hi);
        }

        public void p2() {
                // we know g(0) < 0 and g(infinity) > 0, so first find an x>0 such that g(x) > 0:
                double x = 1;
                while (g(x) < 0) x += x;
                // now use binary search to find zero to the required tolerance
                double z1 = findZero(0,x);
                // now factor this using synthetic division
                double a = a3;
                double b = a2 + z1*a;
                double c = a1 + z1*b;
                double d = a0 + z1*c;
                // note that d should be approximately zero, and. importantly:
                //     g(x) =~ (x - z1)(ax^2 + bx + c)
                // so now use the quadratic formula to find the two zeroes of (ax^2 + bx + c)
                double expr = Math.sqrt(b*b - 4*a*c);
                double nearZero2 = (-b + expr) / (2*a);
                double nearZero3 = (-b - expr) / (2*a);
                // note that z2 and z3 are nearly zeroes, so get them closer
                double z2 = findZero(nearZero2);
                double z3 = findZero(nearZero3);
                // print out our answers
                p(z1);
                p(z2);
                p(z3);
        }

        //////////////////////////////////////////////////
        // Problem 3:  If the 0th row of Pascal's Triangle is "1" and
        // the 1st row is "1 1" and the 2nd row is "1 2 1", what is the average
        // of the numbers in the 19th row?
        //////////////////////////////////////////////////

        public void p3() {
                int[] prevRow = new int[101], thisRow = new int[101];
                prevRow[0] = 1;
                int MAX_ROW = 19;
                for (int row=1; row<=MAX_ROW; row++) {
                        // copy row into prevRow
                        for (int k=0; k<row; k++) prevRow[k] = thisRow[k];
                        // now load new row based on sums from previous row
                        thisRow[row] = thisRow[0] = 1;
                        for (int k=1;k<row;k++) thisRow[k] = prevRow[k] + prevRow[k-1];
                }
                double sum = 0;
                for (int i=0; i<=MAX_ROW; i++) sum += thisRow[i];
                System.out.println(sum / (MAX_ROW+1));
        }

        //////////////////////////////////////////////////
        // Problem 4:  Create a finite projective plane of order 2.  This
        // is a 7x7 matrix of 1's and 0's such that:
        //    a) each row contains exactly 3 ones
        //    b) each column contains exactly 3 ones
        //    c) each pair of columns share exactly 1 one in common
        //    d) each pair of rows share exactly 1 one in common
        // We will add one last requirement:  when viewed as a binary number,
        // each row must be greater than the row above it.
        //////////////////////////////////////////////////
       
       
        //////////////////////////////////////////////////
        // Problem 5:  Consider the integral points (also known as "lattice points")
        // in the first quadrant (including the positive x and y axes).  Though it
        // may be counterintuitive, it turns out that there are just as many of
        // these points as there are positive integers!  To see this, we can number
        // the points along the diagonals as follows:
        // 1:  (0,0)
        // 2:  (0,1)
        // 3:  (1,0)
        // 4:  (0,2)
        // 5:  (1,1)
        // 6:  (2,0)
        // 7:  (0,3)
        //...
        // What is the 1234th point in this list, where (0,0) is the first point?
        //////////////////////////////////////////////////

        public void p5() {
                int points = 0;
                for (int diagonal=0; true; diagonal++)
                        for (int x=0; x<=diagonal; x++) {
                                int y = diagonal - x;
                                points++;
                                if (points == 1234) {
                                        System.out.println("(" + x + "," + y + ")");
                                        return;
                                }
                        }
        }

        //////////////////////////////////////////////////
        // Problem 6:  Consider the following expression:
        //    10 + 17 + 26 + 145 + 16 + 22 + 18 + 7 + 202 + 103 + 2 + 24
        // Rewrite this expression, replacing as many plus (+) signs with
        // minus (-) signs as necessary so that the expression evaluates to zero (0).
        //////////////////////////////////////////////////

        public void p6() {
                // not yet available, but here's an answer:
                // System.out.println(10 - 17 + 26 - 145 + 16 - 22 + 18 - 7 + 202 - 103 - 2 + 24);
   
                // try every possibility from 0 to 2^11 with each digit
                // in binary representing a plus (1) or a minus (0)

                int[] vals = {10,17,26,145,16,22,18,7,202,103,2,24};     
                for (int i=0; i<=2048; i++) {
                    int sum = vals[0];
                    int ops = i;
                    for (int j=1; j<vals.length; j++) {
                        if (ops % 2 == 1)
                            sum += vals[j];
                        else
                            sum -= vals[j];
                        ops /= 2;
                    }
                    if (sum == 0) {
                        // got it!
                        ops = i;
                        System.out.print(vals[0]);
                        for (int j=1; j<vals.length; j++) {
                            if (ops % 2 == 1)
                                System.out.print(" + " + vals[j]);
                            else
                                System.out.print(" - " + vals[j]);
                            ops /= 2;
                        }
                        System.out.println();
                    }
                }
        }

        //////////////////////////////////////////////////
        // Problem 7:  The following expression can almost be used to find
        // the day of week for any given calendar date:
        //
        //        int dayOfWeek = (day + 2*month + (int)(0.6*(month + 1)) + year +
        //                                         (int)(year/4) + (int)(year/100) + (int)(year/400))%7;
        //
        // Unfortunately, the expression has an error in it!  Fix the error
        // and use this to determine on what day of the week June 17, 3017 will fall.
        //////////////////////////////////////////////////

        public void p7() {
                int day = 17;
                int month = 6;
                int year = 3017;
                int dayOfWeek = (day + 2*month + (int)(0.6*(month + 1)) + year +
                                                 (int)(year/4) - (int)(year/100) + (int)(year/400))%7;
                System.out.println(dayOfWeek);
        }

        public Contest() {
                // MAX_INDEX = 50;
                // loadPrimes();
                p6();
        }

        public static void main(String[] args) { new Contest(); }
}