tag:blogger.com,1999:blog-6314876008291942531.post6928643844260510631..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Alice and Bob play with an arrayUnknownnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6314876008291942531.post-69517322271230507222010-11-25T08:51:50.895-08:002010-11-25T08:51:50.895-08:00Oh, I got it, bad me.Oh, I got it, bad me.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-50130457522840404182010-11-21T21:49:31.819-08:002010-11-21T21:49:31.819-08:00It's certainly not the obvious greedy strategy...It's certainly not the obvious greedy strategy of take the biggest of the two ends... counterexample is 1 1 99 2<br /><br />It can definitely be solved by a 2D dynamic program which computes the score of an array [i..j]. S[i, j] is equal to max(a[i]-S[i+1, j], a[j]-S[j-1]), and S[i,i]=a[i]. (hmm, that doesn't tell you Alices actual score, just which decision will lead you to it.)<br /><br />I wonder if there's some fun goofy rule like adding all odd numbers and comparing to all even numbers and not immediately jumping into dynamic programming.Unknownhttps://www.blogger.com/profile/07382128872503140808noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-47525771269621323232010-11-18T07:08:48.303-08:002010-11-18T07:08:48.303-08:00Just pop randomly each turn ? I don't get the ...Just pop randomly each turn ? I don't get the question, please explain!Anonymousnoreply@blogger.com