LoneFox's blog

Facebook Hacker Cup 2021: Round 3
By LoneFox, history, 3 years ago, In English

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!

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

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Congrats all :-)

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I solved C with complexity O(N)

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Tourist delaying his submission of C to win by 46 seconds is excellent

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +66 Vote: I do not like it

Problem D requires the following query-on-a-tree subroutine:

  • Color the node to black or white
  • Find the set of white nodes without white descendants

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 with std::set.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    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).

    → Reply