ACM/ICPC Indonesia National Contest 2008

Pembahasan Soal Practice Session

Problem A. 1 2 Hop!

Deskripsi Soal A

Soal ini diambil dari Final BNPC-HS 2007 (Bina Nusantara Programming Contest for High School) dan merupakan soal termudah di Practice Session INC 2008. Meskipun termasuk mudah, peserta tetap harus berhati-hati dengan Presentation Error (PE) yang mudah terjadi di sini.

Solusi untuk soal ini cukup straight forward, kita cukup melakukan iterasi dua tingkat dengan disertai beberapa pengecekan kondisi.

Contoh program yang PE adalah sebagai berikut:

Output yang diberikan:

1~2~hop!~1~2~hop!~1~2~hop!~@

Padahal seharusnya:

1~2~hop!~1~2~hop!~1~2~hop!@

~ = space (' ')
@ = endline ('\n')

Solusi C/C++
oleh Suhendry Effendy

#include <stdio.h>

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

  while ( T-- ) {
    int n;
    scanf( "%d", &n );

    if ( n > 9 ) { puts( "what?" ); continue; }

    for ( int i = 1; i <= n; i++ ) {
      for ( int j = 1; j <= n; j++ ) {
        if ( j == n ) printf( "hop!" );
        else printf( "%d", j );
        if ( i == n && j == n ) putchar( '\n' );
        else putchar( ' ' );
      }
    }
  }

  return 0;
}

Solusi JAVA
oleh Felix Halim

import java.util.*;

public class A {
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);

    int nTC = scan.nextInt();
    while (nTC-- > 0){
      int n = scan.nextInt();
      if (n > 9){
        System.out.println("what?");
      } else {
        String hop = "";
        for (int i=1; i<n; i++) hop += i+" ";
        hop += "hop!";

        String res = hop;
        for (int i=1; i<n; i++) res += " " + hop;
        System.out.println(res);
      }
    }
  }
}

Problem B. Square Lookup Easy

Deskripsi Soal B

Cara paling naif untuk menyelesaikan soal ini adalah dengan melakukan bruteforce 4-titik dari semua titik yang ada. Untuk setiap 4-titik yang dipilih kita akan uji apakah 4-titik tersebut membentuk persegi atau tidak. Jika ya, hitung berapa luas yang dibentuk oleh keempat titik tersebut. Dengan cara ini kompleksitas total waktu yang diperlukan adalah O(n^4), cukup kecil meskipun N = 15.

Pendekatan lain yang bisa dilakukan adalah dengan melakukan bruteforce 2-titik, dan untuk setiap 2-titik yang dipilih kita cari dua titik lain (A dan B) yang diperlukan untuk membentuk persegi. Selanjutnya kita uji apakah A dan B yang dibutuhkan ada di antara titik yang menjadi input (metode naifnya memerlukan O(n), tapi bisa ditingkatkan menjadi O(1) dengan hashing/flag). Jika ya, hitung luas yang dibentuk. Cara ini lebih efisien dan hanya membutuhkan kompleksitas O(n^2).

Dua solusi juri berikut sama-sama menggunakan cara O(n^2) namun dengan pendekatan yang berbeda. Solusi yang dibuat Suhendry Effendy melakukan bruteforce pada dua titik untuk membentuk diagonal persegi, sedangkan Felix Halim melakukan bruteforce pada dua titik untuk membentuk sisi persegi.

Solusi C/C++
oleh Suhendry Effendy

#include <stdio.h>

struct point {
  int x; int y;
  bool operator == (struct point &p) {
    return x == p.x && y == p.y;
  }
};

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

  while ( ncase-- ) {
    int n;
    scanf( "%d", &n );

    int ans = 0;
    point p[20];

    for ( int i = 0; i < n; i++ )
      scanf( "%d %d", &p[i].x, &p[i].y );

    for ( int i = 0; i < n; i++ )
      for ( int j = i + 1; j < n; j++ ) {
        int dx = p[i].x - p[j].x;
        int dy = p[i].y - p[j].y;
        if ( (dx+dy) % 2 != 0 ) continue;

        bool found_a = false;
        bool found_b = false;
        point a, b;
        a.x = p[i].x - (dx + dy) / 2;
        a.y = p[i].y - (dy - dx) / 2;
        b.x = p[i].x - (dx - dy) / 2;
        b.y = p[i].y - (dy + dx) / 2;
        for ( int k = 0; k < n; k++ ) {
          if ( p[k] == a ) found_a = true;
          if ( p[k] == b ) found_b = true;
        }

        if ( found_a && found_b ) {
          if ( ans < dx*dx + dy*dy ) ans = dx*dx + dy*dy;
        }
      }

    printf( "%d.00\n", ans / 2 );

  }

  return 0;
}

Solusi JAVA
oleh Felix Halim

import java.util.*;

class Point {
  int x, y;

  public Point(int x, int y){
    this.x = x;
    this.y = y;
  }

  public Point translate(int dx, int dy){
    return new Point(x+dx, y+dy);
  }

  public int hashCode(){
    return x * 13 + y;
  }

  public boolean equals(Object obj){
    Point that = (Point) obj;
    return this.x == that.x && this.y == that.y;
  }
}

public class B {
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);

    int nTC = scan.nextInt();
    while (nTC-- > 0){
      int n = scan.nextInt();

      Set<Point> set = new HashSet<Point>();
      for (int i=0; i<n; i++)
        set.add(new Point(scan.nextInt(), scan.nextInt()));

      int maxArea = 0;
      for (Point a : set)
        for (Point b : set) if (a!=b){
          int vx = b.x - a.x;
          int vy = b.y - a.y;
          Point c = a.translate(-vy,vx);
          Point d = b.translate(-vy,vx);
          if (set.contains(c) && set.contains(d)){
            int area = vx*vx + vy*vy;
            maxArea = Math.max(maxArea, area);
          }
        }
      System.out.printf("%.2f\n",(double)maxArea);
    }
  }
}

Problem C. Math for Birthday Present Again

Deskripsi Soal C

Soal ini diadopsi dari Penyisihan BNPC-HS 2007 dengan memperbesar batasan N dari 10 menjadi 50000 dan membuat pola requestnya fleksibel.

Pertama kita urutkan dulu data yang diinput dengan menggunakan sorting O(n lg n) (bisa dilakukan dengan fungsi built-in yang ada di C/C++ dan Java). Kemudian gunakan dua variable sebagai penentu index kiri dan kanan. Setiap ada request bola kecil kita geser index kiri, sedangkan jika ada request bola besar kita gunakan index kanan. Kedua request tersebut bisa dilakukan dalam O(1), dengan demikian total kompleksitas waktu yang diperlukan adalah O(n lg n).

Jika kita menggunakan cara naif dengan mensimulasikan proses di atas tanpa melakukan sorting terlebih dahulu, maka request bola tidak bisa dilakukan dalam O(1) tapi O(n) karena kita perlu melakukan iterasi ke semua bola dan memeriksa mana bola terbesar/terkecil yang belum diberikan. Akibatnya total kompleksitas waktu yang diperlukan adalah O(n^2), yang tentunya terlalu besar untuk N = 50,000 dan pasti akan menyebabkan Time Limit Exceed (TLE).

Solusi C/C++
oleh Suhendry Effendy

#include <stdio.h>
#include <stdlib.h>

int comp(const void *a, const void *b) {
  return *(int*)a - *(int*)b;
}

int ball[50001];

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

  while ( T-- > 0 ) {
    int n, k, t;
    scanf( "%d %d", &n, &k );
    for ( int i = 0; i < n; i++ )
      scanf( "%d", &ball[i] );

    qsort(ball,n,sizeof(int),comp);

    int L = 0, R = n - 1;
    for ( int i = 0; i < k; i++ ) {
      scanf( "%d", &t );
      if ( i != 0 ) putchar( ' ' );
      if ( t == 0 ) printf( "%d", ball[L++] );
      else printf( "%d", ball[R--] );
    }
    putchar( '\n' );
  }

  return 0;
}

Solusi JAVA
oleh Felix Halim

import java.util.*;

public class C {
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);

    int nTC = scan.nextInt();
    while (nTC-- > 0){
      int n = scan.nextInt();
      int k = scan.nextInt();

      int[] balls = new int[n];
      for (int i=0; i<n; i++)
        balls[i] = scan.nextInt();

      Arrays.sort(balls);

      int lo = 0, hi = balls.length;
      for (int i=0; i<k; i++){
        if (i>0) System.out.print(" ");
        if (scan.nextInt() == 0){
          System.out.print(balls[lo++]);
        } else {
          System.out.print(balls[--hi]);
        }
      }
      System.out.println();
    }
  }
}