### LoneFox's blog

By LoneFox, history, 6 weeks ago,

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  » 6 weeks ago, # | ← Rev. 2 → +14 Sorry •  » » 6 weeks ago, # ^ | ← 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? •  » » » 6 weeks ago, # ^ | +95 On Codeforces, not so many rounds are won by Indians too. •  » » » » 6 weeks ago, # ^ | ← Rev. 3 → -39 [Deleted] •  » » » » » 6 weeks ago, # ^ | +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.
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   -31 .
•  » » » » » 6 weeks ago, # ^ |   +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.
•  » » » » » » 6 weeks ago, # ^ |   +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.
•  » » » » » » » 6 weeks ago, # ^ |   -9 Future LGM- Everule
•  » » » » » 6 weeks ago, # ^ |   0 Dude, he is just being condescending, ignore such comments.
•  » » » » 6 weeks ago, # ^ |   +10 Oh I see it now, best of luck for the finals.
•  » » 6 weeks ago, # ^ |   +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).
 » 6 weeks ago, # | ← Rev. 2 →   0 Congrats on getting red LoneFox again!!
•  » » 6 weeks ago, # ^ |   +15 He first became red 5 years ago.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +30 Hence the “again” :)... ah, trolled by edit once again XD
 » 6 weeks ago, # | ← Rev. 3 →   +51 Will Radewoosh's 43s-before-the-end-of-the-contest submission be the winning submission?
•  » » 6 weeks ago, # ^ |   +11 Well, at least we know that Errichto knows how to become top2 in last 5 minutes
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 (mostly thanks to the last geometry)
•  » » » 6 weeks ago, # ^ |   +4 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, # ^ |   +39 The submission is incorrect. Congratulation tourist for winning another Facebook Hacker Cup!
•  » » 6 weeks ago, # ^ |   +49 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, # ^ |   +109 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 →   0 https://fb.watch/2bAGSwUBa2/The Final ResultsUpdate 1 : Gennady Won
 » 6 weeks ago, # |   +8 Congrats tourist
•  » » 6 weeks ago, # ^ |   +31 congrats to all top 25 finalist!
 » 6 weeks ago, # |   +20 F for radewoosh.
•  » » 6 weeks ago, # ^ |   -6 vc unko;I guess even LGMs do this sometimes, on FHC Finals nonetheless xDGratz on the solve tho
 » 6 weeks ago, # |   +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!
•  » » 3 weeks ago, # ^ | ← 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.
•  » » » 3 weeks ago, # ^ |   +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.
•  » » » » 3 weeks ago, # ^ | ← 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!