Two players Player-A and Player-B are playing a Number game.
Given 2n Number in random, but linear order. All the numbers are visible and not hidden. Each player picks a number alternatively. A player can only pick it from either end of the list (cannot pick a number from middle of the list).
Player-A gets to pick first, Always. The player who has the maximum total at the end wins the game. How will you make sure that Player-A always wins?
1 comment:
Lets Given Number are
42 40 30 31 55 50
Using Naive Approach Player A will Loose The Game As Shown Below
Since Player-A gets to pick first, he may pick 42 or 51. If Player-A goes by his gut and picks 51,
Then Player-B will get to pick between 42 & 55. Say, he picks 55.
Player-A will get to pick between 42 & 31. Say, he picks 42
Player-B will get to pick between 40 & 31. Say, he picks 40.
Player-A will get to pick between 30 & 31. Say, he picks 31
Player-B will pick 30. So the final Picture is as Given Below
Final Scores are:
* Player-A: 51+42+31 = 124
* Player-B: 55+40+30 = 125
So, even when Player-A has a policy of picking the maximum, he lost the Game. Clearly, the brute-force method of always picking maximum does not work.
Solution
The reason why Player-A lost was because he was only focusing on what he picks. He was not forcing Player-B to pick numbers in a particular fashion.
Suppose if Player-A can force Player-B to pick only the numbers at Even places or only the numbers at odd places in the list, then he can certain his win by pre-calculating the sum of numbers at odd and even places.
In the above example, if I write the Numbers at even places in Green and Numbers at odd places in red
then calculate the Sums
Odd Sum: 42 + 30 + 55 = 127
Even Sum: 40 + 31 + 51 = 122
Odd Sum > Even Sum.
So if Player-A sticks to the Rule:
Always Pic the Numbers which are at odd places in the main List.
Then he can enforce Player-B to choose from two numbers both of which are in the Even positions int he main list. Lets see how:
1. Player-A has the first chance, say he pics 42.
2. Player-B will have to pick from 40 and 51 both of which are at even places in the main list. Say, he picks 51.
3. Now Player-A have 40 & 55 as choices, Since 55 is at odd place, he picks 55.
4. Player-B have to pick from 40 & 31, again both the numbers at even places in the main list.
5. Now player-A picks 30. and Player-B ends up with the last number.
Result:
Player-A: 42, 30, 55 = 127
Player-B: 40, 31, 51 = 122
Player-A wins.
Algorithm:
Step-1: Calculate the sum of all the numbers at even positions. call it E_SUM
Step-2: Calculate the sum of all the numbers at even positions. call it O_SUM
Step-3:
IF E_SUM > O_SUM
From the given two choices at each step, pick the number which is at the even place in the main list.
ELSE
From the given two choices at each step, pick the number which is at the odd place in the main list.
Please let me know your feedbacks
Post a Comment