CCC '07 S4 - Waterpark

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2007 Stage 1, Senior #4

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 marked points (including the start at and the end at ) 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 to points and ; from to and ; and from to . There are 3 ways down the hill. You can check this by seeing that we can go , or .

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

Input Specification

Input begins with a single integer (), on a line by itself, indicating the number of marked points. The next lines contain point pairs of the form x y, where . 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 Specification

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

Sample Input

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

Output for Sample Input

3

• commented on Aug. 14, 2019, 11:25 a.m.

Can someone look at my code I keep on getting MLE for test cases 2 and 5

• commented on Nov. 11, 2017, 8:58 a.m.

how can there be 2^30 edges if the max vertices is 9999

• commented on Nov. 11, 2017, 10:50 a.m.

That refers to the number of unique paths from node 1 to node n, not the amount of edges between nodes.

• commented on Nov. 10, 2017, 10:14 p.m.

My DFS implementation TLEs. Any suggestions?

• commented on Nov. 19, 2019, 8:04 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Nov. 11, 2017, 8:49 a.m.

Brute force dfs TLEs, try using a different approach. DP is one of the problem types here.

• commented on Dec. 10, 2016, 5:26 p.m.

Is there a way I can further optimize my code to not get TLE?

• commented on Dec. 1, 2016, 9:50 p.m.

I keep on getting a value error for python 2.

• commented on Dec. 2, 2016, 11:15 a.m. edited

y.split() returns strings, you should to map(int, y.split()) to convert them into integers.

• commented on Aug. 30, 2016, 10:29 a.m.

My code wont run on Dmoj. Works on some compilers only.

• commented on Aug. 30, 2016, 10:46 a.m.

Check the status code help page for some details about the failed initializing error you're getting. Put simply, you're declaring a integer array which would occupy around 381mb of memory.

The memory limit for this problem is 64mb.

• commented on Aug. 30, 2016, 12:50 p.m. edit 2

Is it a coincidence that the example does the exact same thing as his submission?

• commented on Sept. 22, 2015, 7:14 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Sept. 22, 2015, 8:26 p.m.

dfs doesn't TLE, I used dfs and I have the fastest solution.