For chaining two points A and B

A(x1,y1) at index i in array
B(x2,y2) at index j in array

if ( i<j and x1<=x2 and y1<=y2 and !(x1==x2 and y1==y2))
    then A and B are in a increasing sequence (chain)

For example: A = { (0,0), (1,0), (1,1), (2,1), (2,0)}

longest sequence (cahin) is = {(0,0), (1,0), (1,1), (2,1)} i.e 4 elements

we have to find the longest sequence (chain) of points.

How to approach for this?

solution required is less than O(N^2)

Possible solutions:- 1) LIS (NlogN) link 2) Posets (I don't understand if you can explain)

  • $\begingroup$ We can't explain a solution you haven't told us! $\endgroup$ – Yuval Filmus Jan 12 '17 at 9:42
  • $\begingroup$ I means how to implement this for my conditions or any new way to solve this problem $\endgroup$ – user64506 Jan 12 '17 at 10:14
  • $\begingroup$ Have you tried reading about standard algorithms for longest increasing subsequence? Can they be applied here? Please spend some time studying those standard materials, then edit your question to summarize why they don't apply (or, if they do apply, then you know how to answer your question and can write an answer below). $\endgroup$ – D.W. Jan 12 '17 at 18:04
  • $\begingroup$ I applied working in O(Nlog^2N) but all test cases are not passed :( $\endgroup$ – user64506 Jan 12 '17 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy