ya the idea is in topcoder tutorials first learn how to solve it for single basket alone then it can be extended to multiple baskets
read wiki article about grundy numbers xor will do the rest there are 1000ptr div 1 problems based on this concept for nim the grundy numbers are just the basket size there are other problems for which u have to find the grundy numbers and xor them I dont know about those things but there are such problems at topcoder. Arun, On Sat, Aug 15, 2009 at 9:00 PM, santhosh venkat < santhoshvenkat1...@gmail.com> wrote: > > The reply posted above suggesting Grundy numbers is most efficient than the > game tree given there in wikipedia.I think game tree has exponential run > time for this egg problem. It can be applied to tic-tac toe game > successfully as there are 9 places to be used . but here each basket may > have any number of eggs > On Sat, Aug 15, 2009 at 8:51 PM, sharad kumar <aryansmit3...@gmail.com>wrote: > >> >> can u use a game tree >> http://en.wikipedia.org/wiki/Game_tree >> >> On Sat, Aug 15, 2009 at 8:49 PM, santhosh venkat < >> santhoshvenkat1...@gmail.com> wrote: >> >>> @ Sharad >>> I think the replier's logic and explanation for the same can be found >>> here . >>> http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames >>> Besides i think dp can also be applied here .but it needs lot of memory >>> Santhosh . >>> >>> >>> On Sat, Aug 15, 2009 at 8:42 PM, sharad kumar >>> <aryansmit3...@gmail.com>wrote: >>> >>>> pls explain a bit.suppose there aaaaaare 2 baskets and lets assume 12 >>>> eggs in basket 1 and 15 in b2.wat will u do.... >>>> >>>> >>>> On Sat, Aug 15, 2009 at 8:33 PM, Arun N <arunn3...@gmail.com> wrote: >>>> >>>>> this is same as NIM >>>>> the concept is Grundy Numbers >>>>> just xor all the numbers >>>>> if it is zero 1st player will lose >>>>> else 1st player will win >>>>> assuming both play optimally >>>>> >>>>> Arun, >>>>> >>>>> On Fri, Aug 14, 2009 at 7:50 PM, sharad kumar <aryansmit3...@gmail.com >>>>> > wrote: >>>>> >>>>>> both >>>>>> >>>>>> On Fri, Aug 14, 2009 at 7:35 PM, ganesa thandavam < >>>>>> gthanda...@gmail.com> wrote: >>>>>> >>>>>>> >>>>>>> is the number of eggs same in all baskets ??? >>>>>>> >>>>>>> On Aug 14, 7:00 pm, sharad kumar <aryansmit3...@gmail.com> wrote: >>>>>>> > There are N egg baskets and the number of eggs in each basket is a >>>>>>> known >>>>>>> > quantity. Two players take turns to remove these eggs from the >>>>>>> baskets. On >>>>>>> > each turn, a player must remove at least one egg, and may remove >>>>>>> any number >>>>>>> > of eggs provided they all belong to the same basket. The player >>>>>>> picking the >>>>>>> > last egg(s) wins the game. If you are allowed to decide who is >>>>>>> going to >>>>>>> > start first, what mathematical function would you use to decide so >>>>>>> that you >>>>>>> > end up on the winning side? >>>>>>> >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>>> -- >>>>> Potential is not what U have, its what U think U have!!! >>>>> It is better to worn out than rust. >>>>> >>>>> >>>>> >>>>> >>>>> >>>> >>>> >>>> >>> >>> >>> >> >> >> > > > > -- Potential is not what U have, its what U think U have!!! It is better to worn out than rust. --~--~---------~--~----~------------~-------~--~----~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
