Embedded Files
oleh Untitled Training Camp
Written by:
Jiriki Joeng (kizu)
Reviewed by:
Christoffer Edbert Karuniawan (Chrisedyong)
Leonardo Dahendra (Drakozs)
*warna berdasarkan max rating Codeforces per Jul 2025
Akses soalnya di: https://osn.toki.id/data/OSNP2024.pdf
Studi Kasus A. String Cantik OSN
Studi Kasus A. String Cantik OSN
A1. E
A1. E
A1. E. "NOSNOSO"
Kita ingat definisi string cantik OSN:
Panjang ≥ 3.
Setiap 3 huruf berurutan tepat mengandung satu ‘O’, satu ‘S’, dan satu ‘N’.
Perhatikan tiap pilihan:
Periksa setiap window 3-huruf.
A. "NSO"
"NSO" - > {N,S,O}
Valid
B. “SNOS”
“SNO” → {S,N,O}
“NOS” → {N,O,S}
Valid
C. “SONSO”
“SON” → {S,O,N}
“ONS” → {O,N,S}
“NSO” → {N,S,O}
Valid
D. “ONSONS”
“ONS” → {O,N,S}
“NSO” → {N,S,O}
“SON” → {S,O,N}
“ONS” → {O,N,S}
Valid
E. “NOSNOSO”
“NOS” → {N,O,S}
“OSN” → {O,S,N}
“SNO” → {S,N,O}
“NOS” → {N,O,S}
“OSO” → {O,S,O} (Tidak cantik, karena terdiri atas huruf yang double)
Tidak Valid
A2. 6
A2. 6
String cantik OSN sepenuhnya ditentukan oleh 3 huruf pertamanya, karena pola selanjutnya harus mengikuti aturan agar tiap 3 huruf tetap terdiri dari tepat 1 ‘O’, 1 ‘S’, dan 1 ‘N’.
Banyak cara memilih 3 huruf pertama = jumlah permutasi ‘O’, ‘S’, ‘N’ = 3! = 6.
Jadi, ada 6 string berbeda dengan panjang 100 huruf yang merupakan string cantik OSN.
A3. SALAH
A3. SALAH
Cari subsequence O - S - N - O - S - N di dalam string yang diberikan "CONTOHSTRINGUNTUKSOALBENARATAUSALAH"
O di posisi {2, 5, 19}
S di posisi {7, 18, 31}
N di posisi {3, 11, 14, 24}
Dari semua kombinasi, tidak ada satu kombinasi pun yang dapat membentuk O - S - N - O - S - N, maka itu string yang diberikan tidak memenuhi (SALAH)
Soal Pemrograman
Soal Pemrograman
Setiap string cantik OSN dapat dibentuk dengan mengambil subsequence yang merupakan pengulangan dari permutasi "OSN".
Oleh karena itu, kita harus mencoba untuk semua permutasi "OSN" -> {OSN, ONS, SON, SNO, NOS, NSO}. (Dapat menggunakan do-while next permutation).
Proses setiap permutasi "OSN" untuk mencari panjang subsequence maksimumnya, bisa menggunakan two pointer, 1 di index (modulo 3) string permutasi, dan 1 di string S.
Kasus 1: Panjang maksimum < 3
Keluarkan -1 (Panjang minimal 3)
Kasus 2: Panjang maksimum >= 3
Keluarkan panjang maksimum
Kompleksitas waktu: O (6*|S|)
Subsoal 1:
Kita dapat simulasikan untuk mencari subsequence terpanjangnya dengan mencoba semua permutasi "OSN".
Permutasi 'OSN' = OLIMPIADESAINSNATIONALTINGKATPROVINSI -> OSNOS = 5
Permutasi 'NOS' = OLIMPIADESAINSNATIONALTINGKATPROVINSI -> NOS = 3
Permutasi 'ONS' = OLIMPIADESAINSNATIONALTINGKATPROVINSI -> ONSONS = 6
Permutasi 'SON' = OLIMPIADESAINSNATIONALTINGKATPROVINSI -> SONS = 4
Permutasi 'SNO' = OLIMPIADESAINSNATIONALTINGKATPROVINSI -> SNOS = 4
Permutasi 'NSO' = OLIMPIADESAINSNATIONALTINGKATPROVINSI -> NSONS = 5
Yang terpanjang adalah 'ONSONS' = 6
Jawaban = 6
Solusi penuh:
#include <bits/stdc++.h>
using namespace std;
int main(){
string S;
cin >> S;
char c [3] = {'O', 'S', 'N'};
int jawab = 0;
sort (c, c + 3);
do {
int count = 0, index = 0;
for (auto itr : S){
if (itr == c [index]){
count++;
index++;
index %= 3;
}
}
jawab = max (jawab, count);
} while (next_permutation (c, c + 3));
cout << (jawab < 3 ? -1 : jawab) << '\n';
return 0;
}
Studi Kasus B: Berbagi Banyak Candil
Studi Kasus B: Berbagi Banyak Candil
B1. A
B1. A
Pak Dengklek membeli 100 candil, dan agar sisa candil = 10, harus berlaku 100 mod n = 10.
A. n = 9
100 mod 9 = 1 -> Tidak valid
B. n = 15
100 mod 15 = 10 -> Valid
C. n = 18
100 mod 18 = 10 -> Valid
D. n = 30
100 mod 30 = 10 -> Valid
E. n = 45
100 mod 45 = 10 -> Valid
Setelah di coba, akan terlihat bahwa yang tidak mungkin adalah pilihan A.
B2. 4
B2. 4
Pak Dengklek memiliki paling banyak 100 ekor bebek.
Pak dengklek membeli 20 candil, dan sisa 2.
Dari pernyataan diatas dapat di simplifikasi bahwa kita mencari n yang memenuhi syarat:
20 mod n = 2
n <= 100
n | (20 - 2) -> n | 18
Cara mudahnya adalah kita tinggal cari pembagi 18 yang memenuhi syarat.
Pembagi dari 18: 1, 2, 3, 6, 9, 18
1 -> 20 mod 1 = 0 -> Tidak valid
2 -> 20 mod 2 = 0 -> Tidak valid
3 -> 20 mod 3 = 2 -> Valid
6 -> 20 mod 6 = 2 -> Valid
9 -> 20 mod 9 = 2 -> Valid
18 -> 20 mod 18 = 2 -> Valid
B3. SALAH
B3. SALAH
Terdapat kasus dimana C = D
Saat C = D, syarat n | (C - D) sudah pasti valid, karena semua bilangan dapat dibagi oleh 0, maka jumlah kemungkinan n = max (0, B - D) jika nilai B jauh diatas nilai C dan D, B - C > C mungkin terjadi.
Contoh:
B = 100, C = 10, D = 10, maka n = 90 -> Banyaknya kemungkinan banyaknya bebek > banyak butir candil yang dibeli.
Maka SALAH.
Soal Pemrograman
Soal Pemrograman
Pertama, perhatikan bahwa jika kita membagi C candil ke n bebek dan secara merata, sisa candil adalah C mod n, yaitu D.
Maka C mod n = D.
Kita ingin mengetahui berapa banyak pilihan jumlah bebek n (1 <= n <= B) yang memenuhi syarat.
Berdasarkan rumus diatas, kita dapat simpulkan bahwa n membagi (C - D).
Kedua, dalam operasi modulo, pembagi harus lebih besar dari sisa, dengan kata lain n > D.
Jadi dapat kita simpulkan kita mencari berapa banyak n yang valid ke dalam persamaan berikut:
1 <= n <= B
n | (C - D)
n > D
Kemudian kita bagi menjadi 2 kasus,
Jika C == D
Menandakan bahwa tidak ada candil yang dibagikan. Karena C - D = 0, semua bilangan dapat membagi 0.
Maka semua n yang memenuhi
n > D
1 <= n <= B
Valid. Maka jawaban terletak di D < n <= B
Maka solusi dari kasus ini adalah max (0, B - D)
Jika C > D
Kita tinggal mencari semua pembagi dari C - D.
Kemudian untuk semua pembagi 'd', kita hitung sebagai jawaban jika dan hanya jika 'd' memenuhi D < d <= B.
Kompleksitas waktu: O (sqrt (C - D))
Subsoal 1:
B = 25
C = 8420
D = 20
Cari semua n yang memenuhi:
D < n <= B
n | (C - D)
Kita hanya perlu mencari faktor dari 8400 yang diantara 21 - 25:
21, 24, 25
Jawaban = 3
Solusi Penuh:
#include <bits/stdc++.h>
using namespace std;
int main (){
long long B, C, D;
cin >> B >> C >> D;
long long dibagikan = C - D;
if (dibagikan == 0) {
cout << max (0LL, B - D) << '\n';
return 0;
}
int jawab = 0;
vector <long long> pembagi;
for (long long i = 1 ; i * i <= dibagikan ; i ++) {
if (dibagikan % i == 0) {
if (i > D and i <= B) {
jawab ++;
}
if (i != dibagikan / i) {
if (dibagikan / i > D and dibagikan / i <= B) {
jawab ++;
}
}
}
}
cout << jawab << '\n';
return 0;
}
Studi Kasus C. Tebas Tebang Pohon
Studi Kasus C. Tebas Tebang Pohon
C1. 91
C1. 91
Hanya pohon yang memiliki tinggi > 7 yang akan terpotong, maka pohon 8, 9, ... , 20 akan terpotong. Ada 13 pohon yang terpotong.
Maka jumlah potongan adalah
8 + 9 + 10 + ... + 20 - 13 * 7 = 91
C2. BENAR
C2. BENAR
Semakin rendah ketinggian maksimumnya, semakin banyak potongan pohon yang akan dihasilkan, maka jika kita dapat membangun kandang dengan ketinggian maksimum Z, kita juga pasti bisa membuat kandang dengan ketinggian maksimum Z - 1, dengan syarat Z > 0.
C3. 57
C3. 57
Gunakan binary search untuk mendapatkan jawaban, set range dari 0 hingga tinggi pohon tertinggi.
Maka range nya adalah [0, 100], karena binary search ini memiliki 101 range, maksimum iterasi nya adalah log2(101) = 7 iterasi.
Inisialisasi:
low = 0
high = 100
ans = -1
Iterasi 1:
mid = (0 + 100) / 2 = 50
hitung f(50) = (60−50)+(70−50)+(80−50)+(90−50)+(100−50) = 10+20+30+40+50 = 150
Karena 150 >= 111 -> mid valid
ans = 50
low = mid + 1 = 51
Iterasi 2:
mid = (51 + 100) / 2 = 75
f(75) = (80−75)+(90−75)+(100−75) = 5+15+25 = 45
Karena 45 < 111 -> mid terlalu tinggi
high = mid − 1 = 74
Iterasi 3:
mid = (51 + 74) / 2 = 62
f(62) = (70−62)+(80−62)+(90−62)+(100−62)
= 8+18+28+38 = 92
Karena 92 < 111 -> high = 61
Iterasi 4:
mid = (51 + 61) / 2 = 56
f(56) = (60−56)+(70−56)+(80−56)+(90−56)+(100−56)
= 4+14+24+34+44 = 120
Karena 120 >= 111 -> ans = 56; low = 57
Iterasi 5:
mid = (57 + 61) // 2 = 59
f(59) = (60−59)+(70−59)+(80−59)+(90−59)+(100−59)
= 1+11+21+31+41 = 105
Karena 105 < 111 -> high = 58
Iterasi 6:
mid = (57 + 58) / 2 = 57
f(57) = (60−57)+(70−57)+(80−57)+(90−57)+(100−57)
= 3+13+23+33+43 = 115
Karena 115 >= 111 -> ans = 57; low = 58
Iterasi 7:
mid = (58 + 58) / 2 = 58
f(58) = (60−58)+(70−58)+(80−58)+(90−58)+(100−58)
= 2+12+22+32+42 = 110
Karena 110 < 111 -> high = 57
Loop berhenti karena low (58) > high (57).
Hasil akhir: ans = 57
Soal Pemrograman
Soal Pemrograman
Subsoal 1:
Definisikan f (x) = jumlah potongan yang didapat jika batas tinggi maksimum pohon adalah x.
Tujuan kita adalah mencari x tertinggi yang memenuhi kondisi f (x) >= M.
Karena N <= 1000 dan Ai <= 1000, kita dapat lakukan bruteforce untuk menghitung semua f (x) dari 0 hingga 1000.
Kompleksitas waktu: O (N * Max_Ai)
#include <bits/stdc++.h>
using namespace std;
int main () {
int N;
long long M;
cin >> N >> M;
int A[N + 1];
int maks = 0;
for (int i = 1 ; i <= N ; i ++) {
cin >> A[i];
maks = max (maks, A [i]);
}
int jawab = -1;
for (int x = maks ; x >= 0 ; x --) {
long long jumlah = 0;
for (int i = 1 ; i <= N ; i ++) {
jumlah += max (0, A [i] - x);
}
if (jumlah >= M) {
jawab = x;
break;
}
}
cout << jawab << '\n';
return 0;
}
Subsoal 2:
Observasi:
Fungsi bersifat monoton menurun.
f (0) >= f (1) >= f (2) >= ... >= f (max_Ai)
Jika f (0) < M, maka jawaban nya sudah pasti -1, karena f (0) adalah fungsi yang nilainya paling maksimum, jika f (0) < M, maka semuanya juga akan lebih kecil dari M/
Karena fungsi besifat monoton, kita dapat lakukan binary search, ambil batas-batas yang memungkinkan untuk menjadi jawaban, yaitu [0, max_Ai]. Kemudian dengan binary search kalian akan mendapatkan x maksimum yang memenuhi fungsi f (x) >= M.
Kompleksitas waktu: O (N log Max_Ai)
#include <bits/stdc++.h>
using namespace std;
int main () {
int N;
long long M;
cin >> N >> M;
int A[N + 1];
long long jumlah = 0;
for (int i = 1 ; i <= N ; i ++) {
cin >> A[i];
jumlah += A[i];
}
if (jumlah < M) {
cout << -1 << '\n';
return 0;
}
int l = 0, r = *max_element (A + 1, A + N + 1);
while (l < r) {
int mid = l + (r - l + 1) / 2;
long long cur = 0;
for (int i = 1 ; i <= N ; i ++) {
if (A[i] > mid) {
cur += A[i] - mid;
}
}
if (cur >= M)
l = mid;
else
r = mid - 1;
}
cout << l << '\n';
return 0;
}
Studi Kasus D. Kalkulator Pengubahan Basis
Studi Kasus D. Kalkulator Pengubahan Basis
D1. 610110
D1. 610110
Konversi 15015 ke basis 13
15015 / 13 = 1155, sisa 0
1155 / 13 = 88, sisa 11
88 / 13 = 6, sisa 10
6 / 13 = 0, sisa 6
Maka jawabannya adalah 610110
D2. C
D2. C
Target string: "123010"
Angka yang diubah ke dalam basis 14 oleh Pak Dengklek adalah 33 526
Konversi 33 526 ke basis 14
33526 / 14 = 2394, sisa 10
2394 / 14 = 171, sisa 0
171 / 14 = 12, sisa 3
12 / 14 = 0, sisa 12
Maka 33526 dalam basis 14 adalah 123010 -> Valid
Angka yang diubah ke dalam basis 14 oleh Pak Dengklek adalah 44 502
Konversi 44 502 ke basis 14
44502 / 14 = 3178, sisa 10
3178 / 14 = 227, sisa 0
227 / 14 = 16, sisa 3
16 / 14 = 1, sisa 2
1 / 14 = 0, sisa 1
Maka 44502 dalam basis 14 adalah 123010 -> Valid
Angka yang diubah ke dalam basis 14 oleh Pak Dengklek adalah 44 506
Konversi 44506 ke basis 14
44506 / 14 = 3179, sisa 0
3179 / 14 = 227, sisa 1
227 / 14 = 16, sisa 3
16 / 14 = 1, sisa 2
1 / 14 = 0, sisa 1
Maka 44506 dalam basis 14 adalah 12301 -> Tidak valid
Angka yang diubah ke dalam basis 14 oleh Pak Dengklek adalah 469 238
Konversi 469328 ke basis 14
469238 / 14 = 33517, sisa 0
33517 / 14 = 2394, sisa 1
2394 / 14 = 171, sisa 0
171 / 14 = 12, sisa 3
12 / 14 = 0, sisa 12
Maka 469238 dalam basis 14 adalah 123010 -> Valid
Angka yang diubah ke dalam basis 14 oleh Pak Dengklek adalah 622902
Konversi 622902 ke basis 14
622902 / 14 = 44493, sisa 0
44493 / 14 = 3178, sisa 1
3178 / 14 = 227, sisa 0
227 / 14 = 16, sisa 3
16 / 14 = 1, sisa 2
2 / 14 = 2, sisa 1
Maka 622902 dalam basis 14 adalah 123010 -> Valid
Maka yang tidak mungkin adalah C.
D3. 5
D3. 5
Perhatikan bahwa kita dapat memecah string Y dengan berbagai cara dengan syarat angka setiap segmen harus < basis.
Pada string "71112016" dalam basis 16
Kita dapat pisahkan dulu yang sudah pasti terdiri oleh 1 angka doang
7 | 1 1 1 2 | 0 | 1 | 6
'7', '0', '1', '6' sudah pasti sendiri karena jika angka angka tersebut digabungkan dengan angka sebelahnya, sudah pasti menjadi tidak valid (>= basis atau leading zero).
Jadi berdasarkan observasi tersebut, kita hanya perlu menghitung berapa cara kita dapat memecah 1 1 1 2 dalam basis 16
1 | 11 | 2
11 | 1 | 2
11 | 12
1 | 1 | 12
1 | 1 | 1 | 2
Terdapat 5 konfigurasi. Maka jawaban = 5
7 | 1 | 11 | 2 | 0 | 1 | 6
7 | 11 | 1 | 2 | 0 | 1 | 6
7 | 11 | 12 | 0 | 1 | 6
7 | 1 | 1 | 12 | 0 | 1 | 6
7 | 1 | 1 | 1 | 2 | 0 | 1 | 6
Soal Pemrograman
Soal Pemrograman
Solusi penuh:
Kita dapat menggunakan dynamic programming (DP).
Definisi DP:
Definisikan dp [i] sebagai berapa banyak cara valid untuk memecah substring Y mulai dari index i hingga indeks akhir. Kita inisialisasikan dp [n] = 1 (hanya ada satu cara untuk memecah string kosong, karena menggunakan 0 indexing). Maka jawaban akan terletak pada dp [0].
Subsoal 1:
Kita dapat memecah segmen untuk membuat angka yang memenuhi hal berikut:
Tidak leading zero
Angka yang dibuat < basis.
Karena constraint sangat kecil, basis <= 16 dan |Y| <= 6.
Kita bisa looping index dan basisnya.
Transisi:
Kasus 1: basis <= 10
Jika basis <= 10, maka angka maximum per segmen yang dapat dibentuk sudah pasti 1 digit, maka transisi nya adalah:
Jika Y [i] - '0' < basis:
dp [i] = dp [i + 1]
Jika Y [i] - '0' >= basis
dp [i] = 0 (Sudah pasti invalid)
Kasus 2: basis > 10
Karena tidak boleh leading zero, jika Y [i] = '0', maka transisinya adalah
dp [i] = dp [i + 1]
Jika i + 1 < n && Y [i] != 0 && (Y [i] - '0') * 10 + (Y [i + 1] - '0) < basis
dp [i] = dp [i + 1] + dp [i + 2].
Kompleksitas waktu = O (n * basis)
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7 ;
int add (long long a, long long b) {
a += b ;
if (a >= mod) a -= mod ;
return a ;
}
int main () {
int basis;
cin >> basis;
string Y;
cin >> Y;
int n = Y.length ();
int dp [n + 1];
dp [n] = 1;
for (int i = n - 1 ; i >= 0 ; i --) {
dp [i] = 0;
if (basis <= 10) {
if (Y [i] - '0' < basis) {
dp [i] = dp [i + 1];
}
} else {
if (Y [i] != '0' && i + 1 < n && (Y [i] - '0') * 10 + (Y [i + 1] - '0') < basis) {
dp [i] = add (dp [i + 1], dp [i + 2]);
} else {
dp [i] = dp [i + 1];
}
}
}
cout << dp [0] << '\n';
return 0;
}
Subsoal 2:
Kita bisa mengoptimisasikan dengan looping index dan jumlah digit basisnya saja.
Transisi:
Kasus 1: Y[i] = '0'
Kita tidak boleh membuat angka dengan leading zero, jika Y[i] adalah '0', maka satu satunya angka yang valid yang dapat dibuat adalah '0', kemudian lanjut memecah ke angka berikutnya.
dp [i] = dp [i + 1]
Kasus 2: Y[i] != '0'
Kita dapat membuat angka dengan panjang dari 1 sampai jumlah digit basis dengan syarat angka yang dibuat < basis.
Dengan kata lain untuk semua panjang 'x' dari 1 sampai jumlah digit basis.
dp [i] += dp [i + x] dengan syarat value Y[i] ... Y[i+x-1] < basis dan i + x <= n
Kompleksitas waktu = O (nL), dimana n = panjang string Y, dan L = ceil (log10(basis))
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7 ;
int add (long long a, long long b) {
a += b ;
if (a >= mod) a -= mod ;
return a ;
}
int konversi (string &x, int l, int r) {
long long hasil = 0;
for (int i = l ; i <= r ; i ++) {
hasil *= 10 ;
hasil += x [i] - '0';
}
return hasil;
}
int main () {
int basis;
cin >> basis;
string Y;
cin >> Y;
int digitBasis = 0;
int temp = basis;
while (temp) {
digitBasis ++;
temp /= 10;
}
int n = Y.length ();
int dp [n + 1];
dp [n] = 1;
for (int i = n - 1 ; i >= 0 ; i --) {
dp [i] = 0;
if (Y [i] == '0') {
dp [i] = dp [i + 1];
continue;
}
for (int j = 1; j <= digitBasis && i + j - 1 < n ; j ++) {
// Fungsi konversi untuk mendapatkan value berbentuk integer
if (konversi (Y, i, i + j - 1) < basis) {
dp [i] = add (dp [i], dp [i + j]);
}
}
}
cout << dp [0] << '\n';
return 0;
}
Studi Kasus E. Gosip Gulali
Studi Kasus E. Gosip Gulali
E1. 8
E1. 8
Jenis gulali yang tersedia: {3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45}
Favorit Bebek = {10, 20, 30, 40, 50}
Untuk 10 -> Pilih 9 -> |10 - 9| = 1
Untuk 20 -> Pilih 21 -> |20 - 21| = 1
Untuk 30 -> Pilih 30 -> |30 - 30| = 0
Untuk 40 -> Pilih 39 -> |40 - 39| = 1
Untuk 50 -> Pilih 45 -> |50 - 45| = 5
Jumlah = 1 + 1 + 0 + 1 + 5 = 8.
E2. 10
E2. 10
Kwak <-> Kwok
Kwuk <-> Kwok
Maka
Kwak <-> Kwok <-> Kwuk saling terhubung
Jenis gulali yang tersedia {4, 2, 9}
Grup Kwak, Kwok, Kwuk {8, 3 1}
Gulali jenis 4
|8 - 4| + |3 - 4| + |1 - 4| = 4 + 1 + 3 = 8
Gulali jenis 2
|8 - 2| + |3 - 2| + |1 - 2| = 6 + 1 + 1 = 8
Gulali jenis 9
|8 - 9| + |3 - 9| + |1 - 9| = 1 + 6 + 8 = 15
Pilih antara jenis 2 / 4, menghasilkan ketidak kepuasan yang minimal -> 8
Grup Kwik {6}
Gulali jenis 4
|6 - 4| = 2
Gulali jenis 2
|6 - 2| = 4
Gulali jenis 9
|6 - 9| = 3
Pilih jenis 4, menghasilkan ketidak puasan yang minimal -> 2
Jumlah = 2 + 8 = 10
E3. SALAH
E3. SALAH
Suatu titik yang meminimalkan jumlah ketidak puasan dari suatu grup adalah median, bukan rata-rata.
Contoh, kita memiliki 3 Bebek dengan favorit {1, 1, 10}.
Rata-rata = (1 + 1 + 10) / 3 = 4
|1 - 4| + |1 - 4| + |10 - 4| = 3 + 3 + 6 = 12
Sedangkan yang optimal adalah median tersebut, yaitu 1
|1 - 1| + |1 - 1| + |10 - 1| = 9
Jadi jawabannya SALAH.
Soal Pemrograman
Soal Pemrograman
Subsoal 1:
Pertama, kita harus mengelompokkan bebek-bebek yang bergosip, dapat diselesaikan menggunakan Disjoint Set Union (DSU), yang kemudian kita akan proses per kelompok nya.
Karena M <= 10, kita bisa lakukan bruteforce saja, per kelompok yang ada, kita bisa coba semua jenis gulali, dan cari jenis gulali yang menghasilkan nilai ketidakpuasan terkecil.
Kompleksitas waktu = O (M * N).
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
vector <int> parent ;
public:
DisjointSet (int n) {
parent.resize (n + 1) ;
for (int i = 0 ; i <= n ; i ++) {
parent [i] = i ;
}
}
int FUP (int x) {
if (x == parent [x]) return x ;
return parent [x] = FUP (parent [x]) ;
}
void join (int a, int b) {
if (FUP (a) == FUP (b)) return;
parent [FUP (b)] = FUP (a);
}
} ;
int main () {
int N, M, K;
cin >> N >> M >> K;
int val [N + 1];
for (int i = 1 ; i <= N ; i ++) {
cin >> val [i];
}
set <long long> gulali;
for (int i = 1 ; i <= M ; i ++) {
int jenis;
cin >> jenis;
gulali.insert (jenis);
}
DisjointSet ds (N);
for (int i = 1 ; i <= K ; i ++) {
int u, v;
cin >> u >> v;
ds.join (u, v);
}
vector <int> group [N + 1];
for (int i = 1 ; i <= N ; i ++) {
group [ds.FUP (i)].push_back (val [i]);
}
long long jawab = 0;
for (int i = 1 ; i <= N ; i ++) {
if (group [i].empty ()) {
continue;
}
long long mn = 1e18;
for (auto g : gulali) {
long long jumlah = 0;
for (auto itr : group [i]) {
jumlah += abs (itr - g);
}
mn = min (mn, jumlah);
}
jawab += mn;
}
cout << jawab << '\n';
return 0;
}
Subsoal 2:
Observasi: Suatu titik yang meminimalkan jumlah ketidak puasan dari suatu grup adalah median, jadi, untuk setiap group, kita dapat mencari jenis gulali yang jarak nya terdekat terhadap median.
Kita proses untuk setiap kelompok:
Kasus 1: jika size kelompoknya ganji
Kita hanya harus mengecek jenis gulali terdekat yang >= median dan < median. Hal ini dapat dilakukan dengan binary search.
Kasus 2: Jika size kelompoknya genap
Anggap median size kelompok / 2 sebagai medianL, dan size kelompok / 2 + 1 sebagai medianR. Cari jenis gulali terdekat untuk masing masing medianL dan medianR, kemudian bandingkan.
Kompleksitas waktu = O (N log N + (N + M) log M).
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
vector <int> parent ;
public:
DisjointSet (int n) {
parent.resize (n + 1) ;
for (int i = 0 ; i <= n ; i ++) {
parent [i] = i ;
}
}
int FUP (int x) {
if (x == parent [x]) return x ;
return parent [x] = FUP (parent [x]) ;
}
void join (int a, int b) {
if (FUP (a) == FUP (b)) return;
parent [FUP (b)] = FUP (a);
}
} ;
int main () {
int N, M, K;
cin >> N >> M >> K;
int val [N + 1];
for (int i = 1 ; i <= N ; i ++) {
cin >> val [i];
}
set <long long> gulali;
// offset
gulali.insert (1e10);
gulali.insert (-1e10);
for (int i = 1 ; i <= M ; i ++) {
int jenis;
cin >> jenis;
gulali.insert (jenis);
}
DisjointSet ds (N);
for (int i = 1 ; i <= K ; i ++) {
int u, v;
cin >> u >> v;
ds.join (u, v);
}
vector <int> group [N + 1];
for (int i = 1 ; i <= N ; i ++) {
group [ds.FUP (i)].push_back (val [i]);
}
long long jawab = 0;
for (int i = 1 ; i <= N ; i ++) {
if (group [i].empty ()) {
continue;
}
sort (group [i].begin (), group [i].end ());
if (group [i].size () & 1) {
int median = group [i].size () >> 1;
auto R = gulali.upper_bound (group [i][median]);
auto L = R;
L --;
long long jumlahR = 0, jumlahL = 0;
for (auto itr : group [i]) {
jumlahL += abs (itr - *L);
jumlahR += abs (itr - *R);
}
jawab += min (jumlahL, jumlahR);
} else {
int medianR = group [i].size () >> 1;
int medianL = medianR - 1;
auto R = gulali.upper_bound (group [i][medianL]);
auto L = R;
L --;
long long jumlahR = 0, jumlahL = 0, mn = 1e18;
for (auto itr : group [i]) {
jumlahL += abs (itr - *L);
jumlahR += abs (itr - *R);
}
mn = min (mn, min (jumlahL, jumlahR));
jumlahL = 0, jumlahR = 0;
R = gulali.upper_bound (group [i][medianR]);
L = R;
L --;
for (auto itr : group [i]) {
jumlahL += abs (itr - *L);
jumlahR += abs (itr - *R);
}
mn = min (mn, min (jumlahL, jumlahR));
jawab += mn;
}
}
cout << jawab << '\n';
return 0;
}
Studi Kasus F. Maju Tak Papan
Studi Kasus F. Maju Tak Papan
F1. 35
F1. 35
Mulai dari (1, 1), jumlah = 4
Petak kanan (1, 2) = 6
Petak bawah (2, 1) = 3
Kanan > Bawah -> Bergerak ke petak (1, 2), jumlah = 4 + 6 = 10
Pada petak (1, 2)
Petak kanan (1, 3) = 1
Petak bawah (2, 2) = 5
Bawah > Kanan -> Bergerak ke petak (2, 2), jumlah = 10 + 5 = 15
Pada petak (2, 2)
Petak kanan (2, 3) = 8
Petak bawah (3, 2) = 11
Bawah > Kanan -> Bergerak ke petak (3, 2), jumlah 15 + 11 = 26
Pada petak (3, 2)
(Baris terakhir) hanya bisa ke petak kanan (3, 3) = 2
Bergerak ke petak (3, 3), jumlah = 26 + 2 = 28
Pada petak (3, 3)
(Baris terakhir) hanya bisa ke petak kanan (3, 4) = 7
Bergerak ke petak (3, 4), jumlah = 28 + 7 = 35
F2. 22
F2. 22
Tetapkan angka 1 pada (1, 1) agar jawaban lebih optimal.
Paksa robot gerak ke (1, 2) terlebih dahulu, setelah sampai di (1, 2) robot akan otomatis ke (2, 2) -> (3, 2) -> (4, 2) -> (5, 2) karena sudah di kolom terakhir.
Oleh karena itu, gunakan 4 angka terkecil yang belum dipakai untuk (2, 2), (3, 2), (4, 2), (5, 2) yaitu 2, 3, 4, 5. Maka jumlah nya sekarang adalah 1 + 2 + 3 + 4 + 5 = 15.
Kita tinggal menghitung cost untuk memaksa robot dari (1, 1) ke (1, 2). Karena angka 1-5 sudah dipakai, gunakan angka 6 di petak (2, 2) dan angka 7 di petak (1, 2) agar robot berpindah ke (1, 2).
Jumlah = 1 + 2 + 3 + 4 + 5 + 7 = 22
F3. 18
F3. 18
Sama seperti F2,
Tetapkan angka 1 pada (1, 1) agar jawaban lebih optimal.
Paksa robot gerak ke (1, 3) terlebih dahulu, setelah sampai di (1, 3) robot akan otomatis ke (2, 3) -> (3, 3) karena sudah di kolom terakhir.
Oleh karena itu, gunakan 2 angka terkecil yang belum dipakai untuk (2, 3), (3, 3) yaitu 2, 3. Maka jumlah nya sekarang adalah 1 + 2 + 3 = 6.
Kita tinggal menghitung cost untuk memaksa robot dari (1, 1) ke (1, 3).
Petak (1, 1) -> (1, 2)
Karena angka 1-3 sudah dipakai, gunakan angka 4 di petak (2, 1) dan angka 5 di petak (1, 2) agar robot berpindah ke (1, 2).
Jumlah = 6 + 5 = 11.
Petak (1, 2) -> (1, 3)
Karena angka 1-5 sudah dipakai, gunakan angka 6 di petak (2, 2) dan angka 7 di petak (1, 3) agar robot berpindah ke (1, 3)
Jumlah = 11 + 7 = 18.
Soal Pemrograman
Soal Pemrograman
Observasi pertama: kita dapat menggunakan angka 1 di petak (1, 1).
Kita dapat membuat robot bergerak ke ujung bawah kiri / ujung kanan atas terlebih dahulu.
Perhatikan setelah sampai di ujung bawah kiri / ujung kanan atas, robot akan terjamin dapat berjalan dengan lurus ke kanan bawah. Maka kita dapat masukkan saja angka-angka terkecil yang belum dipakai, dan semakin banyak angka-angka terkecil yang kita dapat masukkan, akan semakin optimal.
Berdasarkan observasi diatas:
Paksa robot bergerak ke lurus ke ujung papan (pilih jalur yang lebih pendek).
Kasus 1: Jika N >= M, kita dapat paksa robot bergerak dari (1, 1) ke (1, M), kemudian dari (1, M) kita sudah terjamin bisa menggunakan N - 1 angka-angka terkecil untuk lurus ke (N, M)
Cara ini akan lebih optimal dibanding kita ke (N, 1) kemudian ke (N, M) yang hanya akan terjamin bisa menggunakan M angka-angka terkecil, karena N >= M.
Maka cost dari (1, M) ke (N, M) adalah 2 + 3 + ... + N = N * (N + 1) / 2 - 1. (Kurangi 1 karena 1 sudah digunakan di petak (1, 1)).
Kasus 2: Jika N < M, kita lakukan sebaliknya, kita paksa robot bergerak ke (N, 1) kemudian ke (N, M) agar terjamin bisa menggunakan M - 1 angka-angka terkecil, karena M > N.
Maka costnya adalah M * (M + 1) / 2 - 1.
Agar lebih mudah, jika N > M, kita melakukan swap (N, M), hal ini tidak akan memengaruhi jawaban karena dengan menggunakan cara diatas, dari (1, 1) ke (N, M) dan dari (1, 1) ke (M, N) masing masing membutuhkan (N - 1) + (M - 1) gerakan.
Sekarang, kita tinggal menghitung cost agar robot bergerak paksa ke (N, 1)
Subsoal 1:
Karena N <= 2, terdapat 2 kasus:
Kasus 1: N = 1
Jika N = 1, sama saja seperti kita masih di titik awal. Maka cost = 0.
Rumus akhir = 1 + M * (M + 1) / 2 - 1.
Kasus 2: N = 2
Karena sudah terpakai M bilangan pertama, agar dapat gerak paksa dari (1, 1) ke (2, 1), kita letakkan M + 1 di petak (1, 2), dan M + 2 di petak (2, 1), dengan begitu robot sudah pasti bergerak ke (2, 1) yaitu (N, 1), karena disini N = 2. Maka cost = M + 2.
Rumus akhir = 1 + M * (M + 1) / 2 - 1 + M + 2.
Kompleksitas waktu = O (1).
#include <bits/stdc++.h>
using namespace std;
int main () {
long long N, M;
cin >> N >> M;
if (N > M) {
swap (N, M);
}
if (N == 1) {
cout << 1 + M * (M + 1) / 2 - 1 << '\n';
} else {
cout << 1 + M * (M + 1) / 2 - 1 + (M + 2) << '\n';
}
return 0;
}
Subsoal 2:
Setelah mengetahui N akan selalu menjadi yang lebih kecil, maka M bilangan pertama sudah pasti terpakai untuk gerak dari (N, 1) ke (N, M). Maka bilangan-bilangan terkecil yang tersedia adalah M + 1, M + 2, ..., N * M.
Untuk memaksa robot bergerak kebawah, untuk setiap petak, kita dapat tetapkan value dari petak sebelah kanan sebagai M + 1, kemudian petak bawah dengan M + 2, dengan begitu, robot akan terjamin bergerak ke petak bawah (M + 2). Lakukan terus sampai mencapai (N, 1), dengan begitu cost nya adalah (M + 2) + (M + 4) + ... (M + 2 * (N - 1)) = (M + N) * (N - 1).
Maka rumus akhirnya adalah: 1 + M * (M + 1) / 2 - 1 + (M + N) * (N - 1).
Kompleksitas waktu = O (1).
#include <bits/stdc++.h>
using namespace std;
int main () {
long long N, M;
cin >> N >> M;
if (N > M) {
swap (N, M);
}
cout << 1 + M * (M + 1) / 2 - 1 + (M + N) * (N - 1) << '\n';
return 0;
}
Google Sites
Report abuse