wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> hard coin problem
        
(Message started by: RajivG on Aug 4^th, 2011, 4:12am)

Title: hard coin problem
Post by RajivG on Aug 4^th, 2011, 4:12am

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???

Title: Re: hard coin problem
Post by Grimbal on Aug 4^th, 2011, 6:17am

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.

Title: Re: hard coin problem
Post by paras on Aug 4^th, 2011, 12:06pm

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 :)

Title: Re: hard coin problem
Post by inexorable on Aug 4^th, 2011, 12:06pm

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.

Title: Re: hard coin problem
Post by agent_purge on Aug 6^th, 2011, 10:04am

Solved using DP in O(n2)

[hideb]
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]
[/hideb]

Title: Re: hard coin problem
Post by towr on Aug 6^th, 2011, 1:47pm

on 08/04/11 at 06:17:24, 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.

Title: Re: hard coin problem
Post by sat90 on Aug 7^th, 2011, 1:19am

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--;
}
}

Title: Re: hard coin problem
Post by sat90 on Aug 7^th, 2011, 1:20am

time taken will be O(n).

Title: Re: hard coin problem
Post by towr on Aug 7^th, 2011, 9:47pm

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.

Title: Re: hard coin problem
Post by wiley on Aug 13^th, 2011, 2:28am

Winning player must have choice to be player1(1st turn) or player2(2nd turn) in game. :)

Title: Re: hard coin problem
Post by towr on Aug 13^th, 2011, 1:12pm

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.

Title: Re: hard coin problem
Post by wiley on Aug 17^th, 2011, 11:31am

on 08/13/11 at 13:12:56, 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..

Title: Re: hard coin problem
Post by Hippo on Sep 12^th, 2011, 1:21pm

on 08/07/11 at 21:47:18, 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.

Title: Re: hard coin problem
Post by towr on Sep 12^th, 2011, 10:04pm

on 09/12/11 at 13:21:03, 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

Title: Re: hard coin problem
Post by Hippo on Sep 13^th, 2011, 4:53am

on 09/12/11 at 22:04:40, 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 \sum_even and \sum_{odd no border with one of border} options.
Even player choses maximum so making \sum_odd 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.

Title: Re: hard coin problem
Post by RajivG on Oct 12^th, 2011, 2:07am

on 08/04/11 at 04:12:49, 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

Title: Re: hard coin problem
Post by Hippo on Oct 12^th, 2011, 6:32am

on 10/12/11 at 02:07:57, RajivG 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 ... .

Title: Re: hard coin problem
Post by RajivG on Oct 12^th, 2011, 7:21am

on 10/12/11 at 06:32:39, Hippo wrote:

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)

Title: Re: hard coin problem
Post by Dufus on Dec 25^th, 2011, 5:02am

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(N²) time and O(N²) extra space.

Title: Re: hard coin problem
Post by birbal on Dec 26^th, 2011, 9:22am

on 12/25/11 at 05:02:12, Dufus wrote:

Is it similar? It looks exactly the same problem to me :P

Title: Re: hard coin problem
Post by towr on Dec 26^th, 2011, 10:06am

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).