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

\"\"<\/p>\n

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

Recursion and memorization.<\/p>\n<\/blockquote>\n

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

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

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

There are notes having values V1,V2,V3…Vn arranged in a row. You and your friend take turns alternatively. In each turn you can select either the first or the last note in the row and remove it. The note’s value gets added to your balance. Now you need to determine how you should select the notes such that in the end you have more cash than your friend.
\nYou always go first.<\/p>\n<\/blockquote>\n

For Example :<\/h4>\n
2\n4\n5 3 7 15\n4\n8 15 1 6\n\nFor first testcase\nYou - 15\nFriend - 7\nYou - 5\nFriend - 3\nSo total 15 + 5 =20\n<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
You have to think about your opponent’s move means options available for the your opponent once you are done with the move, What your opponent will pick (he is equally clever and tries to leave you with minimum values to be chosen from) and  then what you will chose.<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
\n
WRONG APPROACH:<\/strong>
\nGREEDY<\/em> .You may think that selecting the maximum value from the two ends will get you the maximum sum of notes.But that’s wrong!!<\/p>\n<\/blockquote>\n
Look at this example:<\/p>\n
14 20 6 8\nIf you use greedy technique , you would end up with 14+8= 22 notes and your opponent would win with 20+6=26 notes. \nWhereas the correct answer to this test case will be:\nyou :20+8=28 notes,\nyour opponent: 6+14=20 notes.<\/code><\/pre>\n
You are encouraged to try this problem ,before looking at the solution.<\/p>\n
<\/strong><\/u><\/a><\/p>\n
Have you noticed that your opponent is equally clever??
\nWe can clearly see that each player is making the move by keeping in mind the two moves which can be made in future and pick the best of them.
\nLet\u2019s make it more clear- Suppose we have coins lined up from Ci to Cj with the values from Vi to Vj respectively.<\/p>\n
In every move you have 2 options \u2013<\/strong><\/p>\n
Either pick the ith coin (from starting)
\nOR pick the jth coin ( from the end).<\/p>\n
Let\u2019s discuss both the options<\/p>\n
You the ith coin (from starting)<\/p>\n
\"\"<\/p>\n
    \n
  1. You choose the ith coin with value Ci: The opponent either chooses (i+1)th<\/sup> coin or jth coin. The opponent intends to choose the coin which leaves you with minimum value.
    \ni.e. The user can collect the value Ci + min(F(i+2, j), F(i+1, j-1) ).<\/li>\n<\/ol>\n
    \"\"<\/p>\n
      \n
    1. You choose the jth coin with value Cj: The opponent either chooses ith coin or (j-1)th<\/sup> coin. The opponent intends to choose the coin which leaves you with minimum value.
      \ni.e. The user can collect the value Cj + min(F(i+1, j-1), F(i, j-2) ).
      \nFollowing is recursive solution that is based on above two choices. We take the maximum of two choices.<\/p>\n
      F(i, j) = Max { Ci + Min{F(i+2,j), F(i+1, j-1)} ,\n      Cj + Min{F(i+1,j-1), F(i, j-2)}}<\/code><\/pre>\n<\/li>\n<\/ol>\n
      SOLUTIONS:<\/h3>\n
      \t\t\t\t\t\t