## 10501 - Simplified Shisen-Sho

Moderator: Board moderators

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

### 10501 - Simplified Shisen-Sho

I can't understand what it means.
Can anybody give some explanation to me?
Thanks.

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
In my viewpoint

________
| ##### |
@#####@
#######
#######
#######
####### in this situation the mark "@" can be removed
because it is connected by two v-lines and one h-line

@__###&
&&| &&&&
&&| &&&&
&&|____@ in this situation the mark "@" can also be removed
because it is connected by two h-lines and one v-line

the difference between the two cases is that
I draw the lines in the outer section of the grid in the first
and in the inner section of the grid in the second

the line can be draw in the spaces left by previous removed
tiles or the bound of the grid

if the tiles are adjoined you also can remove them
the problem says that ->
"(As a side effect, this also means that you can remove two tiles of the same picture that are next to each other in horizontal or diagonal."

I think the problemsetter want to express that in horizontal or vertical,
not diagnal.

Sorry, I am poor in English.

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
Thank you very much.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Anyone knows how to solve the problem quickly?
My thought is using BFS,but it can't be proved nothing left.

DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan
I have wondered the following statement:
(As a side effect, this also means that you can remove two tiles of the same picture that are next to each other in horizontal or diagonal.)
I think it should be "horizontal or vertical", right?
Is the mistake of the problem?

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

I have indicated that in previous post.

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm
just use DFS

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

### 10501

hi, i am trying to solve 10501, but i just cant get my solution to work in time.
can anyone please give a hint?

New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil
Hi,
this problem accept multiple output?

thanks,

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10501 - Simplified Shisen-Sho

Does anyone knows any tricky test data? I got lots of W.A. and didn't know why. Since the definition of this problem is not so clear, can anyone help me clarify the definition? Thanks!
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10501 - Simplified Shisen-Sho

Finally solve this problem. My previous W.A. version uses greedy strategy to eliminate pairs with backtracking. After adding backtrack into my program, I finally got A.C.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10501 - Simplified Shisen-Sho

I got AC. There is only one test case. This problem has a special judge that accepts multiple outputs. The problem statement has some typos.

This line:
(As a side effect, this also means that you can remove two tiles of the same picture that are next to each other in horizontal or diagonal.)
Should be:
(As a side effect, this also means that you can remove two tiles of the same picture that are next to each other in horizontal or vertical.)

This line:
Each tile in the board is labeled after its position in the board, being (1,1) the upper left corner and (n,m) the lower left.
Should be:
Each tile in the board is labeled after its position in the board, being (1,1) the upper left corner and (n,m) the lower right.
Check input and AC output for thousands of problems on uDebug!

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 10501 - Simplified Shisen-Sho

The judge data may be a little weak, so using simple DFS can get AC.