- Beranda
- Komunitas
- Tech
- Programmer Forum
Absolute Permutation – Hackerrank
TS
opvl
Absolute Permutation – Hackerrank
Kali ini opvl bakal sharing tentang solving problem dari hackerrank. Buat yang belum tau hackerrank itu situs yang biasanya buat orang-orang belajar problem solving. Disitu ada banyak banget soal-soal yang bisa buat latihan, mulai dari kusus bahasa pemrograman tertentu sampai yang tentang tentang database atau keamanan jaringan. Soal-soal di hackerrank juga ada tingkatannya easy, medium ama hard.
Soal Absolute Permutation ini masuk kategori medium. Di sesi sharing kali ini opvl bakal bahas pemecahannya. Nah pemecahan soalnya sendiri bakal ada dua, satu yang logika nya bener tapi masih kena LTE ama satu lagi yang udah di improve. TLE (Time Limit Exceeded) itu kalau biasanya logika nya udah bener tapi kelamaan buat selesein soalnya.
Dibawah ini soal yang udah diterjemahin ke bahasa Indonesia
Soal
Kita definisikan P sebagai permutasi dari n bilangan natural pertama pada rentang [1, n]. post[i] merupakan nilai pada posisi ke i pada permutasi P menggunakan indeks berbasis 1.
P dianggap sebagai permutasi absolut apabila |pos[i]-i| = k bernilai benar untuk setiap i∈ [1, n].
Diberikan n dan k, tampilkan permutasi P absolut terkecil secara leksikografis. Apabila tidah terdapat permutasi absolut, tampilkan -1.
Sebagai contoh, diberikan n = 4 dan array post = [1, 2, 3, 4]. Apabila kita gunakan basis indeks 1, buat sebuah permutasi dimana setiap |pos[i]-i| = k. Apabila k = 2, kita dapat mengatur ulang posisi array tersebut menjadi [3, 4, 1, 2].
Tabel 1
Deskripsi Fungsi
Selesaikan fungsi absolutePermutation dibawah. Fungsi harus mengembalikan sebuah integer yang merepresentasikan permutasi terkecil secara leksikografis, atau -1 apabila tidak ditemukan.
Fungsi absolutePermutation mempunyai beberapa parameter berikut:
n : batas atas bilangan natural, inklusif
k : merukapan angka perbedaan masing-masing elemen dengan indeks nya
Format Masukan
Baris pertama merupakan integer t, merupakan jumlah test case.
Masing-masing t baris berikutnya terdapat 2 integer, n dan k.Batasan
1 ≤ t ≤ 10
1 ≤ n ≤ 10ˆ5
0 ≤ k < n
Format Keluaran
Pada baris baru dari setiap masing-masing test case, tampilkan permutasi absolut terkecil secara leksikografis. Apabila tidak terdapat permutasi absolut, tampilkan -1.
Contoh Masukan
3
2 1
3 0
3 2
Contoh Keluaran
2 1
1 2 3
-1
Penjelasan
Test Case 0:
Tabel 2
Test Case 1:
Tabel 3
Test Case 2:
Tidak terdapat absolut permutataion, jadi tampilkan -1
Pembahasan
Dibawah ini source code pertama yang masih kena TLE (Time Limit Exceeded)
Mungkin ada yang tanya, kenapa kita pakai 2xselisihbuat cek angka yang dimasukin apa bisa dijadiin absolutePermutation. Kita pakai 2xselisih soalnya kita perlu bikin kelopok yang anggotanya sebanyak 2xselisih nya biar bisa dijadiin absolutePermutation. Contohnya misal kita pengen ngecek angka = 4 selisih = 2, nah itu kan kita perlu jadiin [1, 2, 3, 4] jadi [3, 4, 1, 2], jadi kita perlu 2xselisih jumlah anggota. Biar lebih paham source code diatas coba liat contoh kasus dibawah, pakai angka = 12 selisih = 2.
Kalau pakai source code yang diatas emang secara logika udah bener, cuma masih kena TLE jadi perlu diperbaikin lagi biar tambah cepet. Bagian yang paling banyak makan waktu sama memori dibagian bikin group sama muter nya biar jadi absolutePermutation. Nah source code dibawah udah dikurangin bagian yang makan banyak waktu sama memori.
Bedanya dari source code yang pertama, do source code yang kedua ini tiap kita nemuin angka yang belum pernah dituker kita tuker dengan nilai sebanyak selisih nya. Biar lebih jelas coba liat contoh pembahasan pakai angka = 12 selisih 2
Source code yang kedua kita cuma pakai 1 looping dan gk pakai nyimpen-nyimpen di variabel lain, jadi lebih efisien.
Segini dulu buat sharing minggu ini, semoga penjelasan pakai contoh soal bisa bikin paham. Buat yang pengen tanya atau request sesuatu silakan colek opvllewat email hq.opvl@gmail.com atau lewat comment dibawah. Boleh juga mampir ke blog opvl di Absolute Permutation - Hackerrank. Moga bermanfaan.
Soal Absolute Permutation ini masuk kategori medium. Di sesi sharing kali ini opvl bakal bahas pemecahannya. Nah pemecahan soalnya sendiri bakal ada dua, satu yang logika nya bener tapi masih kena LTE ama satu lagi yang udah di improve. TLE (Time Limit Exceeded) itu kalau biasanya logika nya udah bener tapi kelamaan buat selesein soalnya.
Dibawah ini soal yang udah diterjemahin ke bahasa Indonesia
Soal
Kita definisikan P sebagai permutasi dari n bilangan natural pertama pada rentang [1, n]. post[i] merupakan nilai pada posisi ke i pada permutasi P menggunakan indeks berbasis 1.
P dianggap sebagai permutasi absolut apabila |pos[i]-i| = k bernilai benar untuk setiap i∈ [1, n].
Diberikan n dan k, tampilkan permutasi P absolut terkecil secara leksikografis. Apabila tidah terdapat permutasi absolut, tampilkan -1.
Sebagai contoh, diberikan n = 4 dan array post = [1, 2, 3, 4]. Apabila kita gunakan basis indeks 1, buat sebuah permutasi dimana setiap |pos[i]-i| = k. Apabila k = 2, kita dapat mengatur ulang posisi array tersebut menjadi [3, 4, 1, 2].
Tabel 1
Deskripsi Fungsi
Selesaikan fungsi absolutePermutation dibawah. Fungsi harus mengembalikan sebuah integer yang merepresentasikan permutasi terkecil secara leksikografis, atau -1 apabila tidak ditemukan.
Fungsi absolutePermutation mempunyai beberapa parameter berikut:
n : batas atas bilangan natural, inklusif
k : merukapan angka perbedaan masing-masing elemen dengan indeks nya
Format Masukan
Baris pertama merupakan integer t, merupakan jumlah test case.
Masing-masing t baris berikutnya terdapat 2 integer, n dan k.Batasan
1 ≤ t ≤ 10
1 ≤ n ≤ 10ˆ5
0 ≤ k < n
Format Keluaran
Pada baris baru dari setiap masing-masing test case, tampilkan permutasi absolut terkecil secara leksikografis. Apabila tidak terdapat permutasi absolut, tampilkan -1.
Contoh Masukan
3
2 1
3 0
3 2
Contoh Keluaran
2 1
1 2 3
-1
Penjelasan
Test Case 0:
Tabel 2
Test Case 1:
Tabel 3
Test Case 2:
Tidak terdapat absolut permutataion, jadi tampilkan -1
Pembahasan
Dibawah ini source code pertama yang masih kena TLE (Time Limit Exceeded)
Code:
def absolutePermutation(angka, selisih)
if selisih == 0
# kalau selisih yang dibutuhin 0, kita cuma
# perlu balikin array dari 1 sampai angka
# yang dimasukin
hasil = (1..angka).to_a
return hasil
elsif angka % (selisih*2) != 0
# kalau jumlah angka yang dimasukin gk bisa
# dibagi 2xselisih, gk bakal
# bisa dijadiin absolutePermutation
return [-1]
end
# jumlah iterasi yang dibutuhin buat tahu
# hasil absolutePermutation
ite = angka/(selisih*2)
hasil = []
# jumlah angka natural yang dibikin kelompok
# buat diputer (rotate) biar jadi
# absolutePermutation
grouping = selisih * 2
(1..ite).each do |i|
group = (grouping*(i-1)+1..grouping*i).to_a
# hasil diputer, dengan indeks ke `selisih`
# jadi yang paling depan
puter = group.rotate(selisih)
hasil = hasil | puter
end
return hasil
end
t = gets.to_i
t.times do |t_itr|
nk = gets.rstrip.split
angka = nk[0].to_i
selisih = nk[1].to_i
hasil = absolutePermutation angka, selisih
puts hasil.join " "
end
Mungkin ada yang tanya, kenapa kita pakai 2xselisihbuat cek angka yang dimasukin apa bisa dijadiin absolutePermutation. Kita pakai 2xselisih soalnya kita perlu bikin kelopok yang anggotanya sebanyak 2xselisih nya biar bisa dijadiin absolutePermutation. Contohnya misal kita pengen ngecek angka = 4 selisih = 2, nah itu kan kita perlu jadiin [1, 2, 3, 4] jadi [3, 4, 1, 2], jadi kita perlu 2xselisih jumlah anggota. Biar lebih paham source code diatas coba liat contoh kasus dibawah, pakai angka = 12 selisih = 2.
Code:
angka = 12
selisih = 2
ite = 3
grouping = 4
hasil = []
ITERASI i = 1
group = [1, 2, 3, 4]
puter = [3, 4, 1, 2]
hasil = [3, 4, 1, 2]
ITERASI i = 2
group [5, 6, 7, 8]
puter [7, 8, 5, 6]
hasil = [3, 4, 1, 2, 7, 8, 5, 6]
ITERASI i = 3
group = [9, 10, 11, 12]
puter = [11, 12, 9, 10]
hasil = [3, 4, 1, 2, 7, 8, 5, 6, 11, 12, 9, 10]
hasil akhir [3, 4, 1, 2, 7, 8, 5, 6, 11, 12, 9, 10]
Kalau pakai source code yang diatas emang secara logika udah bener, cuma masih kena TLE jadi perlu diperbaikin lagi biar tambah cepet. Bagian yang paling banyak makan waktu sama memori dibagian bikin group sama muter nya biar jadi absolutePermutation. Nah source code dibawah udah dikurangin bagian yang makan banyak waktu sama memori.
Code:
def absolutePermutation(angka, selisih)
if selisih == 0
# kalau selisih yang dibutuhin 0, kita cuma
# perlu balikin array dari 1 sampai angka
# yang dimasukin
result = (1..angka).to_a
return result
elsif angka % (selisih*2) != 0
# kalau jumlah angka yang dimasukin gk bisa
# dibagi 2xselisih, gk bakal
# bisa dijadiin absolutePermutation
return [-1]
end
counter = 0
#hasil awal
hasil = (1..angka).to_a
hasil.each { |i|
#counter+1 != i itu berarti `i` dibagian
#itu udah pernah diganti dari iterasi
#sebelumnya, jadi gk perlu diganti
if counter+1 != i
counter+=1
next
end
#kalau `i` belum pernah diganti, kita perlu
#tuker sama di `i+selisih` nya
temp = hasil[counter+selisih]
hasil[counter+selisih] = i
hasil[counter] = temp
counter+=1
}
return hasil
end
t = gets.to_i
t.times do |t_itr|
nk = gets.rstrip.split
angka = nk[0].to_i
selisih = nk[1].to_i
result = absolutePermutation angka, selisih
puts result.join " "
end
Bedanya dari source code yang pertama, do source code yang kedua ini tiap kita nemuin angka yang belum pernah dituker kita tuker dengan nilai sebanyak selisih nya. Biar lebih jelas coba liat contoh pembahasan pakai angka = 12 selisih 2
Code:
angka = 12
selisih = 2
counter = 0
hasil = [1,2,3,4,5,6,7,8,9,10,11,12]
ITERASI i : 1
temp = 3
hasil[0+2] = 1
hasil[0] = temp
counter = 1
hasil = [3,2,1,4,5,6,7,8,9,10,11,12]
ITERASI i : 2
temp = 4
hasil[1+2] = 2
hasil[1] = temp
counter = 2
hasil = [3,4,1,2,5,6,7,8,9,10,11,12]
## i = 1 karena diganti di iterasi sebelumnya
## coba liat `hasi` ke `3`
ITERASI i : 1
masuk if
counter = 3
## i = 2 karena diganti di iterasi sebelumnya
## coba liat `hasi` ke `4`
ITERASI i : 2
masuk if
counter = 4
ITERASI i : 5
temp = 7
hasil[4+2] = 5
hasil[4] = temp
counter = 5
hasil = [3,4,1,2,7,6,5,8,9,10,11,12]
ITERASI i : 6
temp = 8
hasil[5+2] = 6
hasil[5] = temp
counter = 6
hasil = [3,4,1,2,7,8,5,6,9,10,11,12]
ITERASI i : 5
masuk if
counter = 7
ITERASI i : 6
masuk if
counter = 8
ITERASI i : 9
temp 11
hasil[8+2] = 9
hasil[8] = temp
counter = 9
hasil = [3,4,1,2,7,8,5,6,11,10,9,12]
ITERASI i : 10
temp = 12
hasil[9+2] = 10
hasil[9] = temp
counter = 10
hasil = [3,4,1,2,7,8,5,6,11,12,9,10]
ITERASI i : 9
masuk if
counter = 11
ITERASI i : 10
masuk if
counter = 12
hasil akhir [3 4 1 2 7 8 5 6 11 12 9 10]
Source code yang kedua kita cuma pakai 1 looping dan gk pakai nyimpen-nyimpen di variabel lain, jadi lebih efisien.
Segini dulu buat sharing minggu ini, semoga penjelasan pakai contoh soal bisa bikin paham. Buat yang pengen tanya atau request sesuatu silakan colek opvllewat email hq.opvl@gmail.com atau lewat comment dibawah. Boleh juga mampir ke blog opvl di Absolute Permutation - Hackerrank. Moga bermanfaan.
Diubah oleh opvl 29-09-2019 16:48
nona212 dan 4 lainnya memberi reputasi
5
466
0
Guest
Tulis komentar menarik atau mention replykgpt untuk ngobrol seru
Guest
Tulis komentar menarik atau mention replykgpt untuk ngobrol seru
Komunitas Pilihan