Bina Nusantara Programming Contest for High School Students 2008

Problem : A | B | C | D | E | F | G | H

C - Anti Rudal

Data rudal yang diberikan bisa kita representasikan ke dalam koordinat kartesian dengan t-waktu sebagai absis (sumbu-x) dan h-ketinggian sebagai ordinat (sumbu-y). Dengan demikian, yang perlu kita cari adalah berapa jumlah minimal garis yang diperlukan agar semua titik tercover.

Soal ini mirip dengan UVA 497 - Strategic Defense Initiative dengan inti permasalahan yang berbeda, di mana kita diminta untuk mencari berapa jumlah maksimal rudal yang bisa dijatuhkan jika kita hanya memiliki satu peluncur anti-rudal. Permasalahan tersebut adalah salah satu problem klasik Longest Increasing Subsequence (LIS) yang bisa diselesaikan dengan dynamic programming.

Gagasan yang mungkin muncul pertama kali ketika mengerjakan soal ini adalah dengan melakukan LIS berulang-ulang sampai semua titik tercover, namun sayangnya pendekatan ini tidak menghasilkan solusi yang optimal (lihat gambar di bawah).

posisi semua rudal

solusi LIS berulang, output = 3

solusi optimal, output = 2

Untuk menyelesaikan soal ini, urutkan semua titik yang diberikan dari h terkecil ke terbesar. Untuk titik dengan h yang sama, urutkan berdasarkan t terkecil dahulu. Gambar garis pertama dengan mengambil titik pertama yang bisa diambil (sesuai urutan). Ulangi lagi dengan menggambar garis berikut hingga semua titik tercover.

Alternatif lain adalah dengan mengurutkan semua titik dari t terkecil hingga terbesar, namun untuk t yang sama harus diurutkan berdasarkan h terbesar.

Statistik Problem C
YES = 2
NO - Wrong Answer = 18
NO - Time Limit Exceeded = 0
NO - Run-time Error = 3
NO - Compile Error = 1

Solusi C/C++ (oleh Suhendry Effendy)

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 105;

int main()
{

  int T;
  scanf( "%d", &T );

  while ( T-- ) {
    int N;
    int t[maxn];
    int h[maxn];

    scanf( "%d", &N );
    for ( int i = 0; i < N; i++ ) scanf( "%d", &t[i] );
    for ( int i = 0; i < N; i++ ) scanf( "%d", &h[i] );
    
    for ( int i = 0; i < N; i++ )
      for ( int j = i; j < N; j++ )
        if ( h[i] > h[j] || (h[i] == h[j] && t[i] > t[j]) ) {
          swap(t[i], t[j]);
          swap(h[i], h[j]);
        }
    
    int  ans = 0;
    bool clear = false;
    bool shot[maxn] = {false};

    while ( !clear ) {
      clear = true;
      int last = -1;
      for ( int i = 0; i < N; i++ ) {
        if ( !shot[i] && t[i] > last ) {
          clear = false;
          shot[i] = true;
          last = t[i];
        }
      }
      if ( !clear ) ans++;
    }
    
    printf( "%d\n", ans );
  }

  return 0;
}

Solusi Pascal (oleh Eko Wibowo)

var
  i, j, n, tcase, last, ans :longint;
  h,t   : array[1..100] of longint;
  clear : boolean;
  shot  : array[1..100] of boolean;
procedure swap(var a, b : longint);
var c : longint;
begin
  c := a;
  a := b;
  b := c;
end;

begin
  read(tcase);
  while (tcase > 0) do
  begin
    tcase := tcase - 1;
    read(n);
    for i := 1 to n do read(t[i]);
    for i := 1 to n do read(h[i]);
    for i := 1 to n-1 do
      for j := i+1 to n do
        if ((h[i] > h[j]) or ((h[i] = h[j]) and (t[i] > t[j]))) then
        begin
          swap(h[i],h[j]);
          swap(t[i],t[j]);
        end;
    ans:=0;
    for i := 1 to n do shot[i] := false;
    clear := false;
    while not clear do
    begin
      clear := true;
      last  := -1;
      for i:=1 to n do
        if (not shot[i] and (t[i] > last)) then
        begin
          clear :=false;
          shot[i] :=true;
          last :=t[i];
        end;
      if not clear then ans := ans + 1;
    end;
    writeln(ans);
  end;
end.