Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Problem C : Meta Hacker Cup Round 2

Revision en1, by Scyther_07, 2023-10-23 09:52:13

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 xtopics(dp(1,x)==1)

Code
Tags hackercup, trees, dp, bfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Scyther_07 2023-10-23 09:52:13 4333 Initial revision (published)