11534 - Say Goodbye to Tic-Tac-Toe

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

Moderator: Board moderators

Post Reply
Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

11534 - Say Goodbye to Tic-Tac-Toe

Post by Leonid » Sun Oct 19, 2008 11:17 pm

Any idea how to solve the task? :)

altertain
New poster
Posts: 9
Joined: Sat Jan 13, 2007 10:14 am

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by altertain » Mon Oct 20, 2008 8:50 am

If you don't know about grundy number, you should learn it. :)
Lee, Taeyoon

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by mmonish » Tue Oct 21, 2008 11:16 am

I am getting WA in this prob. Anyone please check the following cases or give any tricky case.
Input

Code: Select all

12
..
........................
.....X...O....XO
.
...XOXOXOXO
...X..........O...X....O..O.....X....XO
XOXO
...XOX
............................................................
XOXOXOXOXOXOXOXOXO........................................
XOXO.......XOXO
X....O....X
Output

Code: Select all

Impossible.
Impossible.
Possible.
Possible.
Possible.
Possible.
Impossible.
ImPossible.
Impossible.
Possible.
Impossible.
Possible.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by baodog » Tue Oct 21, 2008 12:40 pm

I get the same answers as you do.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by mmonish » Tue Oct 21, 2008 1:54 pm

>>baodog
thx for ur help. Now i have got AC.. Silly mistake in my coding..

SerailHydra
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by SerailHydra » Tue Oct 21, 2008 2:56 pm

Can anyone tell me how to handle this input with SG function?

..O.X.

The answer should be "Possible."

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by mmonish » Tue Oct 21, 2008 3:32 pm

suppose u r playing 3 nim games here
1. ..O
2. O.X
3. X.

each game canbe represented by three values.first length of the game , second value on the left side and third value on the right side. for each game u can place a X or O in positions from 0 to len-1 and split the game into 2 subgames.The grundy number for each game is simply the xor of the both subgames grundy number.u must take special care about the terminal positions.

hope this helps..
Last edited by mmonish on Tue Oct 21, 2008 4:25 pm, edited 1 time in total.

SerailHydra
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by SerailHydra » Tue Oct 21, 2008 3:41 pm

Can you print the SG function for these three subgame? I think it maybe more than 1.

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by Leonid » Wed Oct 22, 2008 1:59 am

Are there any similar problems to this in UVA?

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by mmonish » Wed Oct 22, 2008 2:57 am

>>SerailHydra
SG value for this trree subgames are 2,0and 1.
>>Leonid
I don't know is there any similar probs in UVA.But u can try this prob https://www.spoj.pl/problems/TRIOMINO/ in spoj.it is quite similar this one..

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: 11534 - Say Goodbye to Tic-Tac-Toe

Post by fushar » Fri May 08, 2009 5:07 pm

Can anyone explain me thoroughly how to solve this problem with grundy number? Please....

Post Reply

Return to “Volume 115 (11500-11599)”