ok, and when n is not even, you need to test explicitly the last element with the whole cards.
2008/12/10 Miroslav Balaz <[EMAIL PROTECTED]> > I thik it is wll known classical problem,or there is some similar well > known problem, you need O(n) comparisons. > Randomized > pick eight random cards and compare then to each other. > and you have very low probabilty that you always choose bad card. > Deterministic. > just compare 1 and second, third and fourth... 2k-1 and 2k. > And pick the smaller elemen from ecah pair that the result is true. > now how many representants will have the good set? > let m be the number of good pairs you compared, the result for them ist > true, aleso 1<=m<=n/2; > within the representatns we must have m good, and at most > n/2-m-(n/2+x-m*2) bad, because each good card when compares with bad card > results in false; > so we dont pic any of them in representants. > So we are to solve the same problem with n/2 cards, of course the x means > how much more than n/2 cards it is. > > > I am not sure about boundary cases > > > > 2008/12/9 Tower <[EMAIL PROTECTED]> > > >> A bank has a collection of n bank cards that they've confiscated, >> suspecting them of being used in a fraud. Each bank card corresponds >> to a unique account in the bank. Each account can have many cards >> corresponding to it, and we'll say that two bank cards are equivalent >> if they correspond to the same account. The only way to say 2 cards >> are equivalent is by using a high-tech "equivalence-tester" that takes >> in 2 cards, and after performing some computations, determines whether >> they are equivalent. >> Their question is the following: among the collection of n cards, is >> there a set of more than n/2 of them that are all equivalent to one >> another? Assume that the only feasible operations you can do with the >> cards are to pick two of them and plug them in to the equivalence >> tester. >> >> >> >> > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
