Review Harta’s Challenge Balas


Kemaren malam saya mengikuti Harta’s Challenge di Z-Trening. Saya sangat senang sekali dengan hasil kompetisi ini karena saya berhasil melakukan NoMoreAC (No More Accepted) alias sapu bersih semua soal :D. Berikut adalah hasil ranking sampai 10 besar di Harta’s Challenge.

# User A B C Total Time
1. algoboy 100 100 100 300 1:49 (3)
2. stjepang 100 100 100 300 1:49 (9)
3. thocevar 100 100 100 300 3:00 (3)
4. syntax_error 100 92 100 292 3:34 (8)
5. pr0ton 40 88 100 228 0:53 (4)
6. AhmedKamel 40 88 100 228 3:55 (3)
7. Adamka 30 88 100 218 2:32 (8)
8. Amtrix 10 100 100 210 3:58 (6)
9. carlosjoa 100 100 200 1:16 (3)
10. hosam_samy 0 100 100 200 3:33 (7)

Soal-soal yang ada di Harta’s Challenge menurut saya cukup menarik, tapi sayang jumlah soalnya hanya ada 3.

Berikut pembahasan dari saya untuk masing2 soal:

[A] Sum it! ==> Dynamic Programming [EASY]

Diberikan 3 angka: A, B dan C. Hitung berapa banyak kemungkinan (modulo jawaban akhir dengan 1,000,000) kita bisa membentuk angka A tepat menggunakan B bilangan. Dan masing2 angka dari B bilangan yang kita gunakan minimal sebesar C.
Contoh:
A=9
B=3
C=2
Jawaban = 3, yaitu : {5 2 2}, {4 3 2} dan {3 3 3}.
{5 2 2}, {2 5 2}, dan {2 2 5} dianggap sama.
Constraint:
2<=A,C<=12000
1<=B<=1000

Hal pertama yang terpikirkan oleh saya adalah solusi Dynamic Programming O(1000 * 12000), karena solusi tersebut reasonable utk tembus time limit. Setelah berpikir beberapa saat, saya menemukan bahwa problem ini hanya modifikasi dari Integer Partition. Lalu saya melihat kalau Memory Limit di soal adalah 8 MB, karena itu saya tidak bisa menggunakan solusi DP TopDown. Satu2nya cara adalah menggunakan solusi DP BottomUp yang hanya pakai memory 2 * 12000. Beruntung di wikipedia sudah ada formula berikut:

  • p(k, n) = 0 if k > n
  • p(k, n) = 1 if k = n
  • p(k, n) = p(k+1, n) + p(k, nk) otherwise.

Tinggal saya rubah ke C++, kemudian testing2 terus submit langsung AC :D.

[B] K-th Sum ==> Simulation + Binary Search [MEDIUM]

Diberikan N angka, cari k-th sum dari setiap penjumlahan 2 bilangan dari N angka tersebut.

Contoh:

Input: N=3, k=4

angka2 = {1, 3, 4 }

Sum 1: 1+1=2
Sum 2: 1+3=4
Sum 3: 3+1=4
Sum 4: 1+4=5 (this is the desired answer)
Sum 5: 4+1=5
Sum 6: 3+3=6
Sum 7: 3+4=7
Sum 8: 4+3=7
Sum 9: 4+4=8

Constraint:

1<=N<=50.000 dan 1<=K<=N^2.

Masing2 angka dari N(0<=Ai<=40.000).

Hal pertama yang saya pikirkan ketika membaca soal ini adalah mencari pola, karena awalnya saya pikir ada pola penjumlahan yang mudah utk saya coding. Setelah berpikir 30 menit lebih menganalisa pola, saya memang menemukan polanya tapi sepertinya sangat sulit untuk di coding :(. Akhirnya saya menemukan cara lain, yaitu menggunakan binary search :D. Yang saya binary search adalah nilai jawaban (kita sebut ini X). Saya merubah  soalnya menjadi berikut: “Hitung ada berapa banyak pasang penjumlahan yang nilainya <= X”. Untuk menjawab pertanyaan itu kita bisa mensimulasikan prosesnya secara linier (nilai N maks 50,000). Jadi kompleksitas totalnya adalah O( N lg K ).

[C] Odd Divisor ==> Simple Math [VERY EASY]
Hitung penjumlahan semua angka antara A sampai B dimana angka tersebut memiliki jumlah pembagi yang ganjil.

Constraint: 1<=A,B<=10^9.

Soal ini sangat mudah sekali kalau kita tau bahwa hanya bilangan kuadrat yang memiliki jumlah pembagi ganjil. Karena itu kita tinggal looping dari X=1 sampai 40,000 (40,000^2 > 10^9). Jumlahkan X*X jika nilainya antara A dan B.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s