10501 - Simplified Shisen-Sho

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
dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

10501 - Simplified Shisen-Sho

Post by dwyak » Tue Jul 15, 2003 3:01 pm

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

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

Post by Ghost77 dimen » Tue Jul 15, 2003 4:07 pm

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. :D

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

Post by dwyak » Wed Jul 23, 2003 5:05 am

Thank you very much. :D

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Fri Jul 25, 2003 7:00 am

Anyone knows how to solve the problem quickly?
My thought is using BFS,but it can't be proved nothing left.

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Post by DemonCris » Thu Sep 11, 2003 6:10 am

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?

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

Post by Ghost77 dimen » Fri Sep 12, 2003 8:58 am

8)

I have indicated that in previous post.

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

Post by gush » Wed Dec 10, 2003 4:05 pm

just use DFS

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

10501

Post by fpavetic » Thu Apr 20, 2006 4:08 pm

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

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

Post by adelar » Thu Dec 13, 2007 1:02 am

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

Post by DD » Tue Sep 14, 2010 7:11 pm

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

Post by DD » Thu Apr 07, 2011 6:14 am

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. :D
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

Post by brianfry713 » Thu Jan 31, 2013 10:38 pm

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: 128
Joined: Wed May 18, 2011 3:04 pm

Re: 10501 - Simplified Shisen-Sho

Post by metaphysis » Sat Aug 18, 2018 5:15 pm

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

muazuicom22
New poster
Posts: 25
Joined: Tue Sep 11, 2018 10:32 pm

Post by muazuicom22 » Sat Sep 29, 2018 6:13 pm

CTY TDL CHUYÊN NHẬN LÀM GIẤY TỜ :

Kính gửi Quý khách hàng , Cty TDL chúng tôi

Nhận làm tất cả các loại giấy tờ liên quan đến BĐS , từ dễ đến khó , khu vực Thành Phố HCM Và Bình Dương.
* Vẽ thiết kế xây dựng, xin giấy phép xây dựng.
* Vẽ hiện trạng đo đạc nhà đất, nhà máy, nhà xưởng.
*Dịch vụ thiết kế Phòng cháy, chữa cháy và Thẩm duyệt.
* Dịch vụ xin chuyển mục đích sử dụng đất.
* Dịch vụ hoàn công nhà xưởng, công trình trên đất.
* Dịch vụ tách thửa sổ đỏ, nhà đất, nhà xưởng, nhà máy.
* Dịch vụ xin cấp mới sổ đỏ, sổ hồng hoặc xin cấp Giấy chứng nhận Quyền sử dụng đất, quyền sở hữu nhà ở và tài sản khác gắn liền với đất.
* Dịch vụ xác định lại ranh giới, thực trạng nhà đất, cấp sổ mới.
* Dịch vụ xem xét lại quy hoạch xây dựng.
* Dịch vụ hợp thức hóa nhà đất.
* Dịch vụ sang tên , đăng bạ sang tên chủ quyền, thừa kế di chúc.


Ai có nhu cầu liên hệ 0938.242.835 c.Hong.
Quý khách Lưu lại khi cần . Trân trọng cảm ơn. Uy Tin_ chinh chuan.
Chúc Anh chị một ngày tốt lành

Post Reply

Return to “Volume 105 (10500-10599)”