As soon as you get one hint, the number of orders drops greatly. Your first question should be to ask about the color or value which occurs closest to n/2 times. When you ask about that, the number of possible orders will be much smaller, and you can continue with just that list. The problem was to find the minimum number of hints required, not to minimize the computation time to find those hints. A faster algorithm is to ask for hints randomly, but that will require more hints.
Don On Wednesday, July 2, 2014 11:20:32 AM UTC-4, vikas wrote: > > Don, if you are talking about cards ordering then it will be n! which > looks pretty high to compute ( consider even for n=10). and then for every > count , you will need to compute every single color and values , i.e. worst > case will be 25 n! ~ O(n!) . Can we do better ? > > On Wednesday, 2 July 2014 01:20:07 UTC+5:30, Don wrote: >> >> Initially there are 5! = 120 possible orders for the cards. You should >> ask for the hint which will reduce that number by the largest amount. So in >> your example above, asking which cards have value 1 would not reduce the >> number at all. Asking which card is Green would reduce the possible orders >> to 24. The algorithm is to make a list of the possible orders. Then for >> each question, count the number of orders in the list would give each >> possible answer. The largest count is the score for that question. Ask the >> question with the smallest score. Then based on the answer, remove any >> orders from the list which are not consistent with that answer. Repeat the >> process until you have only one order remaining. >> Don >> >> On Tuesday, July 1, 2014 12:15:14 PM UTC-4, vikas wrote: >>> >>> One of my friend posted this question to me and I am unable to get >>> anywhere. Could you guys please help >>> >>> A game of cards has 5 colors and 5 values. Thus a total of 25 cards are >>> possible. Player 1 will choose n cards and tell you exactly , what all >>> cards he has. Then he will spread cards in front of you with face downwards >>> in random fashion. >>> So you know the card values but not the ordering. Player 1 will provide >>> you 2 types of hints , he can tell you what all cards have some color or he >>> can tell you what all cards have some value. you need to tell the ordering >>> of cards with the help of these hints. >>> challenge is to find out minimum number of hints to be provided by >>> player 1 so that you are able to make it for all cards. >>> >>> e.g. say player chosen n=5 cards >>> and tells you the values >>> >>> B1 Y1 W1 G1 R1 >>> >>> he can either tell you that what all cards are 1 (in this case all cards) >>> or can tell you different color like leftmost is color 'B" and next >>> after 'Y' and so on. So minimun hints in this case is 4 >>> >>> >>> another example >>> if n=4 >>> G4 R3 R4 B3 >>> >>> Here he can tell you the card 1st and 3rd are of values 4 and cards 2 >>> and 3 are of color 'R'. This will be sufficient to infer the card values. >>> so answer is 2 >>> >>> >>> I am not interested in code , please suggest plain simple algorithms, if >>> possible with arguments that why it is correct ? >>> >>> -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
