Блог пользователя LoneFox

Автор LoneFox, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +115
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

Sorry

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -32 Проголосовать: не нравится

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

    Why are there downvotes on this?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +95 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится -39 Проголосовать: не нравится

        [Deleted]

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +26 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Congrats on getting red LoneFox again!!

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +51 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

https://fb.watch/2bAGSwUBa2/

The Final Results

Update 1 : Gennady Won

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Congrats tourist

»
4 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

F for radewoosh.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Gennady gotta gennady.

»
4 года назад, # |
  Проголосовать: нравится +186 Проголосовать: не нравится

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!

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

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!
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

        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!