May Monthly Contest Results

[PJYelton]

Results for the May contest are here, and it’s not even June yet, go figure

Easy Problem

This one at first glance seems difficult but it turns out after just a few sample cases it becomes pretty obvious what the pattern is. There’s basically three different scenarios that your program would need to account for:

1) No hamburgers at all, in which case just return 0 minutes.
2) Less hamburgers than pansize in which case it will always take 10 minutes
3) More hamburgers than pansize in which case you always fry with the following instructions.

Think of the hamburgers as a long line. Fry the first “panSize” number of hamburgers, place them at the end of the line and add five minutes. Fry the next “panSize” number of hamburgers. If the hamburger is done, take it out of line, otherwise place to end of line. Add five minutes. Continue until there are no more hamburgers.

You’re program could have either simulated this process explicitly, or as most people realized it can be solved with a simple equation of (5 minutes * 2 sides * numHamburgers / panSize) rounded up. However you decided to round up was up to you.

Here are the entries, I’ll refrain from giving official scores I’ll just announce that only one person got all test cases correct.

[PJYelton]

Congrats to Kryptkat for the most interesting entry, an actual working Windows program! Unfortunately the results weren’t correct, made me laugh though

 /* VeggieBurgerCook.c By KryptKat /
/* instructions.txt */
/*
1. If all else fails read the instructions.txt

2. Your new proggie was compiled with Borland C 5.5 Command Line Tools.

3. Your new proggie was designed to run on a Windows box.

4. Getting Started. The first time your proggie runs she may miss the litter box. This is normal. You will notice a "calculate" button. Below that you will see an edit box. Below that you will see two small entry boxes. This is where you enter your pansize and the number of veggie burgers that you are going to cook. Your new proggie will assist you to determine just how long it will take. Most throughly cooked veggie burgers should take 20 minutes but yours for some strange reason only takes five minutes on each side. DISCLAIMER: If they <your veggie burgers> are suvearly under cooked it is not meow fault!

5. When comfortable with your new proggies opperation you may notice that the numbers you entered remain which will let you change or keep the numbers to do another calculation. Just hit the button again to reset. When "calculate" is pressed again your new calculations will appear.

6. Feeding your new proggie. Do not try to feed your new proggie with the veggie burgers. There is special proggie food for growing proggies <veggie proggie food>. Milk is good for your new proggie.

7. Tucking your new proggie in for the night. Most proggies enjoy a good night sleep. When you are ready for your proggie to go to sleep press the red "x" and your proggie will fall asleep quickly.

8. Remember to care for your new proggie every day./*

/* VeggieBurgerCook.c By KryptKat */


#include<stdio.h>
#include<windows.h>

#define MIN WM_USER + 1

enum {CLIENT_Button_Calculate = MIN};

#define frytime 10.0

float fryBurgers(float panSize, float numHamburgers)
{
     float totaltime;

    float cooktime;

    cooktime = numHamburgers * frytime; 

    totaltime = cooktime / panSize;

    return totaltime;
}

LRESULT APIENTRY ClientProc(HWND hWnd, UINT Msg, WPARAM wParam, LPARAM lParam);

HINSTANCE g_hInst;

/* form handles */

HWND Button_Calculate , Client_Edit_PanSize , Client_Edit_Burgers;
HWND Client_Edit_Message;

HWND hClient;

int APIENTRY WinMain(HINSTANCE hInst, HINSTANCE hPrev, LPSTR line, int CmdShow)
{

HFONT hDefaultFont = (HFONT)GetStockObject(DEFAULT_GUI_FONT);

	/* Main Form: */
  
	WNDCLASS Window;

	HWND hwnd;
	MSG Msg;

	Window.cbClsExtra = 0;
	Window.cbWndExtra = 0;
	Window.hbrBackground = (HBRUSH)COLOR_BTNSHADOW;
	Window.hInstance = hInst;
	Window.hIcon = NULL;
	Window.hCursor = LoadCursor(NULL, IDC_ARROW);
	Window.lpfnWndProc = (WNDPROC)ClientProc;
	Window.lpszClassName = "Client";
	Window.lpszMenuName = NULL;
	Window.style = CS_HREDRAW | CS_VREDRAW;
	
	RegisterClass(&Window);
	
	/* Create the Forms: */
	hClient = CreateWindow("Client",
						   "VeggieBurgerCook", 
						   WS_OVERLAPPED | WS_SYSMENU,
					   	   150,
						   150,
						   220,
						   240,
						   0,
						   0,
						   hInst,
						   0);
	
	/* show form: */
	ShowWindow(hClient, SW_SHOW);
	UpdateWindow(hClient);


	while(GetMessage(&Msg, NULL, 0, 0) > 0)
	{
		if (!TranslateMDISysAccel(hClient, &Msg))
		{
			TranslateMessage(&Msg);
			DispatchMessage(&Msg);
		}
	}
	return Msg.wParam;
}

LRESULT APIENTRY ClientProc(HWND hWnd, UINT Msg, WPARAM wParam, LPARAM lParam)
{

 

    float panSize;
    float numHamburgers;

    float totaltime;

    char cookresult[200];
    char Buffer[50];

        

HFONT hDefaultFont = (HFONT)GetStockObject(DEFAULT_GUI_FONT);

	switch(Msg)
	{
		case WM_CREATE:
		{

             
                                Button_Calculate = CreateWindowEx(WS_EX_STATICEDGE, "Button", "Calculate", BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE, 5, 5, 100, 25, hWnd, (HMENU)CLIENT_Button_Calculate, g_hInst, 0);
				SendMessage(Button_Calculate, WM_SETFONT, (WPARAM)hDefaultFont, MAKELPARAM(FALSE, 0));



			Client_Edit_PanSize = CreateWindowEx(WS_EX_STATICEDGE, "Edit", "pansize", WS_CHILD | WS_VISIBLE, 115, 160, 85, 15, hWnd, NULL, g_hInst, 0);
				SendMessage(Client_Edit_PanSize, WM_SETFONT, (WPARAM)hDefaultFont, MAKELPARAM(FALSE, 0));

			Client_Edit_Burgers = CreateWindowEx(WS_EX_STATICEDGE, "Edit", "Burgers", WS_CHILD | WS_VISIBLE, 115, 180, 85, 15, hWnd, NULL, g_hInst, 0);
				SendMessage(Client_Edit_Burgers, WM_SETFONT, (WPARAM)hDefaultFont, MAKELPARAM(FALSE, 0));


			Client_Edit_Message = CreateWindowEx(WS_EX_STATICEDGE, "Edit", "", WS_CHILD | WS_VISIBLE | ES_MULTILINE, 5, 35, 205, 100, hWnd, NULL, g_hInst, 0);
				SendMessage(Client_Edit_Message, WM_SETFONT, (WPARAM)hDefaultFont, MAKELPARAM(FALSE, 0));





		break;
		}

		case WM_COMMAND:
		{
			switch(HIWORD(wParam))
			{
				case BN_CLICKED:
				{
					switch(LOWORD(wParam))
					{
						case CLIENT_Button_Calculate:
						{

                                                     EnableWindow(Button_Calculate, 0);
                                                     GetWindowText(Button_Calculate, Buffer, sizeof(Buffer));

							if (strcmp(Buffer, "Calculate") == 0)
							{

								GetWindowText(Client_Edit_PanSize, Buffer, sizeof(Buffer));
                                                                
                                                                                                   panSize = atoi(Buffer);


                                                                 GetWindowText(Client_Edit_Burgers, Buffer, sizeof(Buffer));

                                                                                                    numHamburgers = atoi(Buffer);



                                                                                                     
                                                                                                   totaltime = fryBurgers( panSize, numHamburgers);

                                                                                                   if(panSize >= numHamburgers) totaltime = frytime ;

                                                                                                   sprintf( cookresult , "To cook %f Veggie burgers  on a grill that will let cook only %f at a time  it will take  %f minutes " , numHamburgers, panSize , totaltime );

                                                                                                   SetWindowText(Client_Edit_Message , cookresult );

                                                                                                   SetWindowText(Button_Calculate, "WantFliesWithDat?");
							}
							else
							{

	                                                   SetWindowText(Button_Calculate, "Calculate");
							}

							EnableWindow(Button_Calculate, 1);
						break;
						}




	}
				break;
				}
			}
		break;
		}

		case WM_DESTROY:
		{
			PostQuitMessage(0);
		break;
		}

		default: return DefWindowProc(hWnd, Msg, wParam, lParam);
	}
	return 0;
}

[PJYelton]

Here is Pete’s code. It gets the correct results in almost all cases but unfortunately fails when the number of hamburgers is less than pansize (it returns zero instead of 10) and missed a couple like panSize=4, numHam=54 which should return 135 but instead it returns 140. Otherwise, good job!

 int fryBurgers(int panSize, int numHamburgers)
{
   int total = numHamburgers * 2;
   int loads = total / panSize;

   if((loads % panSize) != 0)
      loads++;

   return loads * 5;
}

Here is SirNot’s short and sweet entry. I’m not sure where the (total % max / 2) part of the equation comes from, since this ended up giving impossible times that weren’t multiples of 5, for example panSize=4, numHam=54 it returns 136 minutes which is impossible. Take that out and place in a rounding function and you have the correct equation.

int burgerfry(int max, int total)
{
	return (total > max ? (int)((double)total / (double)max * 10 + (total % max / 2)) : 10);
}

ElWhapo’s code came oh-so-close to being correct, only on a very few instances does it barely misstep. For example 12 pansize and 320 hamburgers he lists 265 minutes when the answer is 270.

 class ElWhapo
{
	public:
		int fryBurgers(int panSize, int orderSize);
};

..........................................

int ElWhapo::fryBurgers(int panSize, int orderSize)
{
	// If Pan Is Big Enough To Fit Them All....
	if(panSize > orderSize)
	{
		return 10;
	}

	// If Pan Is Divisible By Order, Then Pan Must Always Be Full
	if((orderSize % panSize) == 0)
	{
		return ((orderSize / panSize) * 10);
	}

	// I'd Try And Explain It, But It's Hard
	// I Drew Possiblities Out On Paper And Found This
	// Pattern In Them All.
	return (((orderSize / panSize) * 10) + 5);
}

That leaves us with just one other entry, Lithorien who got every test case correct! Instead of going with a messy equation that is error-prone he decided to simulate the frying process explicity:

 #include <iostream>

class Lithorien
{
	public:
		int fryBurgers(int panSize, int numBurgers)
		{
			int time = 0; // Time counter.
			numBurgers *= 2; // Now it represents sides.
			
			// If we're cooking non-existant burgers, or are cooking on a non-existant burner, we have problems.
			if ((panSize < 1) || (numBurgers < 1))
			{
				return(0);
			}
			
			// We *= 2'd above so that we could do the simple while loop here.
			// The loop just simply cooks as many burgers as possible, subtracts that amount from the total 
			// amount of SIDES to cook, and then keeps track of the 5-minute increments.
			
			while (numBurgers > 0)
			{
				numBurgers -= panSize;
				time += 5;
			}
			
			// Even if our pan's bigger than the # of burgers to cook, we have a minimum of 10 minutes total.
			// Without this check, the while loop wouldn't catch cooking less sides than slots available, and
			// give a wrong time.
			
			if (time < 10)
			{
				time = 10;
			}
			
			return(time);
		}
};

Everyone, congratulate Lithorien as the winner of the May easy problem contest!!

[PJYelton]

Medium Problem

This one wasn’t too bad. All you needed was a function that could reverse a number then your code simply turns into this:

if number==reverse(number)
   print number of iterations and number and exit
if iterations==10
   print no solution and exit
number+=reverse(number)
increment iterations and loop back

How you created the reverse function was up to you. Easiest way is with the modulus operator. Here is how I would do it:

 int reverse(int num)
{	
	int r=0;
	while (num)
	{
		r*=10;
		r+=(num%10);
		num/=10;
	}

	return r;
}

I received nine entries for this one and all nine used a different yet correct method to solve it with the small exception of one which didn’t look for the fact that the starting number might already be a palindrome. Kudos to everyone! If I have to pick a winner I’ll choose Manofsteel972 who’s code was simplest, most efficient in my opinion. SirNot had a very similar entry but unfortunately I was unable to completely follow his logic without any comments. Second place would go to Togra who went out of his way to ensure that his code could handle any possibility including overloaded variables and different bases.

Everyone congratulate Manofsteel972 and Togra!!

I have attached everyones code since it is too much to include in the post itself. Results of the two difficult problems will be posted in the next couple of days.

[PJYelton]

The rest of the medium submissions:

[PJYelton]

Apologies to Togra who also submitted an answer to the easy problem but who's message somehow got deleted from my private message list. Luckily I had a saved copy of his code on my computer, so here it is. His code also produces the correct answers everytime using the formula that I had detailed above making him the joint-winner with Lithorien. Congratulations to both of them!

/* C Board - monthly contest
 * May 2005, easy problem
 * Author: Togra
 * 
 */

#include <cmath>

class Togra
{

 public:
  /* Calculates the time needed to fry some hamburgers in a pan of certain size.
   */
  int fryBurgers(int panSize, int numHamburgers)
  {
    /* Nothing to eat... */
    if (numHamburgers == 0)
      return 0;

    /* Minimal working time is 10 minutes. */
    if (numHamburgers <= panSize)
      return 10;

    /* First fry all front sides consecutively, then all back sides, leaving no 
     * places unoccupied during the process. Only at the end there might be room 
     * left.
     */
    return 5 * (int)ceil(2.0 * numHamburgers / panSize);
  }

};

[kryptkat]

She does work <extra purrrr!> perfectly!

If you “try” to fry zero veggieburger or imaganary or nonexistant veggieburgers you “take an action” which does take time.

However if you try to fry negative 4 veggieburgers on a negative 4 pansize... <iterate magical word ‘mathmaticus’ and swissh and flick magic wand> negative 4 veggieburgers x negative 4 pansize = 16 real veggieburgers <puff>

Getting your 16 real veggieburgers out of extradimentional space is another matter.

edit

wtg all

[PJYelton]

And now for the last two problems!

Hard Problem version 1

I find the easiest way to explain this problem is with a quick example. Lets take a tree of five nodes marked (1,2,3,4,5) and make the root 3. What can you say about whats to the left and whats to the right? Well, obviously 1 and 2 must be to the left and 4 and 5 must be to the right correct? Anything else? By far the biggest thing you can recognize is that the branches in both directions are ALSO BINARY SEARCH TREES. So to the left, theres a BST of size two, to the right theres a BST of two, so how many possible combinations of trees have 3 at the root? Well, its the number of BST's with two nodes times the number of BST's with two nodes. Likewise, with 4 at the root, it would be number of BST's with 3 nodes times number of BST's with 1 node, and etc etc for roots of 1, 2 or 5. So the total number of trees with 5 nodes is just the sum of all these possibilities:

howMany(5)=howMany(0)*howMany(4)+howMany(1)*howMan y(3)+howMany(2)*howMany(2)+howMany(3)*howMany(1)+h owMany(4)*howMany(0)

For an arbitrary number of nodes, the summation is simply:

howMany(x)=howMany(0)*howMany(x-1)+howMany(1)*howMany(x-2)+...+howMany(x-2)*howMany(1)+howMany(x-1)*howMany(0)

Of course this solution just screams recursion:

int howMany(int x)
{
   int sum=0;

   if (x==0 || x==1)
      return 1;

   for (int i=0; i<=x-1; i++)
      sum+=(howMany(i)*howMany(x-i-1));

   return sum;
}

Unfortunately this is extremely inefficient in much the same way that calculating the fibonacci numbers using recursion is bad, since you are constantly recalculating the same numbers over and over again. In fact, on my computer, howMany(19) times out. Much better is to save your values so they would only need to be calculated once. Here is my iterative solution which calculates each value in succession and saves the results:

int howMany(int x)
{
	int answers[20]={0};
	answers[0]=1;
	answers[1]=1;

	for (int i=2; i<=x; i++)
		for (int j=0; j<=i-1; j++)
			answers[i]+=(answers[j]*answers[i-j-1]);

	return answers[x];
}

Now, as many astute programmers either figured out or already knew, it turns out theres a handy dandy set of numbers that perfectly fits the number of BST's called the Catalan numbers. For example, the 9th Catalan number is the same as the number of BST's with 9 nodes. The formula for calculating the nth Catalan number is simply:

(2n Choose n)/(n+1)

where (2n Choose n) is the number of combinations containing n unordered items out of a set of 2n items and is calculated like this.

I'm not going to grade these as everyone got the answer correct who turned in code with the very small exception of SirNot who had a integer overflow error for nodes=19. Since its tough to say whether a program that used the Catalan numbers should be graded higher/lower than one that did not, I'm going to declare everyone winners, so congrats!! Code to follow

[PJYelton]

SirNot's code, his algorithm was the most unique and if it changed ints to doubles it would lose the overload error and produce correct answers up and beyond 18:

int howmany(int nodes)
{
	int i, j;
	unsigned int tri[40] = { 0 };
	
	tri[0] = 1;
	for(i = 1; i <= nodes * 2; i++)
	{
		tri[i] = 1;
		for(j = i - 1; j > 0; j--) tri[j] += tri[j - 1];
	}
	
	return tri[nodes] / (nodes + 1);
}

Sang-drax's code using the Catalan numbers:

namespace SangDrax
{
    double factorial(double n)
    {
        //Simple recursive factorial function
        if (n<=0) return 1;
        return n * factorial(n-1);
    }
    double   nChoosek(int n, int k)
    {   
        return factorial(n) / (factorial(n-k) * factorial(k));
    }
    int howMany(int k)
    {
        //The number of binary trees are equal to the 
        //catalan numbers. This is quite easy to prove
        //by using induction, but I won't type it here.

        //Return the rounded value
        return nChoosek(2*k,k) / (k+1) + 0.5;
    }
};

Togra's code also using the Catalan numbers using a pretty strong algorithm to calculate 2n choose n:

/* C Board - monthly contest
 * May 2005, hard problem (version 1)
 * Author: Togra
 * 
 * Obviously, the sequence to compute will increase fast. From the small 
 * domain [1,19], we can expect int (32-bit) overflow around term 20. 
 * Since PJYelton gave away howMany(15) == 9694845, I went to the OEIS 
 * (http://www.research.att.com/~njas/sequences/) to find more terms and 
 * perhaps a nice formula.
 *
 * It seems we need to compute Catalan numbers. See 
 * http://mathworld.wolfram.com/CatalanNumber.html for a mathematical 
 * treatment. I found two useful formulae: 
 *
 *  * Direct computation, using binomials:
 *    C(n) = binomial(2 * n, n) / (n + 1)
 *
 *  * Recurrence:
 *    C(n) = 2 * (2 * n - 1) * C(n - 1) / (n + 1)
 *
 * I chose to implement the first one, since I already had a very fast 
 * implementation of binomial() ready.  
 *
 * Care has to be taken to prevent overflow. The binomial coefficients 
 * would overflow (32-bit int) for k >= 17. Switching to 64-bit integers is 
 * a sufficient remedy.
 */

class Togra
{
 public:
  /* Returns the k-th Catalan number, 0 <= k <= 19.
   */
  int howMany(int k)
  {
    return binomial(2 * k, k) / (k + 1);
  }

 private:
  /* Computes the binomial coefficient "n choose k" using clever product 
   * cancelling. Overflow might occur when n > 62.
   */
  unsigned long long binomial(int n, int k)
  {
    unsigned long long i, result = 1;
    if (k > n || n < 0 || k < 0)
      return 0;
    2 * k < n ? (k = n - k + 1) : ++k;
    for (i = n; i >= k; --i)
      result = result * i / (n - i + 1);
    return result;
  }
};

Alvaro's code using a combination of recursion and storing values:

int howMany(int n){
  const int MEMORY_SIZE=20;
  static int memory[MEMORY_SIZE]={1,1,2,0};
  
  // See if we already know the answer
  if(n<MEMORY_SIZE&&memory[n])
    return memory[n];
  
  // If not, compute it recursively
  int result=0;
  for(int i=0;i<n;++i)
    result+=howMany(i)*howMany(n-i-1);
  
  // Store the result if it fits in our memory array
  if(n<MEMORY_SIZE)
    memory[n]=result;
  return result;
}

Treenef's code that uses precomputed Catalan numbers:

/*
  Name: Catalan numbers
  Copyright: ©
  Author: Treenef
  Date: 10/05/05 15:50
  Description: Uses precomputed values
  of the formula:
      
      1   (2n)       nCr = 2nCn
    ----  
    (n+1)  (n)
*/



#include <iostream>


int catalan(int);

using namespace std;
int main()
{
    long int n;
    cout<<"Enter n:"<<endl;
    cin>>n;
   
    catalan(n);
  
    int stop;
    cin>>stop;
    return 0;
}

int catalan(int n)
{
    char array[81][81]={"1","2","5","14","42","132","429","1430","4862",
    "16796","58786","208012","742900","2674440","9694845",
    "35357670","129644790","477638700","1767263190"};
    cout<<array[n-1];
}

joshdick's code that also uses precomputed values:

/* Joshua Karstendick
** 5/3/05
** This program returns any of the first 19 Catalan numbers.
** A Catalan number, C[n], is equal to the number of BSTs
** that can be formed from n distinct elements.
*/

#include <iostream>

const unsigned long int A[] ={ 0,1,2,5,14,42,132,429,1430,4862,16796,58786,208012  ,742900,
					2674440,9694845,35357670,129644790,477638700,17672  63190 }; 

int howMany(int k)
{
	return A[k];
}

int main()
{
	for(int i=0; i < 20; ++i)
		std::cout << i << ": " << howMany(i) << std::endl;
	return 0;
}

And last but not least ClownPimp's code that more or less uses exactly the code I wrote above:

//
// Number of permutations is equal to the number of perms of the
// left subtree times the perms of the right subtree, given a 
// particular root. The root can be any number, so we sum over all
// possible choices for the root. Since this is a BST, we note
// the left subtree consists of i-1 elements and the right subtree
// consists of N-i elements, with i as the root.
//
//          N
//  T(n) = Sum T(i-1)*T(N-i)
//         i=1
//
// Solution implemented using dynamic programming
//----------------------------------------------------------------
class ClownPimp
{
public:
  int howMany(int N)
  {
    int *T = new int[N+1];
    int rval;
    T[0] = 1;
    T[1] = 1;

    for (int i = 2; i <= N; i++) {
      T[i] = 0;
      for (int j = 1; j <= i; j++) {
        T[i] += T[j-1]*T[i-j];
      }
    }

    rval = T[N];
    delete[] T;

    return rval;
  }
};

[PJYelton]

Hard Problem version 2

Since I was a little suprised that so many people knew the Catalan trick to the last problem I decided to create this variation. The solution is the same with only a couple of minor tweaks.

So whats the difference? Well, only that you know you never have to calculate what happens if all of the nodes are to one side since this results in an invalid tree. The only exception to this rule is nodes=2. Other than that, its the same. Just like the first version of the problem the branch to the left and the branch to the right are still BST's only this time they're a BST version 2. So to calculate howMany2(5) for example, you do the same summation just minus the multiplacations of howMany2(0):

howMany(5)=howMany2(1)*howMany2(3)+howMany2(2)*how Many2(2)+howMany2(3)*howMany2(1)

My iterative solution simply changes to:

int howMany2(int x)
{
	int answers[26]={0};
	answers[0]=1;
	answers[1]=1;
	answers[2]=2;

	for (int i=3; i<=x; i++)
		for (int j=1; j<=i-2; j++)
			answers[i]+=(answers[j]*answers[i-j-1]);

	return answers[x];
}

This one definately stumped a few more people, although we still got a healthy dose of entries. Again, everyone who entered got the answer correct so congratulations!!

[PJYelton]

Sang-drax's recursive entry:

namespace SangDrax
{
    int howMany2(int n)
    {
        //This solution is essentially the same as for howMany,
        //but we use the recursive formula instead.
        
        //The number of possible trees for n=1 and n=2
        //This will stop the recursion
        if (n <= 1)
            return 1;
        if (n == 2)
            return 2;

        //Each subtree can have between 1 and n-1 elements
        //Add all these combinations
        int combinations=0;
        for (int k=1; k<=n-2; k++)
            combinations += howMany2(k)*howMany2(n-k-1);
        return combinations;
    }   

}

Togra's entry using combination of storing and recursion

/* C Board - monthly contest
 * May 2005, hard problem (version 2)
 * Author: Togra
 */

class Togra
{
 public:
  /* Compute the number of BST's consisting of k nodes, conforming
   * to the following rule: no node can have an empty branch unless
   * the other one contains at most 1 nodes. 1 <= k <= 27.
   */
  int howMany2(int k)
  {
    // Cache the results to avoid recalculation during recursion.
    static int cache[28] = {0, 1, 2}; // , 0, 0, ...
    if (cache[k])
      return cache[k];

    // Distribute k - 1 nodes recursively over the left and right 
    // main subtrees.
    for (int i = 1; i <= k - 2; ++i)
      cache[k] += howMany2(i) * howMany2(k - i - 1);
    return cache[k];
  }
};

Alvaro's entry also using combination of storing and recursion:

int howMany2(int n){
  const int MEMORY_SIZE=26;
  static int memory[MEMORY_SIZE]={1,1,2,0};
  
  // See if we already know the answer
  if(n<MEMORY_SIZE&&memory[n])
    return memory[n];
  
  // If not, compute it recursively
  int result=0;
  for(int i=1;i<(n-1);++i)
    result+=howMany2(i)*howMany2(n-i-1);
  
  // Store the result if it fits in our memory array
  if(n<MEMORY_SIZE)
    memory[n]=result;
  return result;
}

And last, ClownPimp's using the same code he had above just slightly modified:

//
// Same solution as before, noting that an invalid BST
// consists of trees with one subtree with 0 nodes and 
// the other subtree with more than 1 node
//----------------------------------------------------------
class ClownPimp
{
public:
  int howMany2(int N)
  {
    int *T = new int[N+1];
    int rval;
    T[0] = 1;
    T[1] = 1;

    for (int i = 2; i <= N; i++) {
      T[i] = 0;
      for (int j = 1; j <= i; j++) {
        // skip invalid BSTs
        if (j-1 == 0 && i-j > 1)
          continue;
        if (i-j == 0 && j-1 > 1)
          continue;

         T[i] += T[j-1]*T[i-j];
      }
    }

    rval = T[N];
    delete[] T;

    return rval;
  }
};

Again, congrats to all and expect a new contest probably the second week in June. Again, any feedback good or bad is more than welcome.

[Togra]

The hard problems weren't so hard imho - harder to understand than to write down in code. I had most fun with the medium problem since it required solving some subproblems along the way.

I hope you don't declare everyone winner again so easily... Not that I don't want to share credit , it just makes the contest a lesser contest.

Thanks PJYelton for hosting the contest! I look forward to the next one.

[Sang-drax]

Treenef, your code for the Hard Problem is invalid.

Not only is it invalid, but also very unsafe. What happens when I call howMany(100) or howMany(-1)?

[treenef]

Treenef, your code for the Hard Problem is invalid

Wrong, look again. If that's the case then so is Joshdicks.

What happens when I call howMany(100) or howMany(-1)?

Wasn't part of Pjyelton's criteria if you care to read the original post.
Although, having said that, I understand why my pre-computed values my seem like cheating, but then so long as the output is 'ok' it shouldn't really matter???

Overall great contest PJ. (Although I wish I had the time to do the others - damn my 9-5 job -grrr)

[Sang-drax]

Originally Posted by treenef

Wrong, look again. If that's the case then so is Joshdicks.

It has nothing to do with the use of precomputed values.

1. You have no howMany() function
2. Your function doesn't return anything, even though you declared it as returning int.