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

stde

Sat Feb 16, 2008 7:14 am


CCC S4 2007 help

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

im trying to do this problem
i think my algorithm is almost correct 
so i am still not sure whats wrong with it
all i got for output was  -1
can someone help me with it?

here is my code

// S4_2007_2.cpp -- dynamic approach

#include
#include

int sumPath(int);
int **cMat; // connectivity matrix
int *path; // sum of the path for each vertex
int pathN; // total number of path form i to point
int vertN; // total number of vertices 
int i, j;
int sP, eP; // start and end point
using namespace std;

int main()
{
	ifstream inf;
	inf.open("s4.1.in");

	// initializing stuff
	inf >> vertN;
	vertN ++;
	path = new int[/quote]

by the way, i checked the solutions on the CCC site and i compared them to my own 
and i still dont see the problem   :cry:


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

pistolpete

Sun Feb 17, 2008 11:14 pm


RE:CCC S4 2007 help

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

i'm sort of new to programming (well not that new, just new to contests and such) and I've got a questions so sorry for derailing your thread but... are STL containers allowed in the CCC? And if so, how much does it affect the performance of the program?


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

[Gandalf]

Sun Feb 17, 2008 11:27 pm


RE:CCC S4 2007 help

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

Standard libraries such as the STL are allowed in the CCC, as you can see on the second page of [url=http://access.mmhs.ca/ccc/2007/2007seniorproblems.pdf]the question booklet.  I'm not sure what you mean by the performance of the program...  In terms of execution speed I think what counts far more than the language / libraries used is the algorithm you develop.

*edit*  Oh, and welcome to CompSci.ca!  Hope you enjoy your stay.


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

zylum

Tue Feb 19, 2008 12:58 am


RE:CCC S4 2007 help

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

Data structures also affect the performance not to mention time to code the solution.


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

stde

Tue Feb 19, 2008 1:01 am


RE:CCC S4 2007 help

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

uh..thank you guys


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

zylum

Tue Feb 19, 2008 1:58 am


RE:CCC S4 2007 help

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

int sumPath(int pt)
{
        if (path[pt] != -1)
                return path[pt];
        pathN = 0;
        for (i = 0; i < vertN; i++)
        {
                if (cMat[i][pt] == 1)
                {
                        pathN += sumPath(i);
                        path[pt] = pathN;
                }
        } // end for
        return path[pt];
} // return  

This function doesn't seem right.. First, your terminating condition (ie. if(path[pt] != -1) return path[pt]; ) will never execute because the path array is initialize to -1 and none of the elements ever change.. So even though i haven't run your code I am betting there is some infinite recursion / stack overflow... Further, you should somehow identify leaf nodes so that the path length from a node to a leaf node is 1 (or the some of the leaf nodes it contains). If you dont want to ID the leaf nodes then you could just check if the node has no outgoing paths. Lastly, you initialize your connectivity matrix in the form cMat[StartPoint][EndPoint], but in this function you loop through and sum all the inbound paths rather than outgoing paths (cMat[i][pt] rather than cMat[pt][i])

That should get you started..