May 102018
 

A. Nice Bro Aron

link soal

Diberikan N (1 ≤ N ≤ 1000) bilangan bulat Ci (1 ≤ Ci ≤ 100), output jumlah dari semua bilangan tersebut dikurangi dengan bilangan terkecil.

Ini adalah soal termudah di babak penyisihan dan berhasil diselesaikan oleh 121 tim. Yang Anda perlu lakukan hanya menjumlahkan semua bilangan yang diberikan dan menguranginya dengan nilai paling kecil (persis dengan deskripsi singkat di atas).

int N, C;
int total = 0;
int least = 1000000;
scanf( "%d", &N );
for ( int i = 0; i < N; i++ ) {
  scanf( "%d", &C );
  total += C;
  least = min(least,C);
}
printf( "%d\n", total - least );

Beberapa tim yang tidak berhasil menyelesaikan soal ini terkendala dengan kesalahan umum yang sering dijumpai pada pemula, di antaranya:

  • Mencetak “Masukkan Input:” atau sejenisnya. Apapun yang dicetak oleh program Anda adalah bagian dari output. Karena soal di atas tidak meminta Anda mengeluarkan output yang demikian, maka solusi seperti ini akan mendapat WRONG-ANSWER.
  • Membaca input dari file. Input pada semua soal dibaca melalui standard input, bukan dari file; selain itu, tidak ada nama file yang diberikan di soal.
  • Penggunaan “package” pada Java. Ini akan menyebabkan program Anda tidak bisa dijalankan (Run-Error).

B. Complicated Robot

link soal

Diberikan sebuah string S (Si ∈ {‘N’, ‘S’, ‘E’, ‘W’}; |S| ≤ 1,000) yang merepresentasikan gerakan sebuah robot yang bermula dari koordinat (0, 0), tentukan panjang string terpendek yang juga bisa mencapai posisi akhir seperti yang ditunjukkan oleh string S.

Ini adalah soal termudah kedua pada babak penyisihan dan berhasil diselesaikan oleh 108 tim.

Amati bahwa setiap koordinat (x, y) dapat dicapai dari (0, 0) hanya dengan |x| + |y| langkah. Contoh: koordinat (-3, 2) dapat dicapai dengan “WWWNN” (atau semua kombinasi string lain dengan 3W dan 2N) yang memiliki panjang |-3| + 2 = 5. Dengan demikian, kita hanya perlu mengetahui posisi akhir robot yang mendapat perintah string S.

char S[1005];
scanf( "%s", S );
int len = strlen(S);
int x = 0, y = 0;
for ( int i = 0; i < len; i++ ) {
	if ( S[i] == 'N' ) y++;
	if ( S[i] == 'S' ) y--;
	if ( S[i] == 'E' ) x++;
	if ( S[i] == 'W' ) x--;
}
printf( "%d\n", abs(x) + abs(y) );

C. Raon and Candy

link soal

Baca soal pada link di atas.

Soal ini adalah salah satu dari dua soal tersulit di babak penyisihan.

Perhatikan bahwa pemain tidak bisa bergerak ke lantai yang lebih rendah dari posisinya; Ia hanya bisa mondar-mandir di lantai tersebut (mengumpulkan permen), atau naik ke lantai di atasnya (melalui tangga yang tersedia). Karena sub-masalahnya memiliki sifat acyclic (hanya bisa naik ke lantai di atasnya, tidak bisa turun), situasi seperti ini bisa diselesaikan dengan pendekatan dynamic programming (DP).

State DP yang kita perlukan harus memiliki informasi berikut:

  • row: Lantai di mana pemain berada – max N = 100,
  • pos: Posisi pemain (di tangga kiri atau kanan) – max 2,
  • candy: Jumlah permen yang masih harus dikumpulkan – max C = 1,000.

Pada setiap state dp[row][pos][candy], kita memiliki sebanyak (M + 1) * 2 pilihan, yaitu: mengumpulkan permen dari m ruangan terdekat dari posisinya (m = [0, M]), kemudian naik ke lantai berikutnya melalui tangga di kiri atau kanan. Total state yang kita perlukan maksimal N * 2 * C = O(NC), sedangkan total iterasi untuk setiap state maksimal (M + 1 ) * 2 = O(M); dengan demikian total kompleksitas solusi ini adalah O(NMC).

int dp[MAXN][2][MAXC];
int f(int row, Pos pos, int candy) {
  if ( row == -1 ) return candy == 0 ? -1 : inf;
  candy = max(candy,0);
  if ( dp[row][pos][candy] != -1 ) return dp[row][pos][candy];
  int &ret = dp[row][pos][candy] = f(row-1,pos,candy) + 1;
  int p_start = pos == LEFT ? 1 : M;
  int p_end   = pos == LEFT ? M + 1 : 0;
  int p_move  = pos == LEFT ? 1 : -1;
  int move    = 0;
  for ( int j = p_start; j != p_end ; j += p_move ) {
    move++;
    candy -= arr[row][j] - '0';
    ret = min(ret,f(row-1,LEFT,candy)+move+j+1);       // ke tangga kiri : +j
    ret = min(ret,f(row-1,RIGHT,candy)+move+M+1-j+1);  // ke tangga kanan: +M+1-j
  }
  return ret;
}

Ada beberapa detail yang tidak terlihat pada potongan kode di atas, tapi yang membaca diharapkan bisa menebak sendiri. Pos adalah tipe enum { LEFT, RIGHT }; array dp[] diinisialisasi dengan -1 untuk menandakan bahwa state tersebut belum dievaluasi; inf adalah konstanta dengan nilai yang lebih besar dari output terbesar; fungsi di atas dipanggil dengan f(N-1,LEFT,C), di mulai dari lantai terbawah N-1 sisi kiri.

Base case dari formula DP di atas ada pada baris-4, ketika kita mencapai lantai -1. Ini adalah trik yang saya gunakan agar kita tidak perlu menangani lantai teratas (lantai 0) secara terpisah, yaitu dengan menambahkan lantai bohongan (lantai -1).

D. AoTa Tournament

link soal

Diberikan hasil pertandingan satu lawan satu dari tepat 8 tim (ada 28 pertandingan), tentukan peringkat dari semua tim. Hasil dari setiap pertandingan adalah 2-0, 2-1, 1-2, atau 0-2.

Tantangan pada soal ini ada dua, yaitu: parsing input dan sorting. Tidak banyak yang bisa saya bahas di sini. Anda hanya perlu membaca format input dengan benar dan kemudian mengurutkan nama tim nya sesuai dengan kriteria yang diberikan soal.

Pada saat babak penyisihan berlangsung, ada tim yang menanyakan kriteria pengurutan nama tim dengan total menang yang sama. Di soal hanya disebutkan tim demikian akan diurutkan secara leksikografis (urutan kamus), namun bagaimana aturan urutan antara “A-Z”, “a-z”, dan ‘_’? Aturan urutan yang digunakan oleh juri di soal ini mengikuti kode ASCII dari setiap karakter, yang artinya “A-Z” (65..90) < '_' (95) < "a-z" (97..122). Dengan aturan ini maka Anda hanya perlu melakukan komparasi string seperti biasa.

E. Inaccurate Report

link soal

Baca soal pada link di atas.

Lakukan BFS atau DFS dari setiap node xj sejauh dj. Hitung berapa kali setiap node pada tree tersebut dikunjungi oleh laporan yang ada.

Dengan node pada tree sebanyak N (1 ≤ N ≤ 10,000), operasi BFS/DFS untuk setiap laporan memiliki kompleksitas O(N). Dengan demikian, operasi BFS/DFS untuk semua M laporan (1 ≤ M ≤ 100) memiliki kompleksitas O(NM).

F. Thumb Up Thumb Down Cute Cat

link soal

Diberikan dua buah bilangan bulat N dan S (1 ≤ N ≤ 109; -109 ≤ S ≤ 109), tentukan apakah ada bilangan bulat A dan B sedemikian sehingga A – B = S dan A + B = N.

Ini adalah soal termudah ketiga pada babak penyisihan dan berhasil diselesaikan oleh 76 tim.

Karena batasan N yang cukup besar (maksimal 109) dan time-limit hanya 1 detik, solusi yang mencari nilai A dan B secara brute force (iterasi A dari 1 hingga N) bisa dipastikan akan mendapatkan TIMELIMIT.

Soal ini memiliki solusi O(1). Kita hanya perlu memeriksa apakah …

  1. N – S adalah bilangan genap,
  2. S ada di antara -N hingga N.

Perhatikan bahwa N – S = (A + B) – (A – B) = 2 * B adalah bilangan genap (dua kali nilai B), dan S tidak bisa lebih kecil dari -N atau lebih besar dari N. Jika kedua syarat di atas terpenuhi, maka outputnya adalah YES, jika tidak, NO.

G. Necklaces

link soal

Baca soal pada link di atas.

Salah satu tester soal ini ada yang berpendapat “soal ini nggak susah, tapi format outputnya nyebelin”. Umumnya soal-soal seperti ini hanya meminta output yang dimodulo dengan sebuah bilangan (umumnya 1,000,000,007), namun soal ini meminta output pada most-significant-digits nya.

Pertama, perhatikan bahwa input warna untuk C (baris kedua input) tidaklah berguna. Yang kita perlukan hanya nilai C nya saja.

Soal ini bisa diselesaikan menggunakan dynamic programming (DP) dengan state [n][c] – panjang untaian kalung yang tersisa dan nomor warna yang terakhir yang digunakan. Di setiap state, kita tinggal menghitung total kombinasi jika kita memasang K-1, K, dan K beads (nggak tahu apa Bahasa Indonesianya “beads”, manik-manik?). Masalah berikutnya adalah: tipe data apa yang harus kita gunakan?

Di kasus ini, kita harus menggunakan tipe data double (atau dengan BigInteger/BigDecimal). Beberapa tim menggunakan tipe data long long dan tentunya mendapatkan WRONG-ANSWER. Nilai output untuk soal ini bisa mencapai 10264 dan ini tentunya jauh melebihi batas long long (263 – 1, atau ~1018). Kita tidak perlu mengkhawatirkan presisi perhitungan tipe data double di sini karena yang kita butuhkan hanya 4 most significant digits dan banyak kombinasi di setiap sub-state (K-1, K, K+1) seharusnya tidak berbeda jauh secara signifikan.

double dp[maxn][maxc];
bool memo[maxn][maxc] = {false};
double f(int n, int c) {
  if ( c == 0 ) c = C;
  if ( n == 0 ) return c == C;
  if ( memo[n] ) return dp[n];
  double &ret = dp[n] = 0;
  memo[n] = true;
  for ( int k = K-1; k <= K+1; k++ )
    if ( k >= 1 && n - k >= 0 ) ret += f(n-k,c-1);
  return ret;
}

Banyak state yang diperlukan adalah N * C = O(NC), dan untuk mengevaluasi satu state diperlukan iterasi maksimum 3 (untuk menguji K-1, K, dan K+1) = O(1); dengan kata lain, kompleksitas solusi di atas adalah O(NC). Dengan N ≤ 1,000 dan C ≤ 10, solusi demikian tentunya lebih dari cukup. Anda bisa menggunakan struktur data seperti BigInteger/BigDecimal atau menggunakan Python jika Anda tidak yakin dengan tipe data double. Cost tambahan karena penggunaan tipe data tersebut masih tidak akan membuat solusi demikian mendapatkan TIMELIMIT.

Kemudian, bagaimana agar format outputnya bisa sesuai permintaan soal? Ada banyak cara. Berikut adalah salah satu contoh cara yang saya gunakan (dengan C/C++):

char out[100];
int  exponent;
sprintf( out, "%.3e", f(N,C) );
sscanf( out+6, "%d", &exponent ); out[5] = 0;
printf( "%s x 10^%d\n", out, exponent );

Pada saat babak penyisihan berlangsung, ada tim yang mengajukan klarifikasi mengenai format output soal ini. Awalnya, rentang untuk output A yang dicantumkan pada soal adalah [1, 9], namun apa yang terjadi jika outputnya adalah 0? Sebagai akibatnya, ketentuan untuk format output pun segera diperbaiki menjadi “where A ∈ {0-9}; B,C,D ∈ {0-9}; E ≥ 0; A,B,C,D,E are integers. If A = 0, then B = C = D = E = 0. Dengan demikian, jika outputnya adalah 0, yang harus dicetak adalah 0.000 x 10^0.

H. L-IVE: Length Archiver

link soal

Lakukan kompresi run-length encoding (RLE) pada data dengan N buah bilangan bulat Ai (1 ≤ N ≤ 100,000; 0 ≤ Ai ≤ 255). Setiap bilangan bulat pada hasil kompresi harus berada pada rentang [0, 255].

Soal ini cukup straight forward. Anda hanya perlu melakukan prosedur yang diminta.

int N = 0;    // input size
int M = 0;    // output size
int A[maxn];  // input array
int B[maxm];  // output array

while ( scanf( "%d", &A[N] ) != EOF ) N++;
for ( int i = 0; i < N; i++ ) {
  int cnt = 1;
  while ( i + 1 < N && cnt < 255 && A[i+1] == A[i] ) i++, cnt++;
  B[M++] = cnt;
  B[M++] = A[i];
}

Di soal tidak disebutkan istilah RLE, namun prosedur kompresi yang dijelaskan serupa dengan teknik kompresi sederhana RLE. Bagi Anda yang ingin mengetahui lebih jauh mengenai teknik kompresi ini, silakan baca halaman Wikipedia berikut.


 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)