Problem 1: Gỡ rối chương trình

Độ khó : Trung bình

Khi gỡ rối 1 chương trình, Thomas nhận thấy rằng một lỗi trong chương trình có thể liên kết với sự tồn tại của một thứ được gọi là hình vuông sát thủ trong bộ nhớ của chương trình. Bộ nhớ của chương trình là một ma trận bao gồm R hàng và C cột và chỉ chứa 0 hoặc 1. Một hình vuông sát thủ là một ma trận con hình vuông trong bộ nhớ, chứa nhiều hơn 1 kí tự, mà, khi xoay 180 độ trông vẫn như cũ.
Ví dụ : Ma trận sau đây chứa 3 hình vuông sát thủ.
            101010       101010       101010        101010
            111001       111001       111001        111001
            101001       101001       101001        101001
            Bộ nhớ            các hình vuông sát thủ
Thomas đang muốn biết liệu rằng có một mối liên hệ nào đó giữa kích thước của hình vuông sát thủ lớn nhất và lỗi của chương trình. Hãy giúp đỡ Thomas viết 1 chương trình, cho sẵn sơ đồ của bộ nhớ, đưa ra kích thước lớn nhất của hình vuông sát thủ. Kích thước của hình vuông sát thủ là số hàng (hay số cột) mà nó chứa. Trong ví dụ trên kích thước của hình vuông sát thủ lần lượt là 3,2,2.

Input:   

Dòng đầu tiên chứa 2 số nguyên, R và C, nhỏ hơn hoặc bằng 300.
R dòng tiếp theo, mỗi dòng sẽ chứa C kí tự ('0' hoặc '1'), không có khoảng trống.

Output: 

Đưa ra kích thước của hình vuông sát thủ lớn nhất trên 1 dòng duy nhất, hoặc -1 nếu không có hình vuông sát thủ.

Ví dụ:  

           - input:
          3 6
          101010
          111001
          101001
          - output
               3

 - Giới hạn R,C <= 300, ta có thể đoán rằng thuật toán chuẩn khoảng N^3 (N coi như chiều dài cạnh của bảng, ở đây vai trò của các cạnh bảng là như nhau, N <=300). 

 - Với những bài toán tin độ khó TB trở lên, chúng ta không thể “Đề bảo gì thì làm nấy “được, mà phải tìm xem trong yêu cầu đề đặt ra có gì đó đặc biệt, hay liên quan đến những tính chất có thể giúp chúng ta giảm thiểu khối lượng tính toán.

1) Một hình vuông khi xoay 180 độ nó sẽ thành ra cái quái gì ???

- Hình vuông 1x1, dĩ nhiên nó sẽ thành chính nó.

- Hình vuông 2x2, 

                +giả sử hình vuông đc đánh số

1	2
3	4

                  + bây giờ xoay nó :

4	3
2	1

        

** Nhận xét:  

+ hàng 1 là đảo ngược của hàng 2 ( 4,3 là ngược lại của 3,4), và  hàng 2 là đảo ngược của hàng 1 (2,1 là đảo ngược của 1,2 ). 

+ cột 1 là đảo ngược của cột 2 (4-2 ngược của 2-4, đánh từ trên xuống nhé),... And so on .....

- Hình vuông 3x3,  

+ giả sử hình vuông đc đánh số như sau

1	2	3
4	5	6
7	8	9

+ Và xoay nó 180 độ 

9	8	7
6	5	4
3	2	1

** Nhận xét:

+ bây giờ ta nhận thấy rằng các hàng 1 2 3 là đảo ngược của các hàng 3 2 1.

+ các cột 1 2 3 là đảo ngược của các cột 3 2 1.

- Hình vuông MxM, các trường hợp tổng quát mà ta có thể xét với 1 hàng hay cột bất kì.

+ Với hàng i nào đó :

Ta xoay 90 độ theo chiều ngược kim đồng hồ 2 lần ( tương đương xoay 180 độ )

1	2	3	4	5	6	7	8
O	O	O	O	O	O	O	O
O	O	O	O	O	O	O	O

** Ban đầu

O	O	1
O	O	2
O	O	3
O	O	4
O	O	5
O	O	6
O	O	7
O	O	8

**Xoay lần 1:

O	O	O	O	O	O	O	O
O	O	O	O	O	O	O	O
8	7	6	5	4	3	2	1

** Xoay lần 2:

** Nhận xét : sau khi xoay, hàng i sẽ đc dịch chuyển lên hàng j, và bị đảo ngược lại, ah mà khoan, hàng j và hàng i như thế nào với nhau nhỉ, hãy nhìn các chữ O mà mình đánh vào mảng, hàng i và j cách đều chính giữa bảng(hay 2 đầu bảng cũng đc), hay nói cách khác, i và j ở vị trí đối xứng với nhau qua chính giữa bảng.

+ Và với cột cũng vậy, bạn hãy viết ra giấy và kiểm nghiệm :)

>>>> khi xoay hình vuông 180 độ, bảng mới sẽ đc hình thành theo quy tắc

+ hàng j sẽ là đảo ngược của hàng i ban đầu, với i,j ở vị trí đối xứng.

+ cột j sẽ là đảo ngược của cột i ban đầu, với i,j ở vị trí đối xứng.

2) Tính chất của HVST, tức khi nào 1 hình vuông là sát thủ

Nếu 1 hình vuông là hình vuông sát thủ,

Với i,j là 2 vị trí hàng/cột đối xứng nhau, thì hàng này phải là đảo ngược của hàng kia, để sao cho khi xoay 180 độ, sơ đồ bảng tại 2 hàng đó ko bị thay đổi,

** giải thích : đảo ngược của hàng i thế vào hàng j và bằng hàng j, rõ ràng hàng i,j là đảo ngược của nhau.

>> cột cũng như vậy lun, vai trò nó như nhau mà :)

3) Tính chất quy nạp

Cho hình vuông m x m, và hình vuông con (m-1)x(m-1) ở trung tâm, cách đều viền hình vuông mẹ. Nếu hình vuông con là hình vuông sát thủ, hàng m là đảo của hàng 1, cột m là đảo của cột 1. Thỳ hình vuông m x m là hình vuông sát thủ.

	O	O
	O	O

Phần đc fill ‘O’ là hình vuông con

** cái này khá dễ nhận ra :)

Ắt hẳn đến đây ai cũng có thể dễ dàng nhận ra  phương pháp làm bài này là gì rồi. :)

4) Phương pháp quy hoạch động N^4

Dựa vào tính chất quy nạp ở trên ta dễ dàng nghĩ ra được cách làm bài này PP QHĐ.

Ở đây hình vuông có 2 loại, loại có cạnh lẻ (tâm đối xứng là giao hàng chính giữa, cột chính giữa ) và loại cạnh chẵn.

** Hình minh họa:

	O
O	O	O
	O

	O	O
	O	O

Lẻ (trên)     Chẵn(dưới)

_ Ta sẽ coi tâm của hình vuông cạnh lẻ là 1 ô chính giữa đc tô đỏ như trên, còn tâm của hình vuông cạnh chẵn là hình vuông cạnh 2 ở chính giữa ( tô vàng ở trên ). 

_ Xét lần lượt từng tâm hình vuông như định nghĩa ở trên và tâm đó cũng là 1 hình vuông đối xứng (chấp nhận kích thước 1x1) , với mỗi tâm, ta sẽ mở rộng về 4 phía 1 đơn vị, tức có thêm 2 cột mới ở 2 bên, 2 hàng mới ở trên dưới, và kiểm tra xem 2 hàng/ cột mới thêm vào có phải là đảo ngược của nhau hay không. Nếu đúng, ta tiếp tục mở rộng đến khi điều kiện trên ko thỏa mãn hay hết biên giới bảng.

- Bước mở rộng tốn O(N), bước xét đảo ngược tốn O(N), và bước xét tất cả các tâm O(N^2), chúng ta mất O(N^4) đối với phương pháp này.

** Tăng tốc chương trình:

Thuật toán mà mình muốn nói ở đây có đpt là O(N^4/64), với N<=300, thỳ đpt xấp xỉ 126,5 triệu, nhưng thực tế thỳ nhỏ hơn nhiều.???

Tư tưởng vẫn y như cũ, nhưng chúng ta sẽ cải tiến bước so sánh liệu rằng 2 hàng cột có là đảo ngược của nhau hay không, vẫn là đảo ngược lại, và so sánh giống nhau hay không. Nhưng tại sao tốc độ lại đc đẩy nhanh lên 64 lần.

Để ý bảng chúng ta đang xét là bảng nhị phân, chứa 0 hoặc 1, vì vậy ta sẽ biểu diễn các phần tử bằng dãy bit của các số nguyên lớn. Độ lớn không gian cần xét sẽ giảm đi 64 lần, và ta chỉ cần so sánh các số nguyên này.

>>>>> gọi M[i][j][1] là số biểu diễn dãy 0,1 ở hàng i, từ vị trí j-63 đến j.

>>>>> M[i][j][2] là số biểu diễn dãy 0,1 ở hàng i, từ vị trí j đến j+63.

Tương tự với cột.

ĐPT 126,5 triệu có vẻ lớn nhưng thực tế lại nhỏ hơn, vì với mỗi tâm, chưa chắc ta đã mở rộng đến N lần, hay mở rộng rất nhiều lần. Cộng thêm việc đặt cận thì khối lượng tính toán sẽ nhỏ đi rất nhiều.

** thực nghiệm Máy Celeron B815 2x1,6 GHz, chạy test 300x300 toàn số 1 chỉ 0,2s; hay chạy test 0,1 xen kẽ cũng chỉ 0,2. Các test max random chỉ khoảng 0,15s. Vẫn đảm bảo time chạy không quá lâu :)