10561  Treblecross
Moderator: Board moderators
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
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
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
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

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
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 )
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
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 )
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

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
Hi Andrey!
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.
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
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.
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
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
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.
10561 can some one help me out?
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.
Sana.

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 10561  Treblecross
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
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.

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 10561  Treblecross
I got AC today, but the following IO doesn't match with 'Dreamer#1's output:
His output:
My output:
From this, I guess my solution is wrong and judge data doesn't contain this. Can anyone else check ?
Code: Select all
1
........................................................................................................................................................................................................
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
Code: Select all
WINNING
1 9 12 44 63 84 87 90 111 130 162 165 173
You should not always say what you know, but you should always know what you say.

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 10561  Treblecross
Now it's ok
You should not always say what you know, but you should always know what you say.