piyushnigam.iiit
BAN USERWe have to give the number of paths and not all paths. This can be achieved by a O(MN) algorithm using DP.
the recurrence will be
NumPath(i,j) = NumPath(i-1,j) + NumPath(i,j-1)
Calculate this matrix and the value of NumPath(m,n) will be the answer.
Isn't this problem pretty simple. Following is the algo:
1. the first elements of the arrays will always make the first pair.
2. Say we're at position i(in A) and j(in B)
The next candidates would be (a[i+1],b[j]) or (a[i],b[j+1]), chose the bigger one and increment the counter accordingly.
Please correct me if I m wrong
Follow these steps:
Let the arrays be A1 and A2 with start and end as s1,e1 and s2,e2 resp.
1. find the median m1 of A1 and m2 of A2
2. Compare m1 and m2, say m1 < m2 then the median of the two arrays combined should lie in the second half of A1 or the first half of A2.
3. Update s1=m1 and e2=m2. repeat from 1 till you arrive at s1=e1 or s2=e2.
If a vertical line of symmetry exist .. it should be x = Avg(i): i belongs to set of x co-ordinate of all the points.
- piyushnigam.iiit July 04, 2010first find the line by the above formula ( O(n) ), Also while doing this insert each point in a hash table with x co-ordinate as the key
Then for each x < Avg(i) there should exist a point equidistance from the line on the other side, with the same y co-ordinate, if so .. delete the point from hash table and continue further until all the points less than Avg(i) are covered.
This algo will run in O(n).