CareerCup

I am thinking of this way:

1. we need to go from "start" to "end", then we have to cover a base distance = sum(x_i), which is go directly from start -> d_1 to d_n -> end.

2. the different patterns can be split into pieces like d_i to d_j, which means you can go back and forth between d_i and d_j as many times as you want, as long as the total distance does not exceed Z.

3. So the value P = Z - sum(x_i) can be regarded as the total distance used to go back-and-forth in any pair (d_i, d_j). Each time you made a back-and-forth between (d_i, d_j), it cost 2*x_i.

4. Then you can use DP to calculate the combinations of using x_i to make up the sum equals to P. Each x_i can be used for multiple time. Then final combinations is the total number of patterns.

5. If you need to print all the patterns, you need to search, but in a memoization way. The worst case time complexity could be O(n*P).

Does it make sense??

Example 1: Start--(1)--D1--(2)--D2--(3)--D3--(2)—end and z=18 then possible output are
a) start— (1) —D1— (2) —D2— (3)—D3— (3)—D2—(2)—D1—(2)—D2—(3)—D3—(2) —end
b) start— (1) —D1— (2) —D2—(2)—D1—(2)—D2—(3)— D3— (3)—D2—(3)—D3(2)— end etc…
Example 2: Start—(1)—D1—(1)—D2—(1)—D3—(1)—D4—(1)—D5—(1)—end and z=12 then possible output are
a) start—D1—start—D1—D2—D3—D2—D3—D4—D3—D4—D5—end
b) start—D1—D2—D1—D2—D3—D2—D3—D4—D5—D4—D5—end

x2 is the distance b/w D1 , D2 or start, D2 ?

Its a graph problem ,when you have to reach from {Start} to {End}. There are various paths available(via 2 stones), but we need to traverse the path in such a manner, so that total distance covered to reach the end = Z

its a dynamic algorithmic problem , on every stone there,s several ways to travel a considerable distance that can fulfill criteria of travelling z distance exactly problem come becoz of no optimization criteria on every step so using only 2-d arrays is not gona work

what data strucure should be used for storing intermediate result and how??

This sounds like a Permuation problem where repetitions are allowed: nPr= n^r
Here, total number of stones to choose from is Dn and we must ASSUME that we are going to choose only 2 stones at a time because we have two legs. then we are talking Dn^2 number of patterns. Since we are allowing repetitions, the sum total will always be greater than Z.

How about this for the DP recursion:

DP[i,z]=DP[i-1,z-dist(Di,Di-1)]+DP[i+1,z-dist(Di,Di+1)]

i = 0 for start,1 for D1, n for Dn,n+1 for end

Basically when you are at ith stone and you have to walk z distance more, you can either goto i-1th or i+1th having walked dist(i to i-1) or dist(i to i+1)

Use memoization to store arr[i][z] = DP[i,z] etc.

Breaking conditions:
DP[n+1(end),0] = 1
DP[i,z] = 1 if( dist(i,end_or_n+1) == z) meaning from i you go to end via i+1,i+2 ...
DP[i,z] = 0 if( dist(i,end_or_n+1) > z)
DP[i,z] = 0 if i <0 or i> n+1


MAIN call : DP[0,Z]