2007 Canadian Computing Competition, Stage 1

Problem S4: Waterpark

The local waterpark has a great slide complex, with many paths crisscrossing down the hill. There is one start point and one end point, but at various points one can turn and take different paths. Walter and Wanda are wondering exactly how many different ways there are to go down the slide. Can you solve their problem?

More precisely, there are n marked points (including the start at 1 and the end at n) where the paths down the hill may split or merge. All paths move down the hill to higher numbered positions; some paths will actually cross over others without meeting but we don’t have to worry about that. We won’t worry about the collisions between sliders that can happen either. Our problem is simply to determine the number of different sequences of marked points we can follow down the hill.

For example, at one small waterpark, there are 4 points with direct slides from 1 to points 2 and 4; from 2 to 3 and 4; and from 3 to 4. There are 3 ways down the hill. You can check this by seeing that we can go (1,2,3,4), (1,2,4) or (1,4).

(Here is a hint: think about starting at the bottom of the slide.)

Input

Input begins with a single integer n (1 ≤ n ≤ 9999), on a line by itself, indicating the number of marked points. The next lines contain point pairs of the of the form x y, where 1 ≤ x < y ≤ n. For example, 1234 8765 indicates a direct slide from point 1234 to point 8765. The last line of input will be indicated by point pair 0 0.

Output

The output is an integer, which is the number of different paths from point 1 to point n. You can assume that the number of paths will be less than 2³⁰. It is possible that there is no path from point 1 to point n, in which case the number of paths is 0.

Sample Input

4
1 2
1 4
2 3
2 4
3 4
0 0

Sample Output

3

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Re at the 4th test case. I saved sides in this way,

tot++;
edge[tot].from = x, edge[tot].to = y;
 
I don't know what's wrong. Anyone can help me?

Thanks!

Is the hint provided in the official problem statement? Or is it simply added by the admins?

It was in the original problem statement.

I changed to a DP approach (as opposed to BFS) and succeeded in getting 4/5.  4th is still TLE...any suggestions of what I could improve?

Try using lists instead of sets

Thanks for your input.  I appreciate it.  I tried that too.  Still TLE on #4.  Any other suggestions?

Your solution takes an extra O(n) to check (if g in G[i]). Instead of looping through all vertices and checking if it's in G[i], just loop through all vertices in G[i].

Thank you very much friend!  I got it!

I am using a BFS search for this problem.  It works 3/5 cases with TLE for the other 2.  Any suggestions how I could improve my algorithm?

The code works perfectly on my system but when I submit to the judge it gives me a return error with a segmentation fault.

You are allocating the array of 10000*10000 = 100000000 bytes = 100 MB (bool is one byte). You're using too much memory

any hints? o.o

Do not use input() on this judge, always raw_input() . 

Please ignore the "hint" in the problem about starting at the bottom of the slide, it's useless.

Assume that there are no more than 20000 slides.

I improved my algorithm

Make it purely dynamic and you can have 30 points :)

made it dynamic!
now can i get 30 pts?

Note: I tried to indent some of it!!!!
(I don't really understand how to indent a program!!!)

I'm pretty sure for everyone that if you do not indent problems in a nice readable format, no one will help you indent it. If you do not know the proper method to indent your programs, then maybe you should ask in PEG and we could teach it sometime.

Asking makes you a fool for a minute, not asking makes you a fool for a lifetime.