Round 3 of the 2021 Facebook Hacker Cup is less than 48 hours away!
The round will begin on October 9th, 2021 at 10am PDT and will last for 3 hours. The contest can be found here.
You're eligible to compete in Round 3 if you were among the top 500 contestants in Round 2.
The top 200 contestants will win a Facebook Hacker Cup t-shirt with a "Top 200" badge, and the top 25 contestants will also advance to the Final Round, which will be hosted virtually and live streamed at www.facebook.com/hackercup later this year. Please note that all submission judgments will only be revealed after the round ends, and that time penalty will be used to break score ties. More details about rules and other information can be found in the FAQ.
We wish you the best of luck, and hope that you enjoy the contest!
Congrats all :-)
I solved C with complexity O(N)
I think my solution of C is O(N) tho, in particular I don't think you need to care the size of a subtree as long as its initial size is >= (K+1), as if we declare good node to be nodes that can be identified:
if the tree has no further "good" node, we can keep all the initial node
if the tree has good node, the subtree of good node already has >= (K+1) nodes
Wanna cry so much for being #29, esp. I questioned so much about my O(N) approach.
My solution is the same.
Tourist delaying his submission of C to win by 46 seconds is excellent
Problem D requires the following query-on-a-tree subroutine:
This can be solved without HLD-like stuff. Compute the Euler tour of the tree (of length $$$2N$$$). Every node is now associated with two positions denoting the time visiting in / out the node. If the color of the node is white, mark
(and)to that two positions.The answer for the problem is the number of occurrences of
()in the Euler tour when black nodes are ignored. This quantity can be maintained withstd::set.This is very cool! I also didn't write HLD-like stuff, but it was still $$$O(\log^2)$$$ (binary jumps + Fenwick over euler order).