LoneFox's blog

Facebook Hacker Cup 2020: Final Round
By LoneFox, history, 4 years ago, In English

The finals of the 2020 Facebook Hacker Cup are less than 48 hours away!

On Sat. Dec. 5th at 6:30 — 10:30am PT, our 25 finalists will compete in our first all-virtual finals for the grand prize of $20,000 USD and title of Hacker Cup champion!

You can follow along with the scoreboard and contest problems here.

After the conclusion of the contest, at 11:00am PT, the results will be revealed in a live stream on the Hacker Cup Facebook page!

The Facebook post can be found here.

Update: The round has ended; congratulations to the finalists! The result reveal video can be found here, and the solutions here.

Update: Screencasts are available from Andrew He (ecnerwala) and Neal Wu.

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

Comments Comments (36)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Sorry

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -32 Vote: I do not like it

    I am super surprised no one is from India as most of contestants on Codeforces are from India.

    Why are there downvotes on this?

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

      On Codeforces, not so many rounds are won by Indians too.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it -39 Vote: I do not like it

        [Deleted]

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

          I don't know who's taking it personally, but probably Gennady is very sad because of your comment, especially earning 1250$ every month only by winning Code Jams since he was 19.

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

          I believe Radewoosh is right on this one. He's simply stating a fact. In India, competitive programming isn't considered a sport, it's considered a job requirement. There's nothing wrong with it given that India is a highly populous country and competitive programming is actually required by a lot of companies. Besides, I also think that we do well in chess and that's because the reasons for pursuing chess by any of our players is purely passion and curiosity, and nothing less.

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

            Yeah, I agree that India is a very strong country if it comes to IT. If it comes to CP it's mostly considered as a job requirement, which is OK ofc, but India also has Codechef, which is one of the most known CP websites and is getting better and better nowadays. If it comes to the people who are getting to FHC finals it's mostly about personal motivation, I'm not exactly sure where is it getting from. The only sad thing about India is that every time I write something about this country, there are some people who take it as an attack xd There are no LGMs from India (today) and no really strong Indian competitive programmer comes to my mind, so why be surprised by no finalists.

            → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Dude, he is just being condescending, ignore such comments.

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

        Oh I see it now, best of luck for the finals.

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

    We'll have a livestream for the results, but we won't have a livestream during the contest (though there'll be a live scoreboard as always).

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Congrats on getting red LoneFox again!!

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

Will Radewoosh's 43s-before-the-end-of-the-contest submission be the winning submission?

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

    Well, at least we know that Errichto knows how to become top2 in last 5 minutes

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

      (mostly thanks to the last geometry)

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

      Ah, I forgot about this. Well, it was 3:59:18, so the submission was at the last minute as well.

      And today he submitted problem F at 3h57m and currently 2nd. Interesting.

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

    The submission is incorrect. Congratulation tourist for winning another Facebook Hacker Cup!

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

    We both tried some random heuristics to find best independent set in a graph. I even used multi-threading but that wasn't enough.

    It would be quite bad to win thanks to weak tests though.

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

    Yesterday Errichto told us that his plan is to win this by pushing through some stupid brute/heuristic solution to the hardest problem. At least he stood by his promise

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://fb.watch/2bAGSwUBa2/

The Final Results

Update 1 : Gennady Won

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

Congrats tourist

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

F for radewoosh.

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

Gennady gotta gennady.

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

It's a pity that I spent over an hour debugging B (the logic was ultimately correct, but I wrongly constructed the tree), and it cost me the time to implement D. Aside from whining, I'd like to brag that I'm the only one to solve F. Here's my code.

And last but not least, I'd like to thank the organizers. I'm already looking forward to next FHC!

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

From next FHC, just take top 24 in the final round because we all know whos gonna be in the first place :)

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

I uploaded my screencast at https://youtu.be/W6UWY1xoXbU if anyone wants to see. Congrats to tourist for winning!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    did you try to solve F after the contest?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried, but didn't figure out the solution until I discussed it with ksun48. I'll probably try coding it on stream today.

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

I always appreciate the FBHC team for delivering such a great event! Here is my contest postmortem.

  • A: It is a "Yet another Pareto front problem". It took me about 12 minutes even though I just copypasted JOI2012 Spring Camp Fish. Since I lost top-5 by 20 minutes or so, maybe I had to be more confident for codes written by me 6 years ago. But ofc it's just a postmortem. Maybe it's a good subject for library codes :)
  • B: It is a "Yet another complicated tree DP problem". Considering my lack of confidence I think I did quite well (30 minutes), but Petr's 12 minutes seems infeasible to me. Amazing!
  • C: So there are two ideas involved: First is you can check the feasibility only by considering the partial sum of all fallen drops, so you don't have to actually move the drops. Second is that the expected time is just a sum of probability which the frog could survive until time $$$i$$$. Second idea really combines well with the first idea, which is very nice. I came up the first idea quite quickly, but somehow it was really hard to convert this to actual calculation, which (again as a postmortem) it seems natural to come up with the second idea quickly.
  • D: Like AB, D is quite easy idea-wise, all I had to do is some implementation. But you know, it always feels so good to write yet another boring segment tree.
  • E: For a fixed segment the answer is some complicated formula concerning the # of consecutive ones in prefix, number of ones, number of zeroes. The formula involves floored $$$log_2$$$ or stuffs so it seemed like a tough one. I started from $$$O(N^2 \log N)$$$, and then I divided the cases, precalculated some functions, change the inequality, and repeated, which finished in 5 minutes before the contest. I really have a lot of cases and it wasn't a pleasant experience for me, but 300iq said that case-bashing is not necessary as long as you have that complicated formula.
  • F: I only realized that it was a generalization of circular-arc graphs and trapezoid graphs after the contest :) If I noticed it then I would've tried, so maybe I was lucky to not know. We can google the paper about "Circle trapezoid graph", which describes the reduction to $$$O(N)$$$ clique computation in trapezoid graph. I suspect maroonrk's solution is similar to the paper's one. ksun48 told me about the different reduction to clique in circular-arc graph. F looks like the most intriguing problem of all, I will try to upsolve it. Thanks to the author!
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Second is that the expected time is just a sum of probability which the frog could survive until time i.

    Could somebody explain why this is the case? In the editorial they simply say "The answer may then be computed as $$$\sum(S_{0..C_N})$$$" but they don't explain why.

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

      Let $$$p_i$$$ be the probability that the process won't end for at least $$$i$$$ iterations.

      Then if you sum up $$$p_1 + p_2 + \ldots$$$, the probability of the way that ends in exactly $$$i$$$ seconds will be counted exactly $$$i$$$ times. So you will derive the expected value.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        Ah yes because $$$p_i = \sum_{j = i}^{C_N} p'_{j}$$$ where $$$p'_j$$$ is the probability that the process ends exactly at iteration j. Therefore it is counted exactly i times for each $$$p_i$$$ when you sum them. Thanks for explaining!

        → Reply