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 [email protected].
