Author |
Topic: hard coin problem (Read 3671 times) |
|
RajivG
Junior Member
Gender: 
Posts: 72
|
 |
hard coin problem
« on: Aug 4th, 2011, 4:12am » |
 Quote  Modify
|
we have n coins in a row with different denomination on it and placed randomly
game rule says that either left most or right most coin can be picked and only two players can play this game (one will pick one coin at a time)
now we have to come up with a sequence which make me winner (my sum of denomination of n/2 coins should greater than sum of denomination of remaining n/2 coins)
I tried to solve this but every time I ended up reducing this problem to NP
greedy approach will not work i deduced that but i am not able to find DP solution as well
but interviewer said there is a solution for it because we restrict on possible sequences
any help
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: hard coin problem
« Reply #1 on: Aug 4th, 2011, 6:17am » |
Quote Modify
|
The way I understand the problem, you just need to evaluate the best sum for each contiguous sequence of coins. And there are O(n^2) of them.
If faced with an even number of coins you can guarantee to get half the available value. Compute the sum of the coins at even and the sum of the coins at odd positions. If for instance the set of evens are worth more, always take the coin from the even set, leaving the other player with two coins from the odd set to choose from.
I don't know if it is an optimal strategy, though.
|
|
IP Logged |
|
|
|
paras
Newbie
Posts: 1
|
|
Re: hard coin problem
« Reply #2 on: Aug 4th, 2011, 12:06pm » |
Quote Modify
|
it is given that number of coins is even.
Calculate sum of coins placed at even position and sum of coins placed at odd position.
make the other person pick only smaller sum position coins by picking the bigger sum position coins 
|
|
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: hard coin problem
« Reply #3 on: Aug 4th, 2011, 12:06pm » |
Quote Modify
|
You could do by dynamic programming by using the gain/loss of player1 over player 2 for a sequence of n-1 coins to find the gain/loss for sequence of n coins.
here instead of using actual sums player1 or player2 get, using the gain/loss the first player gets for a given sequence of length n would make DP easy.
|
|
IP Logged |
|
|
|
agent_purge
Newbie
Posts: 4
|
|
Re: hard coin problem
« Reply #4 on: Aug 6th, 2011, 10:04am » |
Quote Modify
|
Solved using DP in O(n2)
| hidden: |
Let coins be 1..N.
d[i,j] = gain (could be negative too) of player with current move when coins from i to j are remaining
d[i,j] = min{ c[i] - d[i-1,j],
c[j] - d[i,j-1] }
d[0,0] = 0
d[i,i] = c[i]
|
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: hard coin problem
« Reply #5 on: Aug 6th, 2011, 1:47pm » |
Quote Modify
|
on Aug 4th, 2011, 6:17am, Grimbal wrote:| I don't know if it is an optimal strategy, though. |
|
It doesn't lead you to win in every game where you could win, for instance 3,2,1,2. Sticking with just the odd or even set means you draw, but if you switch after each of you had a turn, you can win.
So for drawn odds/evens, you can modify the strategy to switch once you're ahead. Though I don't know if that's optimal.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sat90
Newbie
Posts: 7
|
|
Re: hard coin problem
« Reply #6 on: Aug 7th, 2011, 1:19am » |
Quote Modify
|
compare the two coins at end and take decision
my code:
i=0;
j=n;
while(i<=j)
{
if(a[i]<=a[j]) //compare
{
me[k++]=j; //player1 move
j--;
if(a[i]<=a[j]) //player2 move
i++;
else
j--;
}
else
{
me[k++]=i;
i++;
if(a[i]<=a[j])
i++;
else
j--;
}
}
|
|
IP Logged |
|
|
|
sat90
Newbie
Posts: 7
|
|
Re: hard coin problem
« Reply #7 on: Aug 7th, 2011, 1:20am » |
Quote Modify
|
time taken will be O(n).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: hard coin problem
« Reply #8 on: Aug 7th, 2011, 9:47pm » |
Quote Modify
|
A greedy algorithm is not optimal for this problem. Just take 3,10,2,1 as example, you'd get 5 as first player and the second player would get 11.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wiley
Newbie
Posts: 12
|
|
Re: hard coin problem
« Reply #9 on: Aug 13th, 2011, 2:28am » |
Quote Modify
|
Winning player must have choice to be player1(1st turn) or player2(2nd turn) in game.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: hard coin problem
« Reply #10 on: Aug 13th, 2011, 1:12pm » |
Quote Modify
|
Why would you say that? The second player can never win, since the first can always draw or do better; so there wouldn't be a reason to choose to be second player.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wiley
Newbie
Posts: 12
|
|
Re: hard coin problem
« Reply #11 on: Aug 17th, 2011, 11:31am » |
Quote Modify
|
on Aug 13th, 2011, 1:12pm, towr wrote:| Why would you say that? The second player can never win, since the first can always draw or do better; so there wouldn't be a reason to choose to be second player. |
|
Yeah, you are right. Had got wrong picture in my head..
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: hard coin problem
« Reply #12 on: Sep 12th, 2011, 1:21pm » |
Quote Modify
|
on Aug 7th, 2011, 9:47pm, towr wrote:| A greedy algorithm is not optimal for this problem. Just take 3,10,2,1 as example, you'd get 5 as first player and the second player would get 11. |
|
But for sequence like 2,5,25,6,1,16 the parity strategy gives 28-27 while there is possibility to gain 42-13.
Seems to me optimal strategy is to take difference of the border two numbers and chose the end with higher difference.
(16-1)>(2-5) ... take 16 (2-5)>(1-6) ... take 2
(1-6)>(5-25) ... take 1 (6-25)>(5-25) ... take 6
(25-5)>(5-25) ... take 25 ... hmm algorithm fails so take the last number 5.
|
| « Last Edit: Sep 12th, 2011, 1:38pm by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: hard coin problem
« Reply #13 on: Sep 12th, 2011, 10:04pm » |
Quote Modify
|
on Sep 12th, 2011, 1:21pm, Hippo wrote:| But for sequence like 2,5,25,6,1,16 the parity strategy gives 28-27 while there is possibility to gain 42-13. |
|
Winning is winning. As long as you win when you can, I don't see how winning in a different way is more optimal.
Quote:| Seems to me optimal strategy is to take difference of the border two numbers and chose the end with higher difference. |
|
Try that on 99,100,101,102,4,6,8,10
|
| « Last Edit: Sep 12th, 2011, 10:10pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: hard coin problem
« Reply #14 on: Sep 13th, 2011, 4:53am » |
Quote Modify
|
on Sep 12th, 2011, 10:04pm, towr wrote:
Winning is winning. As long as you win when you can, I don't see how winning in a different way is more optimal.
Try that on 99,100,101,102,4,6,8,10 |
|
Nice refutation
OK, the question was to have positive difference.
Other question is to maximize the difference ...
OK suppose we have to gain just possitive difference and the odd sum equals even sum....
For odd player taking maximal border number is optimal counterstrategy as it gives \sumeven and \sumodd no border with one of border options.
Even player choses maximum so making \sumodd minimal gives better chances.
For sequence 100,103,25,32,20,8,30,33,46,38,8,15
Starting from left leads to difference 0, while starting from righ leads to difference 10 due to switch on 8,30,33,46,38,8 subsequence.
When starting from left the opponent switches on 8,30,33,46,38,8,15 what leads to the original even/odd partition.
|
| « Last Edit: Sep 13th, 2011, 5:56am by Hippo » |
IP Logged |
|
|
|
RajivG
Junior Member
Gender:
Posts: 72
|
|
Re: hard coin problem
« Reply #15 on: Oct 12th, 2011, 2:07am » |
Quote Modify
|
on Aug 4th, 2011, 4:12am, RajivG wrote:we have n coins in a row with different denomination on it and placed randomly
game rule says that either left most or right most coin can be picked and only two players can play this game (one will pick one coin at a time)
now we have to come up with a sequence which make me winner (my sum of denomination of n/2 coins should greater than sum of denomination of remaining n/2 coins)
I tried to solve this but every time I ended up reducing this problem to NP
greedy approach will not work i deduced that but i am not able to find DP solution as well
but interviewer said there is a solution for it because we restrict on possible sequences
any help
|
|
finally i got a solution for it, (though it took so many days to come out 4m my mind)
posting here to get it reviewed if solution has any flaw
let us say sequence is
2,5,8,10,25,26,21,6,1,4
now start creating a simple binary tree (choice tree more correctly)
you have choice to pick either 2 or 4
........................0
...................2.......4
now further if we pick 2 then we have choice for picking 5 or 4 and if we pick 4 then we have choice for 2 and 1
so now tree looks like
........................0
.................2..........4
.............5.....4...2.......1
this way we will keep expanding our tree
once tree is done then we just need to find a path on which the sum is higher (which is simple to find)
so max sum path is our answer
let me know if i am wrong some where
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: hard coin problem
« Reply #16 on: Oct 12th, 2011, 6:32am » |
Quote Modify
|
on Oct 12th, 2011, 2:07am, RajivG wrote:
finally i got a solution for it, (though it took so many days to come out 4m my mind)
posting here to get it reviewed if solution has any flaw
let us say sequence is
2,5,8,10,25,26,21,6,1,4
now start creating a simple binary tree (choice tree more correctly)
you have choice to pick either 2 or 4
........................0
...................2.......4
now further if we pick 2 then we have choice for picking 5 or 4 and if we pick 4 then we have choice for 2 and 1
so now tree looks like
........................0
.................2..........4
.............5.....4...2.......1
this way we will keep expanding our tree
once tree is done then we just need to find a path on which the sum is higher (which is simple to find)
so max sum path is our answer
let me know if i am wrong some where
|
|
It must be wrong ... you forgot there is another player ... so if you choose one parity and change sign in the depths of the chosen parity ... it would correspond to the game, but with minimax search ... .
|
|
IP Logged |
|
|
|
RajivG
Junior Member
Gender:
Posts: 72
|
|
Re: hard coin problem
« Reply #17 on: Oct 12th, 2011, 7:21am » |
Quote Modify
|
on Oct 12th, 2011, 6:32am, Hippo wrote:
It must be wrong ... you forgot there is another player ... so if you choose one parity and change sign in the depths of the chosen parity ... it would correspond to the game, but with minimax search ... . |
|
wait.... problem says that i need to give a winning sequence only, if not followed player may loose (loosing reason could be same as you said)
|
|
IP Logged |
|
|
|
Dufus
Newbie
Posts: 43
|
|
Re: hard coin problem
« Reply #18 on: Dec 25th, 2011, 5:02am » |
Quote Modify
|
FWIW, I came across a similar problem,
Consider a row of n coins of values v(1) ... v(n), where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.
It seems the problem can be solved using Dynamic programming in O(N2) time and O(N2) extra space.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: hard coin problem
« Reply #19 on: Dec 26th, 2011, 9:22am » |
Quote Modify
|
on Dec 25th, 2011, 5:02am, Dufus wrote:FWIW, I came across a similar problem,
Consider a row of n coins of values v(1) ... v(n), where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.
It seems the problem can be solved using Dynamic programming in O(N2) time and O(N2) extra space. |
|
Is it similar? It looks exactly the same problem to me 
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: hard coin problem
« Reply #20 on: Dec 26th, 2011, 10:06am » |
Quote Modify
|
In the original problem you only have to win, here you want to get the maximum score (which usually means you win unless you draw, but it's typically more effort as well).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print