Nov 112014
 

F. Truth and Lies

Author: Suhendry Effendy
Prepared By: Suhendry Effendy, Felix Halim
(link to problem F)

Abridged problem statement: given a rooted tree of N (≤ 10,000) nodes where each node has a value (0 or 1), determine the minimum number of nodes which value should be changed (from 0 to 1 or viceversa) such that there is no parent-child pair where the parent’s value is 1 while the child’s value is 0.

This problem can be solved either by dynamic programming or recursive method.

The dynamic programming state would be dp[node][value], where node is the current node, and value is the value of current node’s parent. If value is 1, then current node’s value should also be 1 (change it if it’s not); otherwise it can be either 0 or 1.

This problem can also be solved by simple recursion (which I used). Notice that if a node has a value of 1, then all of its successor’s value (its subtree) should also be 1. Using this fact, we can device an algorithm to solve the problem: recurse and ask each node whether it’s better if it turns its value into 0 (in which, recurse to its children), or simply turn its value and all its successors into 1 (don’t need to recurse). Note that the second option (turning into 1) requires the information on how many nodes are there in its substree which value are 0 – this can be answered by another recursion in O(N) for all nodes, store all answers in an array.

There are 110 submissions have been made for this problem, in which 33 teams managed to get accepted. The first team who solve this problem is UMN-Alpha (minute 21) from Universitas Multimedia Nusantara.


  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)