# UVA Problem: Longest Run on a Snowboard (10285)

In this problem we need to find the longest path in a directed acyclic graph (dag).

The algorithm and explanation is given bellow-

# Consider each grid point/height as a node of a directed graph.

# Initially length of each node is lengthOf (r,c)= 1. 0<=r<R , 0<=c<C.

# Consider a directed edge from node X to four neighboring node (top, down, bottom, left) if there value is less than X value.

Example-

10 2 4

3 14 22

8 13 20

Here directed edge from node 10 is 10->2 and 10->3. Directed edge from node 2 is none, since neighbor node 10,4,14 all of are greater than 2 and so on.

Now loop –

For(i=0; i<row; i++)

{

For(j=0; j<column; j++)

{

longestRun(node at i’th row & j’th column);

}

}

longestRun function return the longest run from node position at (r,c).

int longestRun(int r,int c)

{if any neighbor (i,j) of (r,c) has value less than (r,c) value then && lengthOf(r,c) not previously calculated then

{

x= longestRun(i,j);

if(lengthOf(r,c)<x)

{

lengthOf(r,c)=x;

}

}

return lengthOf(r,c) + 1;

}

Here is the explanation;

# Start from node 10. 2 directed edge from node 10.

a. 10->2, 2->empty . No edge from node 2. Highest length of 2 is 1.

b. 10->3, 3->empty. No edge from node 3. Highest length of 3 is 1.

So we get highest length of 10 is 2.

# Start from node 2.

We calculate highest length of node 2 previously, so no need to calculate again.

# Start from node 4.

1 directed edge 4->2

- highest length of 2 is 1, so highest length of 4 is 2.
Continue this for each node and take the maximum.

In this example we get the longest run for node 22.

3 Directed edge for node 22.

- 22->4 , we have calculated longest run for 4 before which is 2, so here longest run for 22 is 3.
- 22->14, we have calculated longest run for 14 before which is 4, so here longest run for 22 is 5.
- 22->20, which is not calculated before , so calculate longest run for 20. We find longest run for 20 is 4, 20->13->8->3. So longest run for 22 is 5.