Skip to content

UVA Problem: Game of Sum(10891)

October 9, 2011

Problem Statement:

Problem Explanation:

This Problem is classic example of dynamic programing.

Lets , Sum{i,j}= sum of element from i to j;
Best{i,j}= max point can be achieved from i to j element.

suppose n=4, A can take following 7 way-

1. Sum{1} – Best{2-4}
2. Sum{1-2} – Best {3-4}
3. Sum{1-3} – Best {4}
4. Sum{1-4} – Best {}
5. Sum{4-4} – Best {1-3}
6. Sum{3,4} – Best {1-2}
7. Sum{2-4} – Best{1-1}

A will choose from above 7 option in which he can get maximum score that
is Best[1-4].if A take {1} then B will get element{2-4}. Then B will play perfectly
to achieve more point from elemenmt {2-4}, which is Best{2-4}. B can achieve
Best{2,4} by maximum of following way-

1. Sum{2} – Best{3-4}
2. Sum{2-3} – best{4}
3. Sum{2-4} – Best{}
4. Sum{4-4} – Best{2-3}

B will take the option where he can get maximum score. If B take {2} , then
A will get element{3-4}, So A will try to get maximum score from element {3,4},
which is Best{3,4} and can be achieved either following way-

1. Sum{3-3} – Best{4-4}
2. Sum{3-4} – Best{}
3. Sum{4-4} – Best{3-3}.

Above we solved all the subproblems to calcualte option 1 of Problem Best[1-4],
Sum{1} – Best{2-4}. Similary we have to calculate other 6 option. And the option
with higest value is the our answer.

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: