-----------------------------------

Cinjection

Sat Feb 23, 2008 4:29 pm


Critique my solution please.

-----------------------------------

Hey guys. In my quest to learn dynamic programming techniques, I've solved the S4 problem from the 2007 CCC. To my great pleasure, my solution seems to work and is fast. I'm happy with it, but I'm wondering if I'm doing something wrong. I'd appreciate if someone could look over my C++ solution and tell me if I'm doing something wrong or not doing something right.

Here's a link to the question: 

#include 
#include 

using namespace std;

vector *nodes;

vector nWays(1);

int calculateNWays(int nodeNum)
{
	if (nodeNum == 1){
		return nWays[1]; //One way to get to the first node.
	}
	else if (nWays[nodeNum] != 0)
	{
		return nWays[nodeNum];
	}
	else
	{
		int ways(0);

		for(int i=0; i < nodes[nodeNum].size(); i++)
		{
			ways += calculateNWays( nodes[nodeNum][i] );
		}
		
		return ways;
	}
}

int main()
{
	ifstream in("S4.in");
	ofstream out("S4.out");

	int nNodes(0);
	in>>nNodes;

	nodes = new vector[nNodes+1];
	nWays.resize(nNodes+1);

	

	//Init to zero
	for (int i=0; i >nodeFrom;
	in>>nodeTo;

	do
	{
		nodes[nodeTo].push_back(nodeFrom);
		
		in>>nodeFrom;
		in>>nodeTo;

		
	} while (nodeFrom != 0 && nodeTo != 0);

	nWays[1] = 1;

	//Let's go do some dynamic programming!
	for (int k=2; k >nodeFrom;
      in>>nodeTo; 

in >> nodeFrom >> nodeTo;


-----------------------------------

Cinjection

Sun Feb 24, 2008 12:49 pm


Re: RE:Critique my solution please.

-----------------------------------

Your solution is short and ugly! It also dresses poorly! ;-)

Actually I'm insanely far behind on some work; but a cursory glance seems to show it's good.

Got some problem files we can  it with too?

Thanks. I tested it with the test cases that CCC used, and it worked with all five.


-----------------------------------

cyberfish

Wed Mar 19, 2008 5:32 pm


RE:Critique my solution please.

-----------------------------------

Don't know about the coding, but the algorithm is exactly the same as the one I submitted.

http://access.mmhs.ca/ccc/2007/CCC2007S4WaterparkRecursion.txt


-----------------------------------

A.J

Wed Mar 19, 2008 5:56 pm


Re: Critique my solution please.

-----------------------------------

I had a MUCH faster method by recording the values (memoization) + DP