first player can check if sum of notes placed in the odd position are greater than the sum of notes placed in the even position and can pick accordingly and will always win.
On Sat, Oct 9, 2010 at 10:52 AM, Anand <[email protected]> wrote: > Yes. > http://codepad.org/2KFrv8cs > > > On Fri, Oct 8, 2010 at 9:56 PM, Lego Haryanto <[email protected]>wrote: > >> I think this pasted code is incorrect ... answer for { 2, 5, 7, 1, 8, 9 } >> should be 18, right? >> >> On Thu, Oct 7, 2010 at 10:53 PM, Anand <[email protected]> wrote: >> >>> Using standard Dynamic Programing logic: >>> http://codepad.org/IwBTor4F >>> >>> >>> >>> On Thu, Oct 7, 2010 at 8:43 PM, Gene <[email protected]> wrote: >>> >>>> Nice problem. Let N_1, N_2, ... N_n be the values of the N notes. >>>> Let F(i,j) be the maximum possible score the current player can get >>>> using only notes i through j. Then >>>> >>>> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) ) >>>> >>>> This is saying that the current player always makes the choice that >>>> minimizes B the best score that the other player can achieve. When we >>>> know that choice, the best _we_ can do is the sum of all the available >>>> notes minus B. >>>> >>>> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j) >>>> where i > j. >>>> >>>> For example, suppose we have notes 3 7 2 1 . The answer we want is >>>> F(1,4). >>>> >>>> Initially we have >>>> F(1,1) = 3 >>>> F(2,2) = 7 >>>> F(3,3) = 2 >>>> F(4,4) = 1 >>>> >>>> Now we can compute >>>> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7). >>>> F(2,3) = 9 - min(F(3,3), F(2,2)) = 9 - min(2,7) = 7 (pick N_2=7). >>>> F(3,4) = 3 - min(F(4,4), F(3,3)) = 3 - min(1,2) = 2 (pick N_3=2). >>>> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care). >>>> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7). >>>> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1). >>>> >>>> >>>> On Oct 7, 8:14 pm, Anand <[email protected]> wrote: >>>> > Given a row of notes (with specified values), two players play a game. >>>> At >>>> > each turn, any player can pick a note from any of the two ends. How >>>> will the >>>> > first player maximize his score? Both players will play optimally. >>>> >>>> -- >>>> 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]<algogeeks%[email protected]> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>> -- >>> 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]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Fear of the LORD is the beginning of knowledge (Proverbs 1:7) >> >> -- >> 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]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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?hl=en.
