ACM/ICPC Indonesia National Contest 2007 - Qualification

Problem A

The Chosen Sub Matrix

GCC/Visual C++: matrix.cpp Java: matrix.java
Time Limit: 1s

From a given N x N matrix, you should find an M x M sub matrix which has the least distinct element in it. If there are more than one sub matrixes which have the same number of distinct elements then compare each element in descending order and choose one that has the first highest element. If all of distinct elements of all sub matrixes are the same, chose one with the least row index, and then the least column index. The matrix index starts at 1.

For example, given a 4x4 matrix:

3 9 9 9 3 9 9 2 3 9 9 2 2 5 5 2

Then, the possible sub matrixes of 3x3 are:

3 9 9 3 9 9 3 9 9 S1

9 9 9 9 9 2 9 9 2 S2

3 9 9 3 9 9 2 5 5 S3

9 9 2 9 9 2 5 5 2 S4

Sub matrix S₁ has 2 distinct elements: 9 and 3;
Sub matrix S₂ has 2 distinct elements: 9 and 2;
Sub matrix S₃ has 4 distinct elements: 9, 5, 3, and 2;
Sub matrix S₄ has 3 distinct elements: 9, 5, and 2.
Sub matrixes are ranked using the rules above and give result as S₁, S₂, S₄, and then S₃.
Which means the chosen sub matrix is S₁.

Input Specification

The first line of each case contains two integers, N (1<=N<=10) the size of matrix, and M (1<=M<=N) the size of sub matrix to be chosen. In the next N lines, each contains N integers (each separated by a space) that represent the matrix. Each element in the matrix should be between 0 and 9 inclusively.

Output Specification

For each case you should output in a single line, the top-left index (row and column, separated by a single space) of the chosen sub matrix.

Sample Input

4 3
3 9 9 9
3 9 9 2
3 9 9 2
2 5 5 2
10 2
1 5 7 8 2 3 3 3 1 7
2 2 3 6 3 7 3 2 3 1
5 9 3 5 7 0 4 6 9 1
1 0 3 4 2 6 4 3 9 0
7 4 9 9 5 4 6 2 1 5
5 6 9 9 6 6 3 8 0 8
4 3 3 5 2 1 7 6 4 1
6 5 9 5 0 3 1 8 8 6
2 2 2 8 0 1 3 5 9 0
3 6 4 2 3 3 0 2 0 0

Sample Output

1 1
5 3

Untuk jawaban click disini