Kết hợp theo chiều dọc của các ô

Question

Gần đây trong một cuộc cạnh tranh mã hóa, tôi đã xem qua câu hỏi này.

Chúng tôi có 1000 ô trong đó mỗi ô là ma trận 3x3. Mỗi ô trong ma trận có giá trị số nguyên từ 0 đến 9, biểu thị độ cao của ô. Vấn đề là để tìm các cặp tối đa như vậy mà chúng phù hợp hoàn hảo. Gạch có thể được luân chuyển để phù hợp. Bằng cách phù hợp trong nó có nghĩa là cho ngói A và gạch B

A [i] + B [i] = const cho i = 0-8

Cách tiếp cận tôi nghĩ cho vấn đề này là tôi có thể duy trì giá trị băm tương ứng với từng ô. Sau đó, tôi sẽ tìm thấy sự kết hợp có thể có của gạch mà có thể là một phù hợp có thể và nhìn nó trong hashtable.

Ví dụ: Đối với hình xếp bên dưới

5 3 2     4 6 7       5 7 8 
4 8 9 matches with  5 1 0 for const = 9 & with 6 2 1 for const=10 
1 4 5     8 5 4       9 6 5 

cho ô này 'const' sẽ từ 9 (thêm 0 đến phần tử tối đa) thành 10 (thêm 9 vào phần tử tối thiểu). Vì vậy, tôi sẽ nhận được hai kết hợp có thể cho gạch mà tôi sẽ nhìn lên trong bảng.

Nhưng phương pháp này là tham lam và không đưa ra câu trả lời mong muốn và tôi cũng không thể nghĩ ra một hàm băm phù hợp sẽ xem xét tất cả các phép quay có thể.

Vì vậy, cách tiếp cận tốt để giải quyết vấn đề này là gì?

Tôi chắc chắn có một cách bạo lực để giải quyết vấn đề này nhưng tôi đã thực sự tự hỏi liệu một giải pháp khả thi cho vấn đề tồn tại trên các dòng "theo chiều ngược lại" k ".

Answer 1

Không chắc chắn đây có phải là cách hiệu quả nhất để thực hiện việc này hay không, nhưng nó chắc chắn hoạt động.

gì tôi sẽ làm là:

1. Đi qua tất cả gạch và kiểm tra tối đa và giá trị nhỏ nhất của mỗi ngói và lưu nó trong một mảng khác nhau.
2. Kiểm tra tất cả các cặp có thể.
   1. Nếu min(A) + max(B) == min(B) + max(A) sau đó kiểm tra xem một số vòng quay của B có khớp hoàn toàn trên A hay không. Nếu có, hãy thêm 1 vào số của bạn.
   2. Khác, nó không phù hợp để bạn có thể bỏ qua việc kiểm tra cặp này.

Lưu ý: Lý do tiết kiệm cả tối đa và tối thiểu cho mỗi gạch là nó có thể cứu chúng ta tính toán không cần thiết và quay kiểm tra như trong O(1) chúng ta có thể kiểm tra nếu nó không phù hợp.

Answer 2

Đối với n = 1000, tôi sẽ gắn với giải pháp lực lượng brute (O^2). Tuy nhiên một thuật toán O (n log n) được mô tả dưới đây.

Trật tự lexicographicalish được xác định bởi những điều sau ít hơn điều hành:

Cho hai ma trận M1, M2, xác định M1' như M1 nếu M1[1] là tích cực và -M1 nếu M1[1] là tiêu cực, và tương tự như vậy hoặc M2' . Chúng ta nói rằng M1<M2 nếu M1'[1]<M2'[1], hoặc nếu M1'[1] == M2'[1] và M1'[2] < M2'[2], hoặc nếu M1'[1] == M2'[1] và M1'[2] == M2'[2] và M1'[3] < M2'[3], vv

1. Trừ các yếu tố giữa mỗi ma trận từ phần còn lại của các phần tử của ma trận tức là A'[5] = A[5] và A'[i] = A[i] - A[5]. Sau đó A' phù hợp với B 'nếu A'[i] +B'[i] = 0 cho i!=5 và độ cao là A'[5] + B'[5].

2. Tạo một mảng ma trận và từ điển. Xoay mỗi ma trận sao cho góc trên cùng bên trái có giá trị tuyệt đối tối thiểu trước khi thêm nó vào mảng. Nếu có nhiều góc với cùng giá trị tuyệt đối thì sao chép ma trận và lưu cả hai phép quay trong mảng.

   Nếu một số phép quay của ma trận phù hợp với chính nó và i,j là chỉ số của phép quay của ma trận này, hãy thêm cặp khóa-giá trị (i,j) và (j, i) vào từ điển.

3. Tạo một mảng S của các chỉ mục 1,2 ... và sắp xếp S bằng cách sử dụng thứ tự từ điển.

4. Thay vì cần các phép toán O (n^2) để kiểm tra tất cả các cặp ma trận có thể, chỉ cần kiểm tra tất cả các cặp ma trận có chỉ số là S_i và S_(i+1).. kiểm tra rằng hai ma trận không phải là phép quay của cùng một ma trận gốc trước khi tính toán độ cao của cặp.