A Game - Usaco Sec 3 problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

A Game - Usaco Sec 3 problem

Post by b3yours3lf »

hi,

i'm trying to solve this problem, but i don't understand what is mean by optimal strategy. is this mean player 2 always choose largest number that can be pick?

thanks for ur kind response.

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Re: A Game - Usaco Sec 3 problem

Post by angga888 »

b3yours3lf wrote:i'm trying to solve this problem, but i don't understand what is mean by optimal strategy. is this mean player 2 always choose largest number that can be pick?
If I remembered correctly the answer for your question is NO. Player can also choose the smaller number if it will give him/her better result at the end of the game.

Hope it helps :wink:

kirya
New poster
Posts: 2
Joined: Thu Apr 01, 2004 12:01 pm
Contact:

Post by kirya »

This problem can be solved using DP. Let
sum[j] - sum of elements from i-th position till j-th position
f1[j] - first player score on this table
f2[j] - second player score on this table
f2[j]=sum[j]-f1[j].

answer is f1[1][n] and f2[1][n]

Post Reply

Return to “Algorithms”