ACM/ICPC Indonesia National Contest 2007 - Qualification
Problem A
The Chosen Sub Matrix
Time Limit: 1sFrom 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:
|
Then, the possible sub matrixes of 3x3 are:
|
|
|
|
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
Pembahasan Problem A - The Chosen Sub Matrix
Anda diberikan matrix N x N berisikan angka dari 0 sampai 9. Anda harus "memilih" sub-matrix M x M yang mempunyai elemen berbeda terkecil. Jika ada sub-matrix yang mempunyai elemen berbeda terkecil yang sama, maka anda harus memilih yang mempunyai elemen terbesar yang tidak sama. Jika masih seri juga, maka pilih yang row nya terkecil, lalu column terkecil.
Algorithm untuk problem ini juga straight forward: cari satu-per-satu diantara semua sub-matrix M x M, update hasil kalau ketemu yang lebih bagus. Anda bisa lihat implementasi algoritma ini dibawah (dalam C maupun Java).
#include <stdio.h>
typedef struct {
int row, col; // posisi (row,col) dari Square M x M
int nums[10]; // num[i] == 1 kalau ada angka i di Square ini,
// kalau tidak maka num[i] == 0
// dimana i adalah angka antara 0..9
} Square;
// menghitung kemunculan angka i dalam array nums
int count_distinct(int nums[10]){
int i=0,ret=0;
for (i=0; i<10; i++)
if (nums[i]) ret++;
return ret;
}
// membandingkan dua Square sesuai yang diminta soal
// return true kalau sa lebih bagus dari pada sb
int better(Square *sa, Square *sb){
int distinct_a = count_distinct(sa->nums);
int distinct_b = count_distinct(sb->nums);
int i;
// pertama tama, bandingkan jumlah angka yang berbeda
if (distinct_a != distinct_b)
return distinct_a < distinct_b;
// kedua, bandingkan kemunculan element tertinggi
for (i=9; i>=0; i--)
if (sa->nums[i] != sb->nums[i])
return sb->nums[i] < sa->nums[i];
// ketiga, bandingkan baris
if (sa->row != sb->row) return sa->row < sb->row;
// perbandingan terakhir adalah kolom
return sa->col < sb->col;
};
int N,M,arr[10][10];
Square get_square(int r, int c){
Square square;
int i,j;
square.row = r;
square.col = c;
for (i=0; i<10; i++)
square.nums[i] = 0;
for (i=0; i<M; i++)
for (j=0; j<M; j++)
square.nums[arr[r+i][c+j]] = 1;
return square;
}
int main(){
int i,j;
while (scanf("%d %d",&N,&M)!=EOF){
for (i=0; i<N; i++)
for (j=0; j<N; j++)
scanf("%d",&arr[i][j]);
Square chosen = get_square(0,0);
for (i=0; i+M<=N; i++)
for (j=0; j+M<=N; j++){
Square current = get_square(i,j);
if (better(¤t, &chosen))
chosen = current;
}
// print square yang terpilih
printf("%d %d\n",chosen.row+1, chosen.col+1);
}
}
import java.io.*;
import java.util.*;
public class Matrix {
int[][] arr = new int[10][10];
int N, M;
class Square implements Comparable<Square> {
int row, col; // posisi (row,col) dari Square M x M
int[] nums; // nums[i] == 1 kalau ada angka i di Square ini,
// kalau tidak maka nums[i] == 0
// dimana i adalah angka antara 0..9
// meng-inisialisai data untuk Square pada posisi[r][c]
public Square(int r, int c){
row = r;
col = c;
nums = new int[10]; // ter-inisialisasi sendiri dengan 0
// mengisi nums[i] dengan 1 jika ada angka i di Square ini,
// kalau tidak ada maka nums[i] = 0
for (int i=0; i<M; i++)
for (int j=0; j<M; j++)
nums[arr[r+i][c+j]] = 1;
}
// menghitung kemunculan angka i dalam array nums
int distinctCount(){
int ret = 0;
for (int i=0; i<10; i++)
if (nums[i]==1) ret++;
return ret;
}
// membandingkan dua Square sesuai yang diminta soal
public int compareTo(Square that){
int thisDistinct = this.distinctCount();
int thatDistinct = that.distinctCount();
// pertama tama, bandingkan jumlah angka yang berbeda
if (thisDistinct != thatDistinct)
return thisDistinct - thatDistinct;
// kedua, bandingkan kemunculan tertinggi
for (int i=9; i>=0; i--)
if (this.nums[i] != that.nums[i])
return that.nums[i] - this.nums[i];
// ketiga, bandingkan baris
if (this.row != that.row) return this.row - that.row;
// perbandingan terakhir adalah kolom
return this.col - that.col;
}
}
public void solve(){
Scanner scan = new Scanner(System.in);
// baca input selama masih ada integer berikutnya
while (scan.hasNextInt()){
N = scan.nextInt(); // baca N
M = scan.nextInt(); // baca M
// membaca matrix N x N ke variable arr
for (int i=0; i<N; i++)
for (int j=0; j<N; j++)
arr[i][j] = scan.nextInt();
Square chosen = new Square(0,0);
for (int i=0; i+M<=N; i++)
for (int j=0; j+M<=N; j++){
Square current = new Square(i,j);
if (current.compareTo(chosen) < 0)
chosen = current;
}
// output square yang terpilih
System.out.printf("%d %d\n",chosen.row+1, chosen.col+1);
}
scan.close();
}
public static void main(String[] args){
new Matrix().solve();
}
}
No comments:
Post a Comment