## Min-Max Search

Moderator: Board moderators

Dimitar
New poster
Posts: 8
Joined: Tue Sep 20, 2005 11:42 am

### Min-Max Search

Can you help me with this task. I think that it can be
solved with min-max search, but i can't find an example on
how to implement this algorithm.

Game

Two players are playing this game: There are n numbers (n<=128), ordered in a row.
The first player takes one number from the left or the right side.
Then the second player takes one number from the left or the right
side of the rest of the numbers.
In this way they take the numbers, until there are no numbers left. What is
the maximum sum of the numbers that the first player has taken, if the both
players are playing optimal.

input:
first line: n - the number of numbers
second lind: n numbers, of which a <= 100

output:
the maximum sum of numbers that the first player can take

Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am
DP problem...

Dimitar
New poster
Posts: 8
Joined: Tue Sep 20, 2005 11:42 am
OK, thanks

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
It's actually way way simpler than DP

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Quantris wrote:It's actually way way simpler than DP

Nope. To win or draw this game, "thinking about parity" is enough. But the greedy algorithm doesn't guarantee that you get the maximal sum.

Consider the following input:

Code: Select all

``````8
3 0 3 0 3 0 3 10
``````
The greedy algorithm will win 12:10, but the first player can force a 19:3 win.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
just do the "parity" technique at each step.

Maybe that is DP after all.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Quantris wrote:just do the "parity" technique at each step.

Maybe that is DP after all.
Would you care to explain your algorithm in more detail, preferably on my input?

Fixxxer
New poster
Posts: 5
Joined: Tue Aug 30, 2005 6:20 pm
Isnt it a usaco problem?
i solved it using memoization

max_profit(i,j)=MAX((a[i]+sum[i+1][j]-max_profit(i+1,j)),(a[j]+sum[i][j-1]-max_profit(i,j-1)))