Nov 112014
 

H. Kawal Pemilu

Author: Felix Halim
Prepared By: Felix Halim, Ilham Winata Kurnia, Suhendry Effendy
(link to problem H)

As you might have noticed (above), this problem is proposed by one of the programmer behind kawalpemilu.org. He (implicitly) said that this problem is motivated by one question in QUORA asking about the custom in-memory database structure used by kawalpemilu. I guess the solution to this problem is the answer to that question.

The administrative divisions can be represented by a rooted tree, where the root is the national region. Each node X has a child Y iff Y lies within X region and their level differ by exactly 1. Implementation-wise, you don’t need to construct the tree; all you need is only the immediate parent information for each node (one parent for each node). Each node should keep the votes count on its region, such that when there is a query of the 2nd type, the answer can be obtained in O(1) – just retrieve the votes count (from an array, for example). When there is a query of the 1st type (incoming votes), you need to update the votes count from the node (village) to all its predecessors until the root. Notice that there are only 5 levels of administrative regions, thus the tree depth will also be 5.

There are 114 submissions have been made for this problem, in which 50 teams managed to get accepted. The first team who solve this problem is BerinGAS (minute 36) from University of Indonesia.


  27 Responses to “ACM-ICPC INC 2014”

  1. “One popular approach was by first sorting all the strings and pair each succesive string whenever possible”, kode saya spt itu, hanya saja pasangkan dr yg terpanjang http://ideone.com/PGjPAq

  2. komen untuk prob J

    β€œOne popular approach was by first sorting all the strings and pair each succesive string whenever possible”, kode saya spt itu, hanya saja pasangkan dr yg terpanjang http://ideone.com/PGjPAq

    • koreksi, prob G

    • Ngga, kode kamu nggak seperti itu. Approach kamu itu jadi sama dengan approach greedy yang bener (pasangin dari leaves) — string yang paling panjang saat itu pasti leaf.

      Yang dimaksud “pair each succesive string whenever possible” itu comparenya bener-bener cuma sama 1 string di sebelahnya aja (sorted); sedangkan kamu compare dengan yang panjangnya lebih pendek.

  3. a bit curious about problem H. Did you use the real Kawal Pemilu data for judge’s test case? πŸ˜€

  4. nice problem, nice editorial, pretty helpful, thx πŸ™‚

  5. saya penasaran dgn problem yg blm sempat saya kerjakan (dan AC), apakah mungkin akan diupload ke situs online judge ?

    saya dpt ide sederhana utk problem J dgn menelusuri apakah suatu nilai bisa jadi pivot (menjadi ‘L’), setelah itu cek apakah bs dr index tersebut menjadi good segment, jika tidak cetak impossible, kode saya : [[REMOVED]]

    thx koreksinya πŸ˜€

  6. How about ACM-ICPC 2014 Jakarta write up?? Will it be published?

  7. How can I get input data ?

    Thank you for sharing.

    • Ah… I didn’t notice this comment before >.< I'll not share the input data publicly. You can test your solution in some online-judges, e.g., tokilearning or joj. (I think) I have sent the test data to the admin on those sites.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)