Min-Max Search

Let's talk about algorithms!

Moderator: Board moderators

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

Min-Max Search

Post by Dimitar »

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

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by Zyaad Jaunnoo »

DP problem...

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

Post by Dimitar »

OK, thanks

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris »

It's actually way way simpler than DP

think about parity.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

Quantris wrote:It's actually way way simpler than DP

think about parity.
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
Location: Edmonton AB Canada

Post by Quantris »

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

Post by misof »

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

Post by Fixxxer »

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)))

Post Reply

Return to “Algorithms”