Felix Halim .NET |  |

| Enter your search terms Submit search form

Story | Research | Programming | Scripts | Member | Miscellaneous

### ACM/ICPC Indonesia National Contest 2007 - Qualification

## Problem A

# The Chosen Sub Matrix

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 S1 has 2 distinct elements: 9 and 3;
Sub matrix S2 has 2 distinct elements: 9 and 2;
Sub matrix S3 has 4 distinct elements: 9, 5, 3, and 2;
Sub matrix S4 has 3 distinct elements: 9, 5, and 2.
Sub matrixes are ranked using the rules above and give result as S1, S2, S4, and then S3.
Which means the chosen sub matrix is S1.

## 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

Problem Setter: Bong Win Ce

Kembali ke pembahasan soal ini

Lihat problem lain:

1. The Chosen Sub Matrix
2. Avoiding Financial Nightmare
3. No Pause Telegraph
4. Burger, French Fries, Soft Drink
5. Taxi!

`© Felix Halim 2009 (Loaded in 0.00479 secs)`

    Timeline:
    start_time (diff_time_with_previous) tree_structure
    0.00000 (0.00000) Total
    0.00003 (0.00003) -Logging Request
    0.00005 (0.00003) --Creating fhnet PDO...
    0.00350 (0.00345) --fhnet PDO created
    0.00352 (0.00002) --Statement created
    0.00427 (0.00075) --Statement executed

    Summary:
    start_time (duration) section_name
    0.00000 (0.00482) : Total
    0.00003 (0.00427) : Logging Request