CCC 07 S4 waterslide

[chopperdudes]

okay in preparation for CCC junior this year, i've done most of the junior's hard questions (except for nukit, which i looked at long ago, can't figure out, and gave up and will do it later for preparation), so now i'm doing some of the S3 and S4's. one thing i've noticed is that questions are getting harder actually? (those J5/S3 were kinda jokes)... but 2007's junior was wayy too easy. anyways....

i was doing S4 of 07, at first i tried the recursive approach, start from node 1, find its connecting nodes, and recurse it until it has reached the final node, which will add one to the counter. however this got quickly (or rather sooo slowly) pwn'ed by the huge test cases. next i had the idea similar to calculating the fib number, start from final node, the ways to the final nodes is equal to the sum of the ways to all of its preceeding nodes, recursively do this until you reach one, which will return one. i also memorized the calculated value in an array so they can be looked up instead of recalculated. this works for all the test data very quickly, but still takes 2 to 3 minutes for test case 4, which surprisingly, the direct recursion method was actually more efficient.

how else could this problem be done? here's my code in turing:
(the first output will be calculated with the fib approach, followed by the time, and the 2nd (which will take forever in test cases other than 1 and 4) is calculated with direct recursion, followed by the time)

[CodeMonkey2000]

here is my c++ solution. I think it's right, but I haven't checked it yet. Basically if slide x leads to y, then the number of ways to y is incremented by the number of ways to x. Initially everything is set to 0, except for slide 1, since there is only 1 way to slide 1. THis is a good DP.

c++:

#include <fstream> #include <vector> #include<iostream> #include<algorithm> using namespace std; struct node {     int x,y; }; bool func (node i,node j) { return (i.x<j.x); } int main() {     ifstream fin("s4.in");     ofstream fout("s4.out");     int n,i,j;     fin>>n;     vector<node>slide;     vector<int>ways(n+1,0);     ways[1]=1;     fin>>i>>j;     while(i!=0 && j!=0)     {         node tmp;         tmp.x=i;tmp.y=j;         slide.push_back(tmp);         fin>>i>>j;     }     sort(slide.begin(),slide.end(),func);     //for(int x=0;x<slide.size();x++)       //  cout<<slide[x].x<<" "<<slide[x].y<<endl;     for(int x=0;x<slide.size();x++)         ways[slide[x].y]+=ways[slide[x].x];     fout<<ways[n];     cout<<ways[n]; }