CareerCup

Assuming a general graph with edge weights and you are allowed to repeat intermediate nodes, then the following recursion seems to give a dynamic programming algorithm:

Let the source and destination vertices be s and t.

We need to compute Best[s,t,10]. Best[x,y,t] is best path between x to y of t hops.

The recurrence is

Best[u,v,m] =  min_{over all u'} [ max {Distance(u,u'), Best[u',v, m-1]} ]

Best[u,v,1] is easy to calculate.

Assuming the number of hops is constant, a naive implementation of this will give an O(n^2) time and O(n^2) space algorithm.

I have updated my solution as
Consider this question for 10 stations and 4 flags Let the distance between them be as 1-----2--3---4----5-----6------7-------8-9---10

Where – represents the distance in units It means distance between 1st and 2nd station is 5, And hence the distance between the first and tenth station will be (5+2+3+4+5+6+7+1+3) = 36

We apply binary search between 1st and 10th station hence we get 36/2 = 18

Hence we will choose the pivot as 18 unit of distance and apply binary search from

(i) 1st and 18th unit of distance for 1st flag

(ii) 19th and 36th unit of distance for 2nd flag

Average of distance is 9 for 1st flag which is more closer to 4th station we place flag on station 4.

Average of distance is 9 and hence distance from starting is 27 which is more closer to 7th station Hence we place 2nd flag on station 7.

Hence answer will 1,4,7,10.Hence maximum distance is optimized as b/w any two stations is 15 in this case Similarly we can solve for 100 stations

Please check whether this approach is correct or there can be any more efficient. Correct me if i am wrong Thanks in advance

if you select 1 and 100...that itself will make the max distance b/w two hops as 99...
am i missing something here.

looks like a shortest path problem --> see Dijkstra's algorithm (you were on the right track with a dynamic programming approach)

The question is not very clear to me.

Are we given the list of possible adjacent stations? OR any two stations are adjacent and we are given the distance?

Can we repeat stations in the hops? (assuming we can repeat makes the problem easier, I think).

Can you please clarify?

Hey guys, it we have 100 nodes and I want to reach from node 1 to node 100 in exactly 10 hops (with min expense), how do we do that? Dijkstra's algo might give me a path in < 10 hops. Any ideas?

How about finding hop near the 1/8th distance, 2/8 th distance and so on ? So we can find the cumulative distance O(n) and search for the 8 hops O(1).

How about all pairs shortest path execution on a general graph?
Post the execution short them and return minimum k (10) results

floyld warshall with a modification for number of steps will work. Correct me if i am wrong

My approach is this:

Consider this question for 10 stations and 4 flags Let the distance between them be as
1-----2--3---4----5-----6------7-------8-9---10

Where – represents the distance in units It means distance between 1st and 2nd station is 5, And hence the distance between the first and tenth station will be (5+2+3+4+5+6+7+1+3) = 36

We apply binary search between 1st and 10th station hence we get 36/2 = 18

Hence this distance is 1 unit far from 6 and 3 units from 5, hence we will select the 6th station as the pivot and apply binary search between (i) 1st station and 6th station (ii) 6th station and 10th station

Average of distance between 1st station and 6th station is 19/2 = 9.5units from 1st station Hence 9.5 is more closer to station 4 and we place flag on station 4.

Average of distance between 6th station and 10th station is 17/2 = 8.5units from 6th station Hence it is more closer to station number 7 and we place flag on station 7.

Hence answer will be 1,4,7,10.Hence maximum distance is optimized as b/w any two stations is 15 in this case Similarly we can solve for 100 stations.

Correct me if i am wrong

Please check whether this approach is correct or there can be any more efficient. Correct me if i am wrong Thanks in advance

This problem is very simple .... Greedy approach will work. step 1: Find the minimum distance, step 2: Add this minimum distance with the minimum adjacent distance (Either left one or
right one). step 3: Join this two to one single distance. step 4: Repeat step 1-3 until total number of distinct distance become equal to the number of flags+1

My approach. I 'll start doing depth first search from the root and will maintain a level variable which will be counting the number of levels.
{{

int graph[100][100];
bool flag[100];
int n;
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
void dfs(int node,int level)
{
if(level==10&& node==dest)
print(stack);
else
{
flag[node]=false;
qsort(graph[node],n,sizeof(int),compare);
for(int i=0;i<n;i++)
{
if(!flag[i])
{
dfs(i,level+1);
stack.push(i);
}
}
stack.pop(node);
flag[node]=false;
}
}
}}

{My approach. I 'll start doing depth first search from the root and will maintain a level variable which will be counting the number of levels.
{{

int graph[100][100];
bool flag[100];
int n;
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
void dfs(int node,int level)
{
if(level==10&& node==dest)
print(stack);
else
{
flag[node]=false;
qsort(graph[node],n,sizeof(int),compare);
for(int i=0;i<n;i++)
{
if(!flag[i])
{
dfs(i,level+1);
stack.push(i);
}
}
stack.pop(node);
flag[node]=false;
}
}
}}}