10561 - Treblecross

All about problems in Volume 105. 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
dapumptu
New poster
Posts: 5
Joined: Tue Nov 25, 2003 3:30 pm

Post by dapumptu »

Can someone help me check my grundy number for n= 0~44
, is it right????


0~9
011123034
10~18
111030321

250301212

303412103

032125030
Top
gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm

Post by gush »

the output should be as follows.

WINNING
3
LOSING

WINNING
3
WINNING
1 12 15 17 20 24 28 31 33 36 47
WINNING
3 5
WINNING
4 10 16 22 23 33 34 35 37 38 39 49 50 51
WINNING
17 20
WINNING
1 4 5 6 9
WINNING
3 6
WINNING
3
WINNING
11
WINNING
12
WINNING
3 12
WINNING
13 16
LOSING

WINNING
12 15
WINNING
11
WINNING
7
WINNING
1 3 7 8 17 18 19 28 29 33 35
WINNING
12 15
LOSING

WINNING
52 53 55 56
WINNING
23 29
Top
gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm

Post by gush »

the output should be as follows.

WINNING
3
LOSING

WINNING
3
WINNING
1 12 15 17 20 24 28 31 33 36 47
WINNING
3 5
WINNING
4 10 16 22 23 33 34 35 37 38 39 49 50 51
WINNING
17 20
WINNING
1 4 5 6 9
WINNING
3 6
WINNING
3
WINNING
11
WINNING
12
WINNING
3 12
WINNING
13 16
LOSING

WINNING
12 15
WINNING
11
WINNING
7
WINNING
1 3 7 8 17 18 19 28 29 33 35
WINNING
12 15
LOSING

WINNING
52 53 55 56
WINNING
23 29
Top
Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Contact Whinii F.

Post by Whinii F. »

Hi.
I read up some math, and solved this problem. But I did not understand the all background of this.. (I'm really bad in math :wink:)

I believe there should be another approach that is not based on game theory, and it is much more likely the "another method" is feasible for real contest environments. (Looking at Yarin's 0.15sec time confirmed it :) )

I tried to find one, but it was not easy. :(

Could anybody offer a helping hand? I'll greatly appreciate it.

Best regards,
JongMan
JongMan @ Yonsei
Top
Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov »

Hello, Whinii F.!

Why don't you like this method? To my mind it was one of the most beautiful problems and one of the best of my solutions!! :P

Great thanks to Jimmy M
Top
Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Contact Whinii F.

Post by Whinii F. »

Hi Andrey! :D

I just thought so because I am not good at math at all. :( Suppose that I faced this kind of problem in an actual contest environment. I don't think I would solve it, since I don't know this particular theory. So I just imagined of a different solution that can deal with some more general situations.

(Yeah, give some chance to those who are not good at math! :))

That was all. It was not intention, at all, to mean that the method was not good. :wink:

Thanks for paying attention. :)

And dapumptu:

Your table seems to be different from mine. My AC program has a table like:

0 ~ 9: 0 1 1 1 2 2 0 3 3 1
10 ~ 19: 1 1 0 4 3 3 3 2 2 2
20 ~ 29: 4 4 0 5 5 2 2 2 3 3
30 ~ 39: 0 5 0 1 1 1 3 3 3 5
JongMan @ Yonsei
Top
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 »

here are some test cases:
  • 39
    XX.....
    .....XX
    ...XX.
    .XX...
    .XX.X..XX.XX.
    ...
    XX.
    .XX
    .X.
    X.X
    X..
    ..X
    .....
    X.....X..X.............X....X..X
    .X.X...X
    ...............................................
    .X.X.X.................X...X.............X......
    X...........X.....X......X...................X.....
    .....X...........XX......
    .........
    .X.XX...
    .......X
    ...........XX
    .X..........XX
    XX..........XX
    .X.......X......
    X................X.
    X.......X........X....X...X
    .....................
    .............
    ...................................
    ............XX..........
    .........X.......................................X......
    .......................X......X.................X.......
    .X..............X.................X..........
    ..................................................
    ....................................................................................................
    ......................................................................................................................................................
    ........................................................................................................................................................................................................
  • WINNING
    3
    WINNING
    5
    WINNING
    3 6
    WINNING
    1 4
    WINNING
    1 4 7 10 13
    WINNING
    1 2 3
    WINNING
    3
    WINNING
    1
    LOSING

    WINNING
    2
    LOSING

    LOSING

    WINNING
    3
    LOSING

    WINNING
    3
    WINNING
    1 12 15 17 20 24 28 31 33 36 47
    WINNING
    3 5
    WINNING
    4 10 16 22 23 33 34 35 37 38 39 49 50 51
    WINNING
    17 20
    WINNING
    1 4 5 6 9
    WINNING
    3 6
    WINNING
    3
    WINNING
    11
    WINNING
    12
    WINNING
    3 12
    WINNING
    13 16
    LOSING

    WINNING
    12 15
    WINNING
    11
    WINNING
    7
    WINNING
    1 3 7 8 17 18 19 28 29 33 35
    WINNING
    12 15
    LOSING

    WINNING
    52 53 55 56
    WINNING
    23 29
    WINNING
    5 10 11 13 14 19 21 22 29 30 32 37 38 40 41 46
    WINNING
    7 8 18 50 51 83 93 94
    WINNING
    40 111
    WINNING
    5 11 21 22 24 26 34 38 45 50 64 65 69 75 78 81 91 93 94 96 97 104 105 107 108 110 120 123 126 132 136 137 151 156 163 167 175 177 179 180 190 196
hope it helps. you should get AC if you can pass the above cases.
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.
Top
Sana
New poster
Posts: 1
Joined: Wed Apr 07, 2004 6:02 pm

10561 can some one help me out?

Post by Sana »

I ve never submitted a problem on acm and this problem was assigned to me as my course assignment and it has quite heavy weitage and i am unable to solve it as am not good in Math..its due on 11 April can some one help me out with it? i ll be really thank full. if some one cant give me a sample solution if he can help me atleast to make up the logic it will be okay.. time is very short for me.
Sana.
Top
BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by BiK »

Marian or everybody else,

Do you know some good books about Grundy-Sprague numbers?

Thanks
Top
zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:
Contact zobayer

Re: 10561 - Treblecross

Post by zobayer »

Can anyone tell me whether I could check X.X type cases directly using grundy numbers or I just need to check them manually?
And for finding winning positions, if I check manually and using grundy at the same time, will it cause any trouble? Here, I mean by manual checking are those cases like XXX... or ...XXX or .....X.X..... ?
Thanks :)
You should not always say what you know, but you should always know what you say.
Top
zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:
Contact zobayer

Re: 10561 - Treblecross

Post by zobayer »

I got AC today, but the following IO doesn't match with 'Dreamer#1's output:

Code: Select all

1
........................................................................................................................................................................................................
His output:

Code: Select all

WINNING
5 11 21 22 24 26 34 38 45 50 64 65 69 75 78 81 91 93 94 96 97 104 105 107 108 110 120 123 126 132 136 137 151 156 163 167 175 177 179 180 190 196
My output:

Code: Select all

WINNING
1 9 12 44 63 84 87 90 111 130 162 165 173
From this, I guess my solution is wrong and judge data doesn't contain this. Can anyone else check ?
You should not always say what you know, but you should always know what you say.
Top
zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:
Contact zobayer

Re: 10561 - Treblecross

Post by zobayer »

Now it's ok :)
You should not always say what you know, but you should always know what you say.
Top
Post Reply

Return to “Volume 105 (10500-10599)”