Clever Geek Handbook

Maximum profit-memory, DP, optimality

I was tinkering with the problem in algorithm games, I tried the following problem but couldn't find an efficient way to do it ::

So please help me. This is problem.

This is the exact link :: http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm228

+3


source to share


4 answers


I assume you would like to solve this problem yourself, so I will give you a hint: this problem has an optimal substructure .

Imagine you have both coin solutions N-1

(no leftmost and no rightmost). It would be easy to compute the solution for the moments N

, then?

You can use two related methods to use this property - dynamic programming and its subtype called memoization . The idea is to keep the solution to each subproblem with L

coins missing on the left and R

coins missing on the right (use an array for that NxN

). Before solving the problem, check the array to make sure you've already solved it. You will need to solve no more than N^2/2

subproblems to find a solution.



Here's the pseudocode for a memoized solution:

// solved[L][R] array contains the highest value a player could get
// on a subproblem where L coins are missing from the left
// and R are missing from the right of the original sequence on his move
int solved[N][N] // initialize each element to -1.
int coins[N]     // initialize with coin values 

int solve(int L, int R) {
    if (L+R == N) return 0; // No coins remain
    if (solved[L][R] >= 0) return solved[L][R];
    int remaining = sum(coins from L to R)
    int takeLeft = remaining - solve(L+1, R);
    int takeRight = remaining - solve(L, R+1);
    int result = max(takeLeft, takeRight);
    solved[L][R] = result;
    return result;
}

main() {
    int alice = solve(0, 0);
    int bob = sum(coins) - alice;
}

I remember TopCoder running this issue for a while in early 2005 or 2006, but I don't remember enough details to find their problem archive.

+1


source


You can solve it with dynamic programming . The state can be represented:

set of available coins,
whos turn it is

For each state, you must calculate the maximum amount of money that the person in turn can win.



Council. The rules of this game can be described set of available coins

as an interval.

@edit

for(int interval_size = 1; interval_size <= n; interval_size++) {
    for(int interval_start = 0; interval_start + interval_size <= n; interval_start++) {
         // result[interval_start][interval_start + interval_size] depends only on
         // -> result[interval_start][interval_start + interval_size - 1]
         // -> result[interval_start + 1][interval_start + interval_size]
    }
}
+2


source


Let dp[i, j] = maximum profit alice can make for the coints i, ... j

.

We have:

dp[i, i] = input[i] for all 1 <= i <= N
dp[i, i + 1] = max(input[i], input[i + 1])
dp[i, j] = max(// take first coin, opponent will minimize your next move
               input[i] + min(dp[i + 2, j], dp[i + 1, j - 1]),
               // take last coin, opponent will still minimize your next move
               input[j] + min(dp[i, j - 2], dp[i - 1, j - 1]))
+2


source 


//@ IVlad ::Implement your code ,its giving incorrect answer.Had I implemented it properly??
int coins[1000];
int dp[1000][1000];
int main()
 {
int T,N;//N=How many coins are there
cin>>T; //No of Test Cases.
while(T--)
{
    cin>>N;
    for(int i=1;i<=N;++i)
    {
        cin>>coins[i];
    }
    for(int i=1;i<=N;++i)
    {
        dp[i][i]=coins[i];
    }
    for(int i=1;i<=N;++i)
    {
        if(i+1<=N)
        dp[i][i + 1] = max(coins[i], coins[i + 1]);
    }
    for(int i=1;i<=N;++i)
    {
        for(int j=1;j<=N;++j)
        {
            if((i+2)<=N && (i+1)<=N && (j-2)>=1 && (i-1)>=1 && (j-1)>=1)
            dp[i][j]=max( (coins[i] + min(dp[i + 2] [j], dp[i + 1][ j - 1])),coins[j] + min(dp[i] [j - 2], dp[i - 1] [j - 1]));
        }
    }
    cout<<dp[1][N]<<endl;//Answer
}

return 0;

}

+1


source






More articles:


All Articles