World's most popular travel blog for travel bloggers.

[Answers] Conditional LCS problem

, , No Comments
Problem Detail: 

A producer wants to arrange couples of boys and girls for a dance.
There are n boys arranged in a row [A1...An] in some certain order and n girls arranged in a different row [B1...Bn], also in some certain order. Only a couple in which there is a boy and a girl with exactly the same height can dance.
The height of every boy and girl is known. The producer needs to find the maximum number of couples that can dance (There might be people who can't dance).

  1. Show an algorithm for the general case.
  2. Show an algorithm, in which you can't change the order of the boys and the girls. In other words: If there is a couple (Ai,Bj) then there can't be (Ak,Bp) (so that k > i, p < j or k < i, p > j)

Analyze the complexity in every case.

What I know is that the solution to 1 is sorting the array in $O(nlogn)$.
My idea in approaching 2 is that it's like LCS in a static table, only with numbers and not chars, which takes $O(n^2)$.

Can 2 be done in better complexity that $O(n^2)$?

Asked By : Trinarics

Answered By : FrankW

Longest common subsequence (not necessarily continuous) is the solution for the second problem, not for the first. (For the first problem it is not only slower than necessary, but also gives the wrong result. Consider e.g. $A=[1,2]$, $B=[2,1]$: LCS would give only 1 couple, while actually 2 can be formed.)

For the first problem, as @sai_preet pointed out in a comment, you can sort both arrays and then find the couples with a procedure analoguous to merge. This will take $\Theta(n\log n)$ time.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback