Felix Halim .NET  
Google 
Name:  Message:

Problem A - The Chosen Sub Matrix

Complete Problem Statement here

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();
    }
}

Lihat problem lain:

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

© Felix Halim 2009 (Loaded in 0.00167 secs)