LoneFox's blog

By LoneFox, history, 4 years ago, In English

Round 2 of the 2020 Facebook Hacker Cup is less than 48 hours away!

The round will begin on August 29th, 2020 at 10am PDT and will last for 3 hours. The contest can be found here.

You're eligible to compete in Round 2 if you scored at least 25 points in Round 1.

Everyone who solves at least one problem will receive a Facebook Hacker Cup t-shirt, and shirts for the top 200 contestants will include a “Top 200” badge! We'll begin shipping out t-shirts by early 2021 or earlier, at which point the winners will receive emails with tracking information.

The top 200 contestants will also advance to Round 3, taking place on Sept. 12th. Please note that all submission judgments will only be revealed after the round end, 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!

The Facebook post can be found here.


Update: The round has ended, thank you for participating! The scoreboard can be found here, and the solutions here.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to increase stack size in windows 10? (I am using c++ in sublime text 3)

Was solving https://www.facebook.com/codingcompetitions/hacker-cup/2018/round-2/problems/B

I used g++ -Wl,--stack,268435456 -o setup.exe setup.cpp in command prompt

But still this error pops up:

terminate called after throwing an instance of 'std::ios_base::failure' what(): basic_filebuf::underflow error reading the file

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

    You can find some information regarding increasing the stack size here, and more generally on the internet. Though it's worth noting that it's not obvious that your error is a result of your stack size.

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

      yes got it done, i don't know what was the problem in Windows, but in Ubuntu, I added ulimit -s unlimited inside sublime build, then it was fine.

      Thanks

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. LoneFox Can you please share the file size for each problem? It'll help me decide if I'm going to use file I/O and what I should prepare for.

  2. Will the input have the exact same formula as last time (or if there is a new formula, is it possible for you to share it with us)? I'll template, if possible, as the last thing I want to be debugging is input reading.

Thanks!

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

    We'll keep the size of each input file under 8MB (generally much smaller), and some problems will feature expressions for input generation similar (not necessarily identical) to those present in Round 1.

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

      But why keep changing the input method?

      I assumed the input method would be the same as round 1 (on the premise that you'd want competitors to spend their time solving problems and not dealing with input idiosyncrasies), only to be met with an extremely subtle and completely unannounced change, forcing me to debug for 10 minutes. In a competition where penalty is sum of times, this was extremely costly.

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

        Problems may have different requirements for how to reasonably generate input for them.

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

          Not the case here. The shift from 1-indexing to 0-indexing from round 1 to round 2 was unnecessary -- I don't see how having tables with 0 people changes problem A in any way.

          And for the different modulos in problem C, you could have simply supplied the modulos in the input file, and then we would have been able to read all input arrays with the same code.

»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

As a tester, I very much enjoyed the problems. GLHF to everyone competing!

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

shirts for the top 200 contestants will include a “Top 200” badge!

That's a pretty cool idea NGL, my only concern being that now it looks less cool to laymen since they'd imagine there's less than 200 ppl with this shirt.

»
4 years ago, # |
Rev. 2   Vote: I like it +155 Vote: I do not like it

Asian coders starting their round at midnight be like:

Nothing's gonna stop me from going straight to bed after 1AC

»
4 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

If someone solves only a subtask, can he get a tshirt?

Assuming subtasks exist

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

    There are no subtasks or partial marks per problem.

»
4 years ago, # |
Rev. 2   Vote: I like it +50 Vote: I do not like it

Input format is so disgusting(except second problem), statements are so long and hard to understand, problems(at least first 2, that I read) are so boring, so I decided not to participate in this round.

I hoped that the problems would be somehow more interesting than in round 1 and qualification round, but I was wrong.

Very upset and demotivated.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can't I see Petr, Gennady or Mikhail in the standings? Are they already advancing to the finals?

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

I wonder if Tourist, Petr, Errichto, neal and ksun are not submitting just because they know something that people who have completed the set don't? Like, they're thinking about something bigger

Also, ecnerwala made his final submission first, and yet he is shown to be behind Benq Can anyone clarify how are rankings calculated?

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

Penalty as sum of times is stupid.

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

    Why? ICPC does the same thing

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

      But ICPC is a team competition and in my opinion that mitigates some problems that arise compared to individual competition. I agree that sum of times is stupid for individual. You have no way of catching up if you were 5 mins slower on first two problems.

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

      I think it's different because:

      • ICPC has a lot more problems; you don't expect to have solved all problems when the time ends; a problem set is (in my opinion) bad for a contest, if there are at least two teams that have solved all problems
      • ICPC has a penalty for wrong submissions (which, to be fair, I'm not sure it even exists in FHC; if it does, then it's definitely redundant);
      • in ICPC there are three teams, which hedges the risk of potentially solving the easiest problem 5 minutes after other people; in FHC it's devastating to spend 10 minutes instead of 5 minutes on A, because you effectively "lose" 20 minutes of penalty on D;
      • in ICPC you aren't allowed with pre-written code; here, it makes all the difference in top 80; I'm not saying that in other contest it doesn't, but that here it's much too significant;
      • ICPC problem statements don't have a convoluted input parsing scheme.

      Overall I think the ICPC experience is incomparable with this contest, and I've never had the experience of finishing an ICPC contest in 100 minutes without any wrong submissions just to wait for another 30 minutes for people to surpass me, with literally nothing to do but blame myself for not having pre-written templates and triple-checking the input parsing. It might sound arrogant, but I'm sure I'm not the only one in this situation, to feel like the contest was very poorly thought through, with this penalty system.

»
4 years ago, # |
  Vote: I like it -39 Vote: I do not like it

I hope you have good plagiarism detector because i participated in this contest lolololo...

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

    This was funny 6 months ago.

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

      You gave him the attention he desperately wanted to get. Better to completely avoid such comments, he will surely get bored and leave it. XD

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

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

The input format is getting more and more ridiculous (eg Problem C).

Suggestion: Provide an optional helper script that converts the downloaded input into a larger file with the decoded input. This would be similar to how GCJ provides a helper script for interactive problems see here.

This would simplify the input processing for everyone, and still keep the downloaded file size under control.

LoneFox SecondThread

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

    Thank you for the suggestion! We'll certainly consider alternatives such as scripts or encrypted zip files (at least for next year), bearing in mind that the addition of an extra step in the process and interaction with different software may add a different sort of confusion/complexity for competitors.

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

      It was common in IPSC to give a python script to generate the input, and removing all the hassle from contestants. Also an encrypted zip file looks good too!

      I think any of these strategies will improve the UX, and any new process/interaction/software will be easily learnt by contestants in a 72 hours qualification round.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? I couldn't even solve an easier version where $$$h[ p[i] ] > h[i]$$$.

»
4 years ago, # |
Rev. 5   Vote: I like it +236 Vote: I do not like it

First time, in many years of competitive programming, that I boredom-quit a contest.

Problems B and C were already not the best, but problem D is on the highest level of boredom! What is the point of giving a problem about known techniques that is hard because:

  1. The said techniques are implementation-heavy.
  2. Everything is on a tree to make everything harder.
  3. The input is in an awful format.

A contestant who does not know the technique will never solve such a problem. A contestant who knows the technique reads the problem, sees the solution in half a minute, and then spends half-an-hour wondering what he did wrong in his life to deserve this...

To FHC organizers: Please find some better problem-setters/testers (maybe outside facebook). You are organizing one of the most important contests in competitive programming (and, I guess, you have a budget that is way bigger than the usual atcoder/codeforces contest). Don't waste this opportunity.

p.s. I agree with the replies that B, C were not "bad problems". I did not want to say that they are bad, just that they are not good enough to make me forget about D.

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

    My solution for D was parsing the input, copy-pasting the code from https://codeforces.net/blog/entry/51275, and a nice and short actual solution that uses that data structure. So it was at least possible to solve D without implementation-heavy techniques (assuming copy-pasting the above data structure is not counted as such).

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

      So copy-pasting data structures makes problems fun?

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

        :) I did not say that this problem was fun, I said that it was possible to avoid heavy implementation.

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

      May I know which implementation did you use? I had issues with swapping objects using this implementation.

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

        I've actually used two, and added asserts that they return the same outputs: https://codeforces.net/blog/entry/51275?#comment-351410 and https://codeforces.net/blog/entry/11155?#comment-539199

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

        I had the same issue with the same implementation (as of now I don't know why). I fixed this by avoiding swaps on the structure and instead storing id[u] — the index of the structure used by node $$$u$$$. Then I can simply swap two numbers — swap(id[u], id[v]).

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

          Let me know if you figure out the issue, I will investigate myself.

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

            I didn't use this implementation, but I see one suspicious thing in it: the lambda at line 30 implicitly captures this, which is used by the call to end().

            When the contents of two HullDynamic are swapped the Line objects are moved to the other HullDynamic without being changed, i.e. Line::succ still remains the old lambda. This old lambda doesn't work properly now, because it still compares next(y) to the end() of the old HullDynamic (that was captured through this).

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

              Yeah, this is indeed true. Thanks for clarification.

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

          I used this and passed. Some people told me that swapping the structure may not break the complexity, but I’m not that much of C++ expert..

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

            Do you mean that you swapped the structures and passed? Complexity wasn't an issue for me, but I was getting garbage values for queries when I swapped the structures themselves.

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

              Ah sorry. I mean I also had the same id[v] stuff because I don’t know how to do it otherwise.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 4   Vote: I like it -10 Vote: I do not like it

        I struggled in a lot of problems with this implementation. It seems like the multiplications overflow when the limits are high and then everything goes wrong.

        UPD : Sorry misunderstood the problem

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

        I believe that kactl's LineContainer is neat and efficient. It also didn't have such problems.

        Also, you can use object1 = move(object2); if you don't need object2 anymore. I think it may be better than swap().

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

    I thought C was ok, at least you have to think a bit or draw something on the paper.

    Otherwise having tree+queries problems in every round is just beyond boring.

    Maybe they should change the format and do something completely different. It just can't get worse.

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

    I thought B was nice (no ugly input and above average quality for its level).

    But everything went downhill from there and you are absolutely right about D.

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

      Good that someone liked it but B requires literally 0 observations/ideas, just a standard approach.

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

      I found the video from D rather interesting.

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

Curious to know more about B solution

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

My solution for problem D is successfully validated, but crashed on full input...

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

    Just to be sure, is it maybe the stack size on your machine? Some trees in the main input were quite deep.

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

      Mine crashed even on validation input before increasing stack size

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

Rank 200 :P

LoneFox Please tell there won't be any changes in ranklist XD

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

    In general you can only go up after the contest (because of people getting disqualified for plagiarism), so you should be safe :)

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

    Rank 201 by one second. Please accept one more person into Round 3 :D

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +198 Vote: I do not like it
      • If you want to know the value of one year, just ask a student who failed a course.

      • If you want to know the value of one month, ask a mother who gave birth to a premature baby.

      • If you want to know the value of one hour, ask the lovers waiting to meet.
      • If you want to know the value of one minute, ask the person who just missed the bus.
      • If you want to know the value of one second, ask the person who just escaped death in a car accident 12tqian.

      (c) Marc Levy

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

Why you have to torture us with problem like C?

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

the video in problem D is more interesting than all the problems (:

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

Consistently bad after Round 1

»
4 years ago, # |
  Vote: I like it +53 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +125 Vote: I do not like it

The only creative thing about problem D is the pun "log-istics team".

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

Never thought I'd find myself as the 201st, with the difference between 200th and 201st place being only 1 second. :(

RIP Round 3

»
4 years ago, # |
Rev. 2   Vote: I like it +89 Vote: I do not like it

I made 6 bugs in reading input in D. SIX!!! Very glad that they show what is actually the valid input that we want to get.

»
4 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

https://www.facebook.com/codingcompetitions/fb-hack what is this competition? Is it a team-based CP competition or some other stuff? LoneFox

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

    FB Hack is an event that has a CP component, and also an ideas hackathon. It's made for teams of 5 university students, and it's held locally in various regions (though of course online during COVID).

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

Everybody seems to use dynamic hull, but isn't this really easy with plain static hull? Process tree from bottom to up and build a segment tree over preorder and ech time you get a new node and want to know its value (and some queries for it) just ask about some base intervals and that's it. Only tricky thing you need to care about is that for each base interval all queries regarding it come after all insertions, so you need to build it from what you gathered up to this point first time you query it.

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +37 Vote: I do not like it

    With dynamic hull you don't need a segment tree — simply merge the hulls of children via small-to-large and answer queries at that node. This gets you extremely short extra code (excluding parsing and copy-pasting structure, a single DFS with ~15 lines).

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

      Well, having dynamic hull over static hull may indeed simplify things, but if somebody can't find ready-to-use dynamic hull then solution I suggested is far easier than coding dynamic hull and proves that having dynamic hull was not a prerequisite here.

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

        Was not a prerequisite, but the problem asks "write dynamic convex hull" which makes it a bad problem in my opinion.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Need help in finding error in my dp for problem B.

Code
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    if(i & j) lrpp=lr*((1.0-p)*dp[i][j-1]+p*dp[i-1][j]);    // when (weak, strong) plays
    

    Should be if (i && j)

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

      Thanks.
      Couldn't find this silly mistake during the contest. Disappointing.

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

        Maybe next time use if (i > 0 && j > 0)

        This is equivalent to if (i > 0 & j > 0) in case you mis-spell the && operator

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

Am I the only one who cannot access the scoreboard? (for both "Everyone" and "Friends") It keeps loading forever.

Tried clearing the cookies, still getting the same result. But opening the scoreboard while in incognito (not logged in) works. Maybe something is wrong with my account.

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

My screencast, 7th place https://youtu.be/Gpsn2P5UY_A (very fast ABC then quite slow D because I didn't copy anything)

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

Can we expect very generous t-shirt distributions in future rounds too?

»
4 years ago, # |
Rev. 4   Vote: I like it +37 Vote: I do not like it

Did anyone receive the email saying that the Round 2 would last for 24 hours, instead of 3 hours?

I planned to compete the next day, as the round started late (1am) where I am living now, therefore I missed the round.

My mistake is not checking the time again in the announcement FB post and this post. But this inconsistency costs me a chance to participate.

Edit: I cannot add the image. Link to the image: https://pasteboard.co/JoGsyHj.png

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

The best thing about this round was free T shirts. I did really like problem A and B, not much implementation and stuff, but problem C was, at least in my opinion, a straight out implementation problem, with zero thinking needed (parse inputs, figure out which edge is where, repeated set operations, etc.). I thought it was just me, but even the editorial didn't offer a better approach. And from other comments, it seems the same goes for problem D. Not that I personally care as I wouldn't have made it into the top 200 either way, but its sad that in such a prestigious competition tougher problem implies implementation oriented problem.

PS :- I did like the effort in trying to make the problem statements funny.

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

Till which date can we expect the t-shirts to come. Really excited for it :P

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

    It's mentioned in the post:
    We'll begin shipping out t-shirts by early 2021 or earlier, at which point the winners will receive emails with tracking information.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why is tourist not participating in this? Just curious...

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

    He is, I think he was exactly 1 rank above me in this round.

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

I have found a strange mail last night. I think this is fake. Is it from hacker cup official?

IMG_20201106_093833.jpg

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

    I too received such an email, though my name was present in the email instead of the ascii characters. All previous round announcement emails I got were from the same email address as this one. But your mail seems strange so I guess it maybe better to wait for someone from FB to confirm.

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

      I see, those characters are actually my name. My facebook account name was written in my local language using some font. So, now i am afraid of my name. is it make some problem while delivery? I thought this was fake because they mentioned this prize for begin top 2000. But after that i found they use the same mail address they sent announcement mail.

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

        If your name is correct when read in your local language it should be fine. Maybe the delivery mail will ask for the details once again.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          i think it is fake because In my email, it is written about top of 1500

          oh sory , after rechecking my email, that is written about top of 2000 ... sorry

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

            I've received similar email from [email protected] with next content:

            The Facebook Hacker Cup Store team is delighted to send you this one-time promo code redeemable for Facebook Hacker Cup Store Swag.
            
            Please click this link and enter your code.
            

            I assume this is a fraud, but it would be great if facebook could confirm that. Unfortunately I found no possibility to contact them in facebook

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

              I received it today.

              In 2019 there was also some mail with jniwebshop link, and I got my T-shirt, so I think it is not a fraud.

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