Marcadian’s Blog

Bina Nusantara Programming Contest (BNPC-HS) Final Round
Problem E Lining Up

Ini soal gua yang buat (writeup mesti paling panjang) hehehe… intinya adalah dikasih inverse lalu temukan sequence aslinya. Inversi adalah banyaknya angka di sebelah kanan suatu posisi I, yang nilainya lebih besar dari nilai di posisi I, jadi untuk sequence a1..an yang merupakan permutasi dari 1..N, misalnya sequence 3 4 2 1 inversinya adalah 2 2 1 0,

2 angka dikanan angka 3 yang lebih kecil 3,

2 angka dikanan angka 4 yang lebih kecil 4,

1 angka dikanan angka 2 yang lebih kecil 2

0 angka dikanan angka 1 yang lebih kecil 1

Untuk mencari sequence aslinya, kita harus mengetahui K-th element dari suatu set angka, misalnya set angka kita adalah {2,3,4,1} dan di beri inverse 3, maka artinya ada 3 angka di kanan yang akan lebih kecil dari angka sekarang, maka angka sekarang adalah 4. Untuk menyelesaikan soal ini cukup dengan looping 2 tingkat. Ada beberapa cara untuk menyelesaikan soal ini.

Cara pertama adalah kita membuat seperti insertion sort, tiap step langsung print angka lalu geser. Mis a[i] adalah angka pada rank ke-i

Misalnya inversi kita adalah 2 2 1 0

untuk source nya bisa diliat disini, well karena wordpress gratisan ini hanya bisa .doc kalo ga bisa dibuka, ubah aja extension nya ke .txt

a[1] | a[2] | a[3] | a[4]

1 | 2 | 3 | 4

ada 2 angka yg lebih kecil, maka ada print a[3] yaitu 3,

setelah angka 3 dibuang dari set, maka rank setiap angka berkurang 1 menjadi

a[1] | a[2] | a[3] | a[4]

1 | 2 | 4 |

ada 0 angka yg lebih kecil, maka print a[3] yaitu 4

setelah angka 4 dibuang dari set, maka rank setiap angka berkurang 1 menjadi

a[1] | a[2] | a[3] | a[4]

1 | 2

ada 1 angka yang lebih kecil, maka print a[2] yaitu 2

a[1] | a[2] | a[3] | a[4]

1

ada 0 angka yang lebih kecil maka print a[1] yaitu 1

Cara lain adalah sbb

Mis: a[i] adalah inverse dari angka i maka pada saat awal, a[i] = i-1

a[1] | a[2] | a[3] | a[4]

0 | 1 | 2 | 3

mis inversi kita 2 2 1 0,

cari angka yang memiliki inversi 2 yaitu 3, print 3 jika kita sudah membuang suatu angka dari suatu set, maka inversi dari semua angka yang lebih besar pasti berkurang 1. Mis jika kita membuang angka 1, maka inverse dari 2,3,4 pasti berkurang 1.Agar angka yang sudah dibuang tidak terambil maka kita beri suatu nilai yang tidak mungkin misalnya -1. Maka sequence kita menjadi

a[1] | a[2] | a[3] | a[4]

0 | 1 | -1 | 2

cari angka yang memiliki inversi 2 yaitu 4

a[1] | a[2] | a[3] | a[4]

0 | 1 | -1 | -1

cari angka yang memiliki inverse 1 yaitu 2

a[1] | a[2] | a[3] | a[4]

0 | -1 | -1 | -1

cari angka dengan inverse 0, yaitu 1

Solusi gua pake cara yang ini.well solusi yang gua bikin masih ke stdin stdout kalo mau ke file urus ndiri ya, di pascal sebelom read(t) tambahin

Assign(input,’line.in’);

Reset(input);

Assign(output,’line.out’);

Rewrite(output);

Jangan lupa sebelom end kasih

close(input);

close(output);

bahasa c sebelom baca cukup tambah

freopen(“line.in”,”r”,stdin);

freopen(“line.out”,”w”,stdout);

Ada cara laen yang lebih canggih yaitu N log N, menggunakan sebuah tree, karena gat au namanya dan dibuat misof (yg maen uva ma topcoder pasti tau ) timo namain ini misof tree. ( ditulis nanti aja kapan2 hehehehe)