11010 - Tic-Tac-Tough

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

11010 - Tic-Tac-Tough

Post by mido »

tough indeed...

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

thanks...

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by 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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by 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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

arsalan_mousavian wrote: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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

arsalan_mousavian wrote: 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.
arsalan_mousavian wrote: 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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

sclo wrote: 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

arsalan_mousavian wrote:
sclo wrote: 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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

thanks sclo i got AC :D , 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
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone »

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

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by 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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

read previous posts , i think it will help you

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Dreamer#1 wrote: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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Post Reply

Return to “Volume 110 (11000-11099)”