Pembahasan Soal Paste

Tanpa menganalisis soal ini secara hati-hati mungkin anda langsung berfikir perlunya suatu struktur data untuk menyimpan array untuk mencatat posisi baris-baris selama operasi-operasi itu dilakukan. Itu masih OK kalau N masih kecil. Kalau kebetulan dalam testcase digunakan N = 100000 maka anda akan menghadapi masalah memory untuk mengalokasi array sebesar itu.

Dengan membacanya dan menganalisisnya dengan lebih hati-hati maka anda akan menemukan kesederhanaan masalah ini.

Pertama, operasi cut-and-paste itu bersifat reversible. Artinya, dari hasil suatu operasi kita bisa cari asalnya sebelum operasi itu dilakukan. perhatikan contoh berikut ini (baris-baris ditulis ke kanan dengan pemisah tanda koma).

Misalnya sebelum operasi baris-baris berisi:
a, b, c, d, e, f, g, h, i, j
setelah operasi cut(4, 8),
maka akan dihasilkan baris-baris
a, b, c, i, j
dengan (d, e, f, g, h) di dalam 'buffer'. Setelah paste(2) dihasilkan baris-baris
a, b, d, e, f, g, h, c, i, j

Sekarang kita balikan (reversi) operasinya.

Operasi paste dilakukan setelah posisi ke 2. Jadi posisi-posisi 1 - 2 (yaitu a, b) setelah dan sebelum paste sama. Kemudian karena operasi cut dilakukan pada 5 baris maka sejak posisi ke 3 - 7 (yaitu d, e, f, g, h) adalah berasal dari hasil paste isi buffer. Dan, posisi ke 8 - 10 (yaitu c, i, j) mengalami pergeseran sebanyak 5 posisi ke kiri; jadi sebelum paste ada di posisi ke 3-5. Jadi sebelum paste adalah a, b, c, i, j. Sementara, d, e, f, g, ada di 'buffer'.

Operasi cut(4,8) tidak mempengaruhi posisi 1 - 3 karena dilakukan mulai baris ke 4. Berarti terjadi pergeseran baris ke 4 - 5 (yaitu i, j) sebanyak 5 posisi ke kanan. Di tengah dimasukan yang ada di buffer.

Secara umum jika ditanyakan berasal dari mana baris yang sekarang bernomor x sebelum operasi cut-and-paste (M, A, S). Berikut ini kita formulasikan perncarian harga z yaitu nomor baris dari baris x berasal. Maka, terdapat sejumlah kemungkinan kasus:

Reversi Paste mencari y dari x

• jika x <= S maka sebelum paste tetap, yaitu y = x
• jika x > (S+A-M+1) maka sebelum paste x mengalami pergeseran sebanyak (A-M+1) baris, yaitu y = x+A-M+1
• jika x > S and x <= (S+A-M+1) maka sebelum paste x ada di "buffer" pada posisi y' = x-S.

Reversi Cut mencari z dari y atau y' (di buffer)

• Jika ada di buffer (yaitu y') maka z = M + y'-1
• jika tidak ada dibuffer (yaitu y), maka
  • jika y < M maka sebelum cut tetap, yaitu z = y
  • jika y >= M maka sebelum cut ada di sebelah kanannya, yaitu di z = y+A-M+1

Nah, anda sekarang hanya perlu suatu array (berukuran 1000 x 3 integer) untuk menyimpan seluruh parameter operasi tsb dan sementara buffer' itu sebenarnya tidak ada! (Lho koq bisa??)