{"id":2242,"date":"2020-07-29T07:34:55","date_gmt":"2020-07-29T07:34:55","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2242"},"modified":"2022-03-30T13:29:02","modified_gmt":"2022-03-30T13:29:02","slug":"monopoly-again","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/monopoly-again\/","title":{"rendered":"MONOPOLY AGAIN"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Dynamic programming<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium.<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(SIMPLIFIED):<\/h3>\n
\n

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!
\nThe updated rules are as follows:As before, there are N notes, having values V1,V2,…,Vn.
\nBut this time, each player can choose as many of the first X notes as he wants, where 1<=X<=2\u2217M, then M is updated according to the following rule M=max(X,M). M=1 initially.
\nThis 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.<\/p>\n<\/blockquote>\n

For Example :<\/h4>\n
5\n2 7 9 4 4\n\nIn first step you take 2. M=1\nthen he takes 7 and 9. \nThen you take 4 and 4.so total is 10\nIf you take two elements in the first step\nThen M becomes 2 and he selects the rest of the 4 elements because \nX can go till 2\u2217M=4. \nSo the maximum is 10.<\/code><\/pre>\n
You are encouraged to implement the above brute force and think of memoization on your own first ,before looking at the solution.<\/h4>\n
<\/strong><\/u><\/a><\/p>\n
SOLVING APPROACH:<\/h3>\n
\n
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.<\/p>\n
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.<\/p>\n
if(turn%2==0) ,that means it’s the turn of first player:
\nval1=max(val1,tempsum+solve(turn+1,i+ind,max(x,i)))<\/code>;<\/p>\n
if(turn%2),that means it’s the turn of second player:
\nval2<\/code>=min(val2,solve(turn+1,i+ind,max(x,i))<\/code>);<\/p>\n
But using this recursive approach will take exponential time.<\/p>\n<\/blockquote>\n
DYNAMIC PROGRAMMING:<\/h3>\n
\n
To overcome repetitive computation of several sub-problems,we keep memoizing the results obtained.This drops the complexity to polynomial form.<\/p>\n<\/blockquote>\n
SOLUTIONS:<\/h3>\n
\t\t\t\t\t\t