Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Wednesday, November 3, 2010
Alice and Bob play with an array
Alice and Bob play with an array of integers. In turn, each one can pop a number from one of the two ends of the array. What strategy can be used to maximize the sum of popped integers for Alice?
It's certainly not the obvious greedy strategy of take the biggest of the two ends... counterexample is 1 1 99 2
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.)
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.
Just pop randomly each turn ? I don't get the question, please explain!
ReplyDeleteIt's certainly not the obvious greedy strategy of take the biggest of the two ends... counterexample is 1 1 99 2
ReplyDeleteIt 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.)
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.
Oh, I got it, bad me.
ReplyDelete