LoneFox's blog

By LoneFox, history, 6 weeks 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

»
6 weeks ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

Sorry

  • »
    »
    6 weeks 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?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +95 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 3   Vote: I like it -39 Vote: I do not like it

        [Deleted]

        • »
          »
          »
          »
          »
          6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks 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.

          • »
            »
            »
            »
            »
            »
            6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    6 weeks 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).

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Congrats on getting red LoneFox again!!

»
6 weeks 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?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      (mostly thanks to the last geometry)

    • »
      »
      »
      6 weeks 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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

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

  • »
    »
    6 weeks 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.

  • »
    »
    6 weeks 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

»
6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Congrats tourist

»
6 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

F for radewoosh.

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Gennady gotta gennady.

»
6 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it
This Smile Is Priceless
»
6 weeks 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!

»
6 weeks 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 :)

»
6 weeks 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!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    did you try to solve F after the contest?

    • »
      »
      »
      6 weeks 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.

»
6 weeks 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!
  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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!