Skip to content

UVA Problem: Longest Run on a Snowboard (10285)

October 8, 2011

 

Problem Statement

 
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

  1. 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.

  1. 22->4 , we have calculated longest run for 4 before which is 2, so here longest run for 22 is  3.
  2. 22->14, we have calculated longest run for 14 before which is 4, so here longest run for 22 is 5.
  3. 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.
Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: