Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 CCC S4 2007 help
Index -> Contests
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
stde




PostPosted: Sat Feb 16, 2008 7:14 am   Post subject: 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
c++:

// S4_2007_2.cpp -- dynamic approach

#include<iostream>
#include<fstream>

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[vertN];
        cMat = new int *[vertN];

        for (i = 0; i < vertN; i++)
        {
                cMat[i] = new int[vertN];
                path[i] = -1;
        }

        for (i = 0; i < vertN; i++)
                for (j = 0; j < vertN; j++)
                        cMat[i][j] = 0;

        // read from file
        inf >> sP;
        inf >> eP;
        while( sP != 0 && eP != 0)
        {
                cMat[sP][eP] = 1;
                inf >> sP;
                inf >> eP;
        } // end while

        inf.close();
        for (i = 0; i < vertN; i++)
        {
                for (j = 0; j < vertN; j++)
                        cout << cMat[i][j] << " ";
                cout << endl;
        }
        sumPath(vertN - 1);

        // i want to see what values are stored in this array
        for (i = 0; i < vertN; i++)
                cout << path[i] << " ";
        return 0;
} // end main

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 
[/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 Crying or Very sad
Sponsor
Sponsor
Sponsor
sponsor
pistolpete




PostPosted: Sun Feb 17, 2008 11:14 pm   Post subject: 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]




PostPosted: Sun Feb 17, 2008 11:27 pm   Post subject: 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 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




PostPosted: Tue Feb 19, 2008 12:58 am   Post subject: RE:CCC S4 2007 help

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




PostPosted: Tue Feb 19, 2008 1:01 am   Post subject: RE:CCC S4 2007 help

uh..thank you guys
zylum




PostPosted: Tue Feb 19, 2008 1:58 am   Post subject: RE:CCC S4 2007 help

code:
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..
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 6 Posts ]
Jump to:   


Style:  
Search: