211 - The Domino Effect

All about problems in Volume 2. 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
AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

211 - The Domino Effect

Post by AlexandreN » Tue Aug 06, 2002 7:25 pm

Maybe I don't understood what is a valid board of bones
for a given board of pips but I think that for any board
of pips, including the ones in the sample output, there are
a lot of boards of bones.

For example, for the for the first board in the sample input,

5 4 3 6 5 3 4 6
0 6 0 1 2 3 1 1
3 2 6 5 0 4 2 0
5 3 6 2 3 2 0 6
4 0 4 1 0 0 4 1
5 2 2 4 4 1 6 5
5 5 3 6 1 2 3 1

the sample output has only one solution but I think that there
are several trivial others like:


[5 4] [3 6] [5 3] [4 6]
[0 6] [0 1] [2 3] [1 1]
[3 2] [6 5] [0 4] [2 0]
[5 3] [6 2] [3 2] [0 6]
[4 0] [4 1] [0 0] [4 1]
[5 2] [2 4] [4 1] [6 5]
[5 5] [3 6] [1 2] [3 1]

replacing the pairs [a b] by pip[ a ][ b ] pip[ a ][ b ]:

24 24 22 22 21 21 25 25
7 7 2 2 15 15 8 8
15 15 27 27 5 5 3 3
21 21 18 18 15 15 7 7
5 5 11 11 1 1 11 11
17 17 16 16 11 11 27 27
26 26 22 22 9 9 10 10

or
_ _ _ _ _ _ _ _
5 4 3 6 5 3 4 6
0 6 0 1 2 3 1 1
- - - - - - - -
_ _ _ _ _ _ _ _
3 2 6 5 0 4 2 0
5 3 6 2 3 2 0 6
- - - - - - - -
4 0 4 1 0 0 4 1
5 2 2 4 4 1 6 5
- - - - - - - -
[5 5][3 6][1 2][3 1]

replacing the vertical pairs between _ e - e the horizontal pairs between []:

6 25 4 13 17 19 11 13
6 25 4 13 17 19 11 13
21 15 28 17 4 16 3 7
21 15 28 17 4 16 3 7
24 3 16 11 5 2 25 12
24 3 16 11 5 2 25 12
26 26 22 22 9 9 10 10

is this correct ???

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

Post by broderic » Tue Aug 06, 2002 10:02 pm

I don't think that's correct. for instance, you have the [0 4] domino
repeated twice (the second time as [4 0]). But there is only one of each
domino, so that layout isn't valid.

When i solved this problem I assumed that each domino had to be used
exactly once.

Hope this helps.

AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

Post by AlexandreN » Wed Aug 07, 2002 2:07 pm

Thank you very much.
Now I understand this problem.

zizi
New poster
Posts: 7
Joined: Fri Jan 30, 2004 4:51 am

211

Post by zizi » Fri Jan 30, 2004 4:53 am

I use DFS for this problem but it was very slow to get the result. What's the best solution for this problem

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Re: 211

Post by junbin » Fri Jan 30, 2004 8:30 am

zizi wrote:I use DFS for this problem but it was very slow to get the result. What's the best solution for this problem
I believe DFS is the correct method to solve this.. but you have to add in a lot of pruning.

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

211: minor error in presented output

Post by GreenPenInc » Thu Aug 26, 2004 1:37 am

I believe there is an error in the output as presented in the description for 211. In the first problem instance, the first column is lined up under the 'o' in 'Layout': column 4. However, in the second, it falls under the 'u', which is column 5. I cannot conceive how this could have been output by any reasonable program. And since my program (which adds the initial space in all cases, following the most common usage) got AC on the first attempt, I believe the pip data for Layout #1 is improperly justified.
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

User avatar
Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

About the output

Post by Ndiyaa ndako » Sat Nov 04, 2006 8:18 am

Do not forget to add a newline after the last line of output.

adelar
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

Test Cases

Post by adelar » Fri Jun 29, 2007 5:31 pm

thanks, I got AC.

Post Reply

Return to “Volume 2 (200-299)”