ACM/ICPC Indonesia National Contest 2008

Problem D. Eat or Be Eaten

Problem Author: Suhendry Effendy

Diberikan dua buah set bilangan A dan B, anda diminta untuk menentukan berapa banyak pasangan A - B sedemikian sehingga A > B. Ini adalah soal yang paling banyak diselesaikan oleh finalis INC 2008 (total 41 tim Accepted).

Solusi naif soal ini adalah bruteforce O(N²) yang kemungkinan besar akan mendapatkan Time Limit Exceed. Solusi yang lebih baik (Accepted) bisa didapatkan dengan O(N lg N). Pertama, urutkan terlebih dahulu data pada masing-masing set, kemudian hitung berapa banyak pasangan A - B dimana A > B dengan O(N).

      i
A:    1   2   3   7   8
B: -  1   3   6
   j stop: +0

          i
A:    1   2   3   7   8
B: - [1]  3   6
      j stop: +1

              i
A:    1   2   3   7   8
B: - [1]  3   6
      j stop: +1

                  i
A:    1   2   3   7   8
B: - [1   3]   6
          j

                  i
A:    1   2   3   7   8
B: - [1   3   6]
              j stop: +3

                      i
A:    1   2   3   7   8
B: - [1   3   6]
              j stop: +3

Untuk setiap posisi i, cari posisi j dimana A[i] > B[j] dan A[i] <= B[j+1] (posisi pada B dimana B[j] adalah angka terbesar yang masih lebih kecil dari A[i]). Untuk mencari posisi j untuk i + 1, posisi j tidak perlu diulang lagi dari 0, cukup dilanjutkan dari posisi j terakhir. Dengan demikian i dan j masing-masing akan diiterasi sebanyak jumlah data.

Solusi C/C++
oleh Suhendry Effendy

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

int a[20005];
int b[20005];

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

  while ( T-- ) {
    int n, m;
    scanf( "%d %d", &n, &m );
    for ( int i = 0; i < n; i++ ) scanf( "%d", &a[i] );
    for ( int j = 0; j < m; j++ ) scanf( "%d", &b[j] );

    sort(a, a + n);
    sort(b, b + m);

    int ans = 0;

    int j = -1;
    for ( int i = 0; i < n; i++ ) {
      while ( j + 1 < m && b[j + 1] < a[i] ) j++;
      ans += j + 1;
    }

    printf( "%d\n", ans );
  }
  
  return 0;
}

Solusi JAVA
oleh Suhendry Effendy

import java.util.*;

public class Eat {
  void solve() {
    Scanner scan = new Scanner(System.in);
    
    int T = scan.nextInt();
    while ( T-- > 0 ) {
      int n = scan.nextInt();
      int m = scan.nextInt();
      int[] a = new int[n];
      int[] b = new int[m];
      for ( int i = 0; i < n; i++ ) a[i] = scan.nextInt();
      for ( int j = 0; j < m; j++ ) b[j] = scan.nextInt();

      Arrays.sort(a);
      Arrays.sort(b);
      
      int ans = 0;

      int j = -1;
      for ( int i = 0; i < n; i++ ) {
        while ( j + 1 < m && b[j + 1] < a[i] ) j++;
        ans += j + 1;
      }

      System.out.println(ans);
    }
  }

  public static void main(String[] args) {
    new Eat().solve();
  }
}