Scyther_07's blog

By Scyther_07, history, 5 months ago, In English

My code for this problem from Hacker Cup Round 2 is working just fine on Sample Input but its not giving any output on Validation Input.

My approach: First, find all possible candidates for an answer (the ones with frequencies more than the number of leaves). Apply a BFS starting from leaves, and then, for each "possible candidate/topic," I will compute DP(node, topic). The value of DP is 0 when a partition of the subtree node exists such that we need one "topic", 1 when a partition of the subtree node exists such that we need no "topic", and -1 if "topic" can't be the answer. The answer would be $$$\sum_{x \in topics} {(dp(1, x) == 1)}$$$

Code

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it