MONOPOLY AGAIN

CONCEPTS USED:

Dynamic programming

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT$($SIMPLIFIED$)$:

After having lost to you the last time, your friend challenges you to another round of Monopoly. This time, he changes the rules of the game slightly, hoping that this would throw you off your game and he would finally have his sweet revenge. Your task is to play optimally and win this, again!
The updated rules are as follows:As before, there are N notes, having values V1,V2,…,Vn.
But this time, each player can choose as many of the first X notes as he wants, where 1<=X<=2∗M, then M is updated according to the following rule M=max(X,M). M=1 initially.
This continues until all the notes have been claimed. Assuming both you and your friend play optimally and that you take the first turn, calculate the maximum amount you can accumulate.

For Example :

5
2 7 9 4 4

In first step you take 2. M=1
then he takes 7 and 9. 
Then you take 4 and 4.so total is 10
If you take two elements in the first step
Then M becomes 2 and he selects the rest of the 4 elements because 
X can go till 2∗M=4. 
So the maximum is 10.

You are encouraged to implement the above brute force and think of memoization on your own first ,before looking at the solution.

See original problem statement here

SOLVING APPROACH:

Let’s define function f(turn ,ind,m) where turn denotes the player ,ind denotes the starting index and 2*m denotes the maximum index one can choose numbers from.

The trick here is to maximise the sum for player1 and minimise the sum for player2 because we can only control the moves of player1.

if(turn%2==0) ,that means it’s the turn of first player:
val1=max(val1,tempsum+solve(turn+1,i+ind,max(x,i)));

if(turn%2),that means it’s the turn of second player:
val2=min(val2,solve(turn+1,i+ind,max(x,i)));

But using this recursive approach will take exponential time.

DYNAMIC PROGRAMMING:

Learn programming online and to overcome repetitive computation of several sub-problems,we keep memoizing the results obtained. This drops the complexity to polynomial form.

SOLUTIONS:

 #include <stdio.h>

    #define ll long long
    ll dp[101][101][201];
    int n;

    ll arr[101];
     ll int max(ll x,ll y)
    {
    if(x>y)return x;
    return y;
    }
    ll int min(ll x,ll y)
    {
    if(x<y)return x;
    return y;
    }

    ll solve(int turn,int ind,int x){
    if(ind==n){
        return 0;
    }

    ll tempsum=0;

    ll val1=-1;
    ll val2=1000000000000000000;

    if(dp[turn][ind][x]!=-1)
        return dp[turn][ind][x];

    for(int i=1;i<=2*x && (ind+i-1)<n;i++){
        tempsum=(tempsum+arr[ind+i-1]);
        if(turn%2==0){
            val1=max(val1,tempsum+solve(turn+1,i+ind,max(x,i)));
        }
        else{
            val2=min(val2,solve(turn+1,i+ind,max(x,i)));
        }
    }

    if(turn%2==0){
        return dp[turn][ind][x]=val1;
    }
    else
        return dp[turn][ind][x]=val2;
    }

    int main(){

    scanf("%lld",&n);

    memset(dp,-1,sizeof(dp));

    for(int i=0;i<n;i++){
        scanf("%lld",&arr[i]);
    }

    printf("%lld",solve(0,0,1));


    return 0;
    }
import java.util.Scanner;
    import java.util.*;

    class HelloWorld{

    long [][][] dp = new long[101][101][201];
    long [] arr = new long[101];

    long solve(int turn, int ind, int x, int n){
        if(ind==n){
            return 0;
        }
        long tempsum=0, val1=Integer.MIN_VALUE, val2= Integer.MAX_VALUE;

        if(dp[turn][ind][x]!=-1)
            return dp[turn][ind][x];

        for(int i=1;i<=2*x && (ind+i-1)<n;i++){
            tempsum=(tempsum+arr[ind+i-1]);
            if(turn%2==0){
                val1=Math.max(val1,tempsum+solve(turn+1,i+ind,Math.max(x,i),n));
            }
            else{
                val2=Math.min(val2,solve(turn+1,i+ind,Math.max(x,i),n));
            }
        }

        if(turn%2==0){
            return dp[turn][ind][x]=val1;
        }
        else{
            return dp[turn][ind][x]=val2;
        }
    }

    public static void main(String []args){
        Scanner myObj = new Scanner(System.in);
        int n=myObj.nextInt();
        HelloWorld  h = new HelloWorld();
        for(int i=0;i<101;i++)
            for(int j=0;j<101;j++)
                for(int k=0;k<201;k++)
                    h.dp[i][j][k]=-1;
        // Arrays.fill(h.dp, -1);

        for(int i=0;i<n;i++){
            h.arr[i]=myObj.nextLong();
        }
        long res = h.solve(0,0,1,n);
        System.out.print(res);

        // System.out.println("Hello World");
    }
    }
#include<bits/stdc++.h>
    using namespace std;

    #define ll long long

    ll dp[101][101][201];
    int n;

    ll arr[101];

    ll solve(int turn,int ind,int x){
    if(ind==n){
        return 0;
    }

    ll tempsum=0;

    ll val1=INT_MIN;
    ll val2=INT_MAX;

    if(dp[turn][ind][x]!=-1)
        return dp[turn][ind][x];

    for(int i=1;i<=2*x && (ind+i-1)<n;i++){
        tempsum=(tempsum+arr[ind+i-1]);
        if(turn%2==0){
            val1=max(val1,tempsum+solve(turn+1,i+ind,max(x,i)));
        }
        else{
            val2=min(val2,solve(turn+1,i+ind,max(x,i)));
        }
    }

    if(turn%2==0){
        return dp[turn][ind][x]=val1;
    }
    else
        return dp[turn][ind][x]=val2;
    }

    int main(){

    cin>>n;

    memset(dp,-1,sizeof(dp));

    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    cout<<solve(0,0,1);


    return 0;
    }


Space complexity: O(NNN)

Previous post MONOPOLY ONCE AGAIN
Next post MONOPOLY

Leave a Reply

Your email address will not be published. Required fields are marked *