Final JOINTS 2010

Jogja Information Technology Session (JOINTS) – Programming Competition Session (PCS), Universitas Gajah Mada, 11 April 2010

problemset dan solusi sudah diupload.

detailed scoreboard [thanks Vilberto]

EDIT : Pembahasan Soal D.

Soal E, Bilangan

ada dua kemungkinan :

  • bila angka terurut menurun, maka angka 0 harus ditambahkan (tambah digit). urutkan menaik, lalu sisipkan angka 0 di posisi kedua paling depan.
  • bila angka tidak terurut menurun, cari pasangan i, j paling kanan di mana i <= j dan digit[j] < digit[i]. tukarkan. //setelah contest nyadar, mestinya bisa di next_permutation aja sih di C++.

ini soal termudah di contest kali ini – setelah submit sekali, ngga nemu perubahan yang perlu sampe akhir contest. tapi ironisnya nilai saya 0, compile error katanya πŸ˜› nilai saya : 0 (CE)

Soal C, Kayu

lihat Huffman Coding. ga pake mikir langsung koding :p pas debug beberapa jam kemudian, nyadar kalo ada bug kecil yang bs ngancurin seluruh kode. nilai saya : 100

Soal A, Lemari

menggunakan dynamic programming tiga dimensi yang cukup straight-forward, dengan state [depth – tinggi laci yang mau diselesaikan, dari atas] [ jumlah laci yang yang terkunci ] [ boolean, apakah laci tepat di atas yang sekarang terkunci atau tidak ]

fungsi rekursinya :

bila (last = true) atau (depth = teratas), dp[depth][safe][last] = dp[depth+1][safe+1][true]+dp[depth+1][safe][false];

else, dp[depth][safe][last] = dp[depth+1][safe][true]+dp[depth+1][safe][false];

ada tiga versi kode ini yang gw submit. versi pertama pure rekursif dan DP, versi kedua pruning / optimasi rekursif, versi ketiga ganti printf jadi cout, karena output long long di printf rada bahaya kalo ga tau jelas compiler jurinya.

nilai saya : 100

Soal B : Pesan

pikiran naluriah yang pertama adalah bikin algo Longest Common Subsequence diulang berkali2. tapi cepet ketemu counter casenya. Β solusinya sih… hajar rekursif, kasih tabel DP =)) kalo kata Riza, namanya multiple dimension LCS. baru tau juga.

intinya, tabel DPnya punya empat dimensi [posisi string 0][posisi string 1][posisi string 2][posisi string 3], dengan nilai string hasil. untuk setiap state, ada 2 kemungkinan:

  • s[0][pos0] termasuk di dalam string hasil. maka kita harus mencari dp[pos0+1][p1+1][p2+1][p3+1]. p1, p2, p3 adalah indeks occurence pertama yang <= posisi string 1/2/3 di mana karakternya sama dengan s[0][pos0]. hasil : s[0][pos0]+dp[pos0+1][p1+1][p2+1][p3+1].
  • s[0][pos0] tidak ada dalam string hasil, maka kita harus pencari dp[pos0+1][pos1][pos2][pos3].

bandingkan kedua hasil, yang mana yang lebih baik, masukkan ke dalam dp[pos0][pos1][pos2][pos3]. hasil ada di dp[0][0][0][0].

ada 4 versi yang gw buat:

  1. rekursif dengan inner rekursif berdepth 3.
  2. coba pruning dikit.
  3. nyadar kalo ngga perlu ada inner rekursif, rewrite.
  4. ada kurang inisialisasi di rekursif, bisa membuat salah untuk hasil panjang pesan < 2.

nilai saya : 100.

Soal D : Pesta

soal yang gw nggak solve, ga bs ketemu kompleksitas yang lebih bagus. cuma bisa ngurangin dari n^3 jadi n^2 log n (kayaknya sih, ga gt bisa ngitung kompleksitas priority queue). bingung juga jelasinnya, silakan liat kodenya di halaman Solusi πŸ˜› gw sempet nyoba worst casenya di contest time dan ud keliatan bgt ga bkl lewat.

nilai saya : 40 (ternyata masih paling tinggi di soal ini :P)

EDIT : ini soal Google Code Jam 2008. Pembahasan bisa dilihat di sini. thanks Ashar for the input!

================================================

total 340 dari 500. agak kecewa dengan soal Enya sih.rank 2 dari SMAK 1 Penabur Bandung, 270, rank 3 dari Ipeka International, 220 kalo ga salah.

personal background:

tadinya bener2 ga berencana buat ikut JOINTS, tapi ternyata tanggalnya persis banget sama kondangan sodara sehari sebelumnya. lol emg harus ke Jogja, jadi ya sekalian πŸ˜›

general comments gw buat problemset JOINTS:

  • buat gw problemsetnya menarik dan cukup menantang, significantly lebih sulit dari soal JOINTS 2 tahun lalu, tapi juga nggak sulit-dan-tidak-menarik kayak UnPar.
  • sayangnya, soal termudah di contest ini (soal E) nggak cukup gratisan, akibatnya hampir setengah peserta dapet nilai 0 (dengan bodohnya saya compile error di soal ini lol).
  • secara persebaran juga perlu dibenahi, karena tadi ada 2 soal DP, 1 greedy, 1 ad hoc, dan 1 yang gw ngga perfectly solve. graph nggak ada :(( *gw rada bias sih :P*
  • ngga make algo yang aneh2, yang nearly mustahil untuk dipikir sendiri, kayak Strongly Connected Component di Unpar.
  • semua soal terbuka untuk mengemis nilai parsial.
  • menarik, tiga national contests yang besar (JOINTS, BNPCHS-Binus, Unpar) tingkat kesulitan soalnya naik cukup jauh dari tahun 2008. ini kerasa banget terutama untuk JOINTS dan UnPar, karena gw skip ngga ikut tahun 2009nya.

all in all, ini last contest gw sebagai siswi SMAK 1 Jakarta, akhir dari perjalanan competitive programming gw selama beberapa tahun ke belakang. gw senang dan bangga karena bisa menutup bagian hidup gw yang ini dengan catatan yang patut gw banggakan πŸ™‚

Advertisements

16 Responses to Final JOINTS 2010

  1. Andrianto S.G says:

    hue…. selamat ya ….. jd the winner nd Joints 2010…
    Saya perlu blajar banyak dr cece….. Tolong di bantu ya….. hehe

    • Angelina Veni says:

      thanks:) iya, feel free to ask ya kalo perlu apa2… kamu ud punya guru2 yg oke banget di malang, belajar banyaklah dari mereka πŸ™‚

  2. gabriel says:

    Yah, cici veni, kokn galak amat… piala bergilirnya melayang dh… ha9 tapi ga papa lah, tetep kembali ke BPK PENABUR lagi. πŸ˜€

    • Angelina Veni says:

      apanya galak, bedanya sedikit gitu =)) iya, tahun depan bisa diboyong SMAK 1 Cirebon lagi gab πŸ™‚

  3. Andrianto S.G says:

    OK ce…. makasi banyak….
    aku akan belajar lebih lgi da…… wkwkwk

    Oya.. aku blh minta no nya cece g ????
    Biar kalau bth2 g perlu open PC…. hehe
    Kirim ke dyuree@gmail.com aja… itu email q….

    Makasi banyak y….

  4. riza_on says:

    Soal B solusinya pake array satu dimensi lho ven :p
    Awalnya emang tujuannya bikin jebakan koding repot sih, tapi memang gak mempan kalo dikasih ama kamu (doh)

    Soal tahun ini udah diturunin lho kesulitannya, gara2 dikritik peserta tahun lalu.
    JOINTS 2009 (yg kamu skip itu) Juara 1 nya dapet nilai 200an dari 500. Kita selipin Maxflow buat ngerem anak2 TOKI (termasuk kamu :p ), eh malah kamu batal ikut, hehehe…

    • Angelina Veni says:

      yah mendingan maxflow daripada soal pesta yg kemarin kak haha saya suka graph abisnya πŸ˜› hmm kalo bener2 diturunin tahun lalu brarti susah bgt dong haha palagi kalo target participantsnya pra OSN…

      wow mantep banget kak DP 1 dimensi, kyk gimana tuh? ga kepikiran sama sekali πŸ˜• apa main biner dp bitmask gitu kah?

    • riza_on says:

      nggak sih, sama aja kaya n dimensi,
      cuma diakalin indexingnya biar gampang, hehehe… :p

  5. tracy says:

    ci veni!!!!
    betapa bodohnya saya !!!
    😦

  6. Wilbert says:

    Soal A gw pernah liat di UVa.. πŸ˜€
    IMHO.. hohoho..

    Congratz deh! πŸ˜€

  7. Felix J says:

    soal E yang score lu “0” gara2 CE itu, soal GCJ 2009, Round 1B, Problem B :p~
    btw, CE napa lu? ironis banget soal termudah “0”, soal-soal yang bukan termudah nilainya bisa 100 3 biji :p

    • Angelina Veni says:

      o.O padahal gw GCJ 2009 itu Round 1B juga loh ikutnya! ckckck gw gampang lupa soal2 yg gw pernah buat hahaha. kayaknya lupa include apa gitu deh. kalo di Dev C++ kan ga kedetect tuh kalo lupa include kadang2.

      haha hooh lix, gw hoki lah masi bs #1 pdhl salah fatal gitu.

      • Felix J says:

        ckckckckck… meninggalkan peringkat 2 dengan skor terpaut Jauh gitu, tuh hoQ ven? :p~ anw, congrats buat 2009-2010 lu yang superb achievementsnya πŸ˜€ Gud luck buat stanford nya πŸ™‚

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: