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)

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.

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.

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

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.