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

Contest Winner:  Di Ye

Contest Rules:
• "Standard" contest rules generally apply.
• You may use any non-human resources (books, internet, calculators, etc)
• Score based on (# of correct submissions) - 1/2(# of incorrect submissions).
• You may resubmit a problem as many times you wish.
• First tie-breaker:  Best answer on Problem N (the tie-breaker problem -- see below).
• Second tie-breaker:  Total time of correct submissions.

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.
// "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).

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

//////////////////////////////////////////////////
// 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];

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