On May 28, 10:16 pm, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote:
> On Wed, May 28, 2008 at 1:53 PM, Zeratul <[EMAIL PROTECTED]> wrote:
> > We can pair a white pin located at <x1, y1> with a black pin located
> > at <x2, y2> if x1 > x2 and y2 > y2.
>
> you mean y1 > y2 right ?
>
Yes
>
>
> > My idea is to first find all the pins that can make a pair, and do a
> > maximum bipartie matching. But it will cost O(N ^ 3) time.
>
> can you please explain how this will work ?
>
Divide pins into two sets B, W according to their colors
A node in W with location <x1, y1> is connected to a node in B with
location <x2, y2> if and only if x1 > x2 and y1 > y2.
Then find a maximum bipartie matching between the two sets
>
>
> > Is there any better solution for this problem? The hint says that a
> > greedy algorithm will be efficient.
>
> > Sorry for my poor English. many thanks
>
> --
> Ciao,
> Ajinkya
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
