Last Updated on March 30, 2022 by Ria Pathak
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:
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;
}
#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;
}
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");
}
}
[forminator_quiz id="2244"]
Space complexity: O(
NNN)
This article tried to discuss the concept of Dynamic programming. Hope this blog helps you understand and solve the problem. To practice more problems on Dynamic programming you can check out MYCODE | Competitive Programming.
Can you please provide the solution in code? I’ve trying to solve it but i am getting wrong answer but the test case ran fine.