Suhendry’s Blog

Problem B. Converting Numbers

Deskripsi Soal B
Problem Author: Bong Win Ce

Diberikan sejumlah nilai pada range 0 - 100, anda diminta untuk melakukan konversi data tersebut ke dalam range 400 - 600 sesuai ketentuan yang diberikan. Soal ini seharusnya tidak susah karena prinsip penyelesaiannya sama dengan konversi Celcius - Fahrenheit.

Melalui rumus yang diberikan kita bisa mendapatkan batas kiri (L) dan batas kanan (R) dari data input. Yang perlu kita lakukan berikutnya adalah mengkonversi data input dari skala L - R ke dalam skala 400 - 600 dengan cara: X_i‘ = 400 + 200 * (X_i - L) / (R - L).

Pada babak penyisihan tidak banyak tim yang berhasil menyelesaikan soal ini dengan sempurna (11 tim). Dari 11 tim tersebut hanya K.E.F.S dari ITB dan RTC dari UI yang berhasil mendapatkan Accepted dalam 1 submission. Berikut ini adalah kesalahan-kesalahan yang sangat banyak dijumpai pada solusi peserta:

• N = 1
  Nilai N yang perlu ditangani peserta adalah 1 - 1000. Apa yang terjadi dengan rumus perhitungan standard deviasi (SD) ketika N = 1? Jika program peserta tidak menangani kondisi ini, maka program tersebut akan memproses pembagian dengan nol pada floating point number (menjadi NaN/Not-a-Number) dan akibatnya mendapat Wrong Answer.

  Program yang dibuat peserta perlu menangani kondisi N = 1 dengan tidak menghitung SD nya, dan langsung mencetak 500.00 sebagai output (karena satu nilai tersebut pasti AVG dari data yang diberikan).
  

  Test case ke-3 pada test data milik juri menangkap program yang gagal pada N = 1:

  1 1-sAja
  40

• SD = 0
  Standard Deviasi (SD) bernilai nol jika nilai yang diberikan semuanya sama, akibatnya (R - L) pada perhitungan konversi di atas nilainya juga akan nol karena R = L = AVG. Dampak dari perhitungan ini sama seperti pada N = 1 (pembagian dengan nol) yang akan mengakibatkan Wrong Answer

  Test case ke-4 pada test data milik juri menangkap program yang gagal pada SD = 0:

  2 2-sama
  90
  90

• Pembulatan untuk hasil yang di luar rentang 400 - 600
  Pembulatan ini harus dilakukan karena diminta oleh soal: “If the result is not between 400 and 600, round it to nearest end (either 400 or 600)”.

  Test case ke-10 dan 11 pada test data milik juri menangkap program yang gagal pada pembulatan nilai di luar rentang:

  21 OVER-LOW 100 100 100 100 100 100 100 100 100 100 100 0 1 97 100 100 100 100 100 100 100

  21 OVER-HI 100 99 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Selain tiga poin utama di atas, rata-rata kesalahan lain disebabkan karena bug kecil pada program yang dibuat. Juri sempat memperhatikan ada jawaban beberapa peserta yang mendapatkan Time Limit Exceed (program tidak berhenti) karena kesalahan alokasi memori, bukan karena programnya yang tidak efisien. Untuk lebih jelasnya silahkan baca artikel dari Shahriar Manzoor (ACM-ICPC World Final Judge) mengenai Common Mistakes in Online and Real-time Contests pada topik “Time limit exceeded” is not always “Time limit exceeded”.

Solusi C/C++
oleh Suhendry Effendy show

#include <stdio.h>
#include <math.h>

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

  while ( T-- > 0 ) {
    int N;
    char S[21];
    scanf( "%d %s", &N, S );

    puts( S );

    double score[1001], sum = 0;
    for ( int i = 0; i < N; i++ ) {
      scanf( "%lf", &score[i] );
      sum += score[i];
    }

    if ( N == 1 ) {
      puts( "500.00" );
      continue;
    }

    double avg = sum / N;

    double stdev = 0;
    for ( int i = 0; i < N; i++ )
      stdev += pow(score[i] - avg, 2);
    stdev = sqrt(stdev / (N - 1));

    double left = avg - stdev * 3;
    double right = avg + stdev * 3;
    double range = right - left;

    for ( int i = 0; i < N; i++ ) {
      double ans;
      if ( range == 0 ) ans = 500.0;
      else ans = 400.0 + 200.0 * (score[i] - left) / range;
      if ( ans > 600.0 ) ans = 600.0;
      if ( ans < 400.0 ) ans = 400.0;
      printf( "%.2lf\n", ans );
    }
  }

  return 0;
}

Solusi JAVA
oleh Felix Halim show

import java.util.*;

public class numbers {
  void solve(){
    Scanner scan = new Scanner(System.in);

    int nTC = scan.nextInt();
    while (nTC-- > 0){
      int n = scan.nextInt();
      System.out.println(scan.next());
      double[] x = new double[n];
      for (int i=0; i<n; i++)
        x[i] = scan.nextDouble();

      double avg = 0;
      for (int i=0; i<n; i++) avg += x[i];
      avg /= n;

      double sd = 0;
      for (int i=0; i<n; i++) sd += (x[i]-avg)*(x[i]-avg);
      if (n>1) sd = Math.sqrt(sd / (n-1));

      double lo = avg - 3*sd, hi = avg + 3*sd;
      for (int i=0; i<n; i++){
        if (sd==0) System.out.println("500.00");
        else {
          double res = (x[i]<lo)? lo : (x[i]>hi)? hi : x[i];
          System.out.printf("%.2f\n",400.0 + ((res-lo)/(hi-lo)) * 200.0);
        }
      }
    }
  }

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

Pages: 1 2 3 4 5 6 7