11010 - Tic-Tac-Tough

[mido]

tough indeed...

would normal,direct min-max with memoization work here, or must I use shortcuts...?

thanks...

[arsalan_mousavian]

i havn't solved this problem actually , but i think you need shortcut to solve it because of the part of the problem statement ("If a player (temporarily) has no moregames on his pile when it is his turn" )

[arsalan_mousavian]

is there any greedy aproach for taking optimized strategy in choosing board to play ?
thanks in advance

[sclo]

It is possible to solve this using part greedy and part dp.

For each board, use dp to determine the optimal outcome if mary starts, and if johnny starts.

Think about why we can consider each board independently from the others,
and why it doesn't really matter if a player temporarily has no board.

All that remains to be done is to figure out which board johnny and mary would pick. You can prove that a greedy approach can be used to pick the board.

[arsalan_mousavian]

dear sclo
my algorithm is exactly as same as you explained
first i calculate the final result of each board if john or mary start playing on that board ,then in the second stage for each player i choose the board that has the most advantage to him/herself and most disadvantage for his/her oponnent but i got WA over and over , do you have any idea ?
thanks . . .

[sclo]

dear sclo
my algorithm is exactly as same as you explained
first i calculate the final result of each board if john or mary start playing on that board ,then in the second stage for each player i choose the board that has the most advantage to him/herself and most disadvantage for his/her oponnent but i got WA over and over , do you have any idea ?
thanks . . .

That's exactly what I did. Maybe you code to determine which board to pick is not correct, or there's something wrong with the dp.

[arsalan_mousavian]

for choosing the board i do as follow :
first i assign a value to each board for each player as follow :

1. who starts the game will win the game : value = 1000 ;
2. the result of the game does not depend on who starts the game : value = 0 ;
3. if by starting the game player will get better score : value = 500 ;

then whenever is the player's turn to choose, i choose the most value and according to the result of that board
i update the scores , and print the output according to these scores

is it right ?

Thanks

P.S : i used backtracking and memoization for caculating the result of the board according to the starter player

[sclo]

1. who starts the game will win the game : value = 1000 ;
2. the result of the game does not depend on who starts the game : value = 0 ;
3. if by starting the game player will get better score : value = 500 ;

my ranking function for these are quite different from yours. I have 9 possible scores (since there are 9 possible outcome for 2 players, some of these are not possible given the constraints of the board, but i don't care)

Johnny's ranking functions: (pick min score)
0,1 -> 0
-1,1 -> 1
0,-1 -> 2
1,1 -> 3
-1,-1 -> 4
0,0 -> 5
-1,0 -> 6
1,-1 -> 7
1,0 -> 8

( a,b->c stands for if outcome a given mary starts, b given johnny starts, the ranking would be c; -1: tie, 1:johnny wins, 0:mary wins)

using the same reasoning, we can derive mary's scoring functions from johnny's scoring functions.

P.S : i used backtracking and memoization for caculating the result of the board according to the starter player

that's the same as my 3^9 dp

[arsalan_mousavian]

Johnny's ranking functions: (pick min score)
0,1 -> 0
-1,1 -> 1
0,-1 -> 2
1,1 -> 3
-1,-1 -> 4
0,0 -> 5
-1,0 -> 6
1,-1 -> 7
1,0 -> 8

( a,b->c stands for if outcome a given mary starts, b given johnny starts, the ranking would be c; -1: tie, 1:johnny wins, 0:mary wins)

i thoroughly misunderstood your scoring function ,can you plz explain it more , because the above definition is not clear for me
thanks
Arsalan

[sclo]

Johnny's ranking functions: (pick min score)
0,1 -> 0
-1,1 -> 1
0,-1 -> 2
1,1 -> 3
-1,-1 -> 4
0,0 -> 5
-1,0 -> 6
1,-1 -> 7
1,0 -> 8

( a,b->c stands for if outcome a given mary starts, b given johnny starts, the ranking would be c; -1: tie, 1:johnny wins, 0:mary wins)

i thoroughly misunderstood your scoring function ,can you plz explain it more , because the above definition is not clear for me
thanks
Arsalan

I put it into words: The following are johnny's ranking of the boards, the
lower rank the better.
if mary start, mary win game and if johnny start,johnny win, then rank=0
if mary start, tie game and if johnny start, johnny win, then rank=1
if mary start, mary win and if johnny start, tie game, then rank=2
if mary start, johnny win, and if johnny start, johnny win, then rank=3
etc.

[arsalan_mousavian]

thanks sclo i got AC , there was a mistake in my program . i forgot to switch the player that starts the board when the final state is draw
thank you

[polone]

I got WA several times..
Please suppose some test data

[Dreamer#1]

I considered the 1st, 3rd...(odd numbered) boards and 2nd, 4th.. (even numbered) ones separately as Jhonny's and Maria's boards respectively and processed them one by one. For any board I precalculated the its result with 'X' as the first player and 'O' as the second, so incase of Maria's board I just swapped the 'X's and 'O's in it and for Jhonny's I kept it as it is. During the contest I got several WAs with this idea and my implementation is probably ok so I feel I've misunderstood some part of the problem. Its been a week since the contest so I might be saying something wrong here as well but I don't feel like reading the problem over again, I read it atleast 5 times already during the contest. My precalculation of the board stores the outcome of a given board as 1 if player1 wins, 0 if player 1 loses, -1 if player2 wins (ofcourse considering player1 starts). I still can't understand what was I doing wrong. Someone please help me out. Some test cases might be handy as well.

Thanks in advance.

[arsalan_mousavian]

read previous posts , i think it will help you

[little joey]

I considered the 1st, 3rd...(odd numbered) boards and 2nd, 4th.. (even numbered) ones separately as Jhonny's and Maria's boards respectively and processed them one by one.

This is wrong. The problem statement says

Then they divided the game fields between them: first Johnny selected one, then Mary, then Johnny again, etc., until all were divided.

This means Johnny can select any one of the game fields, not only the first, and then Mary can select any one of the remaining, not only the second. So at each turn of the selection process, each player chooses the game field he/she likes best from the remaining game fields.
Sorry if this part of the description was not totaly clear.