LoneFox's blog

Facebook Hacker Cup 2021: Qualification Round
By LoneFox, history, 3 years ago, In English

The Qualification Round of the 2021 Facebook Hacker Cup is less than 48 hours away!

The round will begin on August 27th, 2021 at 10am PDT and will last for 72 hours (3 days). The contest can be found here.

Everyone who solves at least one problem correctly will advance to Round 1, which will take place on September 11th. Please note that all submission judgments will only be revealed after the round ends. More details about rules and other information can be found in the FAQ.

Registration will remain open on the contest page until the end of the Qualification Round. Once you've registered, you may wish to confirm that the information in your competition profile is up to date. In addition to choosing a Display Handle for yourself there, you may now also indicate which country you’d like to represent on scoreboards.

This year's contests will feature a new submission flow making it easier to download large input files. For each problem, you'll now download the full input in a password-protected zip file, and the 6-timer will only begin when you then request the password to access your file. You'll also be given the option to directly download the raw input file (as in past years) in case you have trouble with the zip file. Please see the “How do I submit my solution?” section of the FAQ for more details.

Last year’s increased prizes are making a return in the 2021 Hacker Cup season, including 2,000 t-shirts to be won and a $20,000 grand prize.

We wish you the best of luck, and hope that you enjoy the contest!

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

Comments Comments (131)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had a question : is 6 minute time limit when downloading the input the only TL constraint on our programs ? Or is our source code ran with a tighter TL in the background after contest finishes ?

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

    Your code will not be re-run, so the only time limit is indeed the 6 minutes you have to run your code and upload your output upon downloading the full input — please see the FAQ for more details.

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

      Thanks

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

      What happens if somebody submits a correct output, but wrong source code? For example, the source code of a problem A solution as a part of their problem B submission?

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

        For such cases noticed by the Hacker Cup team, you may be asked to provide your correct source code file after the fact, and intentional submission of wrong/fake source code may in some cases be grounds for disqualification.

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

          But if the code will not be re-run, how will you know it's wrong?

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

            Code may be re-run or otherwise inspected on a case-by-case basis.

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

Very Excited to participate as it will be my very first contest. I request every one who is reading this give your time to each question and try to solve at least anyone of them, you have 3 days.

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

How many official submissions can we make ? I am asking this because what if we aren't able to submit the solution and output in 6 minutes due to any reasons like Power failure or network issues. Will we be able to submit the solution and output for some other input file in 6 minutes ?

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

    You'll only have one chance per problem, meaning that you should be confident that you'll be able to complete your submission within 6 minutes before starting your timer.

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

      Thanks

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

      Last time I had coded the correct solution for a problem, but during submission my program crashed. I could not submit in 6 minutes. Later I found out that it was due to smaller stack size of execuatables on windows.

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

Have a small question. Why dont we have the feature of submitting the code directly and run in your server rather than we running locally like almost all the sites (eg. Google Codejam) ?

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

    There are a couple major advantages (imo) of this system:

    1. If you have local library code you want to use, you can simply import it into your main source file and not have to copy it over and clutter your code.

    2. The 6 minute time limit makes more unconventional solutions and strategies possible (and thus, allows for unconventional problems which might not be solvable with a traditional time limit), which makes for a unique experience. I actually enjoy this more than the traditional submission system.

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

      Even more than local libraries, you can use other tools and environments not usually possible in programming contests. Want to use a spreadsheet or some special math software like Sage? Totally possible in this format.

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

      Does that mean they only care about the output file and not the source code?

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

        Yeah! i think so.
        We do not run your code
        Above statement is from Hackercup FAQ section

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

    Because it's way harder to setup a whole online judge?

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

    People can use different unconventional tools. Like the things then do in Advent of code.

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

can you tell where is the option to directly download raw input file without downloading the zip file, since I downloaded the zip file but was not able to extract the input file while I was trying to unzip it. It showed that an error occurred. Resulting, that I wasn't able to submit correct output file. Although I am pretty much sure that my solution is correct.

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

    The option to download the raw input file shows up in the same window right after you request the password. I also wasn't able to unzip the file right away, so I used this option. Appears that just running 7z x consistency_chapter_1_input.zip and then pasting the password from the clipboard didn't work correctly on my system and 7z rejected the password. Later trying it as 7z x -p12345678 consistency_chapter_1_input.zip worked (substitute '12345678' with the real password).

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

      do you mean that after verifying sample test file, in the same open dialog window, there is an option to download raw input file.

      I am concerned only because I fear to not a submit a solution within 6 minutes, because of these petty issues. Please help.

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

Can anyone tell me how can we run our code on an input text file and produce an output text file. I am using code blocks IDE on windows system. I also tried to manually create the output file by copy pasting input and output . But it's showing me presentation error.

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

    ./file_base_name<input_file_name.txt>output_file_name.txt

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

      Thanks for replying. Can you please tell me where to use this command. I used this in command prompt and it's not working.

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

        Assuming your program is taking input from standard input and outputting to standard output ( e g cin, cout in c++) . Let s say your executable is called a.out after compiling the code. Let s say you have a1.in as input file, and ypu want output to be at a1.out . Then ./a.out < a1.in > a1.out in terminal

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

        You need to replace:
        1)file_base_name — with the executable
        2)input_file_name.txt — with the input file file.
        3)output_file_name.txt — with the file in which you want the output
        This will work in the command prompt once you locate your folder. You can locate your folder using cd +(folder_path). Here replace folder_path with the path of your folder where your CPP file is.

        for generating the executable for your c++ files uses the command. g++ file.cpp -o file (replace file.cpp with the name of your file) It should work after that.

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

it would be really cool to provide participation/progression certificates to participants like the CodeJam, ignore this if already implemented this year <3

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

    Such certificates are in fact available as of this year! You can find past certificates in My Competition History within your profile page, and links to certificates for the 2021 season will also be available as the season progresses.

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

what is the password?

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

    After downloading the input zip file, password is used to open and access that file.

    Note down, You have only 6 minutes for :

    Enter password -> unzip the file -> Run code on it -> generate output file -> submit(source code + output file )

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

imagine having a supercomputer and being able to run any kind of bruteforce...

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

    Even simply having a multicore processor allows to use OpenMP pragmas or the other easy tricks to parallelize the code and make it run faster. And it is fun, because these are the skills, which are never tested in the other competitive programming contests.

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

    It gives us 6 minutes to submit the output. I am pretty sure even my potato computer can do in this time.

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

I can't open the zip file by macOS default application.

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

After reading "Xs and Os" I wonder: why are we being encouraged in such a stupid cheating? :)

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

    Indeed, that's pretty stupid. The fact of cheating is easily provable by the other guy. Reminded me the chess tournament scene from "The Twelve Chairs" movie: https://youtu.be/P8t2dbJ7YXY?t=6751 (with English subtitles).

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

LoneFox when I am clicking on download validation input file, it starts downloading an index.html file. I have tried it 4 times. what should I do?

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

    What browser/OS are you using? A different browser might work.

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

      okay thank you

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

        I'm assuming this reply means that switching the browser fixed it, but just so we know, which browser/OS were you using when it didn't work?

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

          Yes, it worked. Before I was using Chrome but after I switched to Mozilla Firefox it started working.

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

I had a doubt, when it says solution validated does it mean it was correct for that test case or it just means it was submitted successfully?

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

Solved!

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

Well, it's nice to see the "password protected input" feature implemented, but do you really need to use some fancy compression method that standard tools don't support? This is not nice:

$ unzip consistency_chapter_1_input.zip 
Archive:  consistency_chapter_1_input.zip
   skipping: consistency_chapter_1_input.txt  unsupported compression method 99
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Check out their FAQ page. They have clearly mentioned about unzipping and tools that would work without any issue.

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

      The point is that a standard tool such as unzip should work. I spent some time and couldn't find any way to open a FHC zip file in my system (I didn't want to install new software just for this contest). Fortunately it was also possible to download the input normally.

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

    It's indeed necessary to use this type of encryption (AES-256), as the default "ZipCrypto" encryption is highly insecure (further reading here).

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

      Thanks for the explanation. So maybe unzip should support AES-256 (if it really is industry standard).

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

      Oh wow, thanks for the info! It feels so counter-intuitive that zip and unzip are not the right tools to handle [encrypted] zip archives.

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

    install 7zip in MacOS. then run this command on terminal: 7z x problemName_input.zip

    This command will prompt for password. Paste the password with (Command+v) that you copied.

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

I've just registered on Facebook, but it buns me without any reason. I send them my photo and now have a message that they will check it , but I can't write a qualification round without an active Facebook account. Can they unblock my account faster or can I solve problems from this round without a Facebook account?

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

    Hi, I've responded via a private message.

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

I would have preferred the source code to be submitted during validation to have a less panicky 6 minutes.

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

I created a Facebook account yesterday to participate in Hacker Cup. But Facebook has disabled it twice. When it disabled it the first time, it asked me to verify my phone number which I did. Now it is again disabled and Facebook asked for a photo which I have sent but I haven't received a reply. Now I am scared if my account remains disabled, I won't be able to participate. I have tried to create another account with different emails but all are disabled after they are created. Someone, please suggest what I should do. LoneFox please tell me something.

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

    Hi, I've responded via a private message.

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

It might be a dumb question but do we have to solve any one of A1, A2,B, C1,C2 or one question is A1,A2,B and other is C1,C2.

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

After the end of the contest , how much time it will take to evaluate the submitted solutios?

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

What if I submit wrong code but correct output?(I ask for people to try to escape plagiarism checker(if it exists))

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

Why do you have to make the process more tedious by adding password protected inputs? I had issues with extracting the file.

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

    We added this feature so that there's less chance of a slow internet connection interfering with your ability to submit.

    You're still able to download the input directly instead of downloading the zip file, if you desire.

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

    People can face issues while downloading the large input file (like slow net, power cut, system crashed, etc). Password was introduced so that the timer will start after the user has finished downloading the input.

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

Hi, I'd like to suggest you could add functionality to the scoreboard to filter by country, like Google Code Jam has.

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

    Good idea. :)

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

      How does the Friends feature work? Does it only take literally Facebook Friends or we can somehow mark someone as Favorite as CF or Google Competitions?

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

        It's your friends on Facebook, yes.

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

          It would be cool if it would also show people you're Following but aren't friends with.

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

    You can also use clist: link

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

Any intuition as to why this is wrong for C2? Only fails on large cases from the official test set.

Fix first path from $$$1$$$ -> $$$a$$$, last from $$$b$$$ -> $$$1$$$ for all possible distinct pairs of $$$a$$$, $$$b$$$ such that the paths don't have common edges, mark used edges and set $$$c_{x} = 0$$$ for nodes visited. Then $$$k - 1$$$ times, choose the next best path as the diameter with respect to $$$c_{x}$$$ using only unused edges (also mark used edges and set $$$c_{x} = 0$$$ for used nodes). This logically seems correct on examination with exchange arguments on $$$i$$$-th and $$$j$$$-th paths taken in optimal order, considering cases where paths have / don't have a common node separately.

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

    Consider the case where $$$k=2$$$ and vertex $$$1$$$ has only one edge coming from it, like:
    4 2
    1 1 1 1
    1 2
    2 3
    2 4

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

      But, for that case you can choose $$$b$$$ to be equal to $$$1$$$ (root).

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

      Yes, I should clarify that $$$a$$$, $$$b$$$ can be $$$\textbf{any}$$$ pair of nodes for which the paths from $$$1$$$ to $$$a$$$ and $$$1$$$ to $$$b$$$ do not have common edges. Otherwise this would have failed on the samples itself.

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

    https://imgur.com/a/yvjkA9z

    Your approach might not work in the case mentioned in the image above, as there is no such pair of a and b according to the conditions you have specified.

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

      I should have clarified, b can be equal to any node, include $$$1$$$ (the root itself), so in this case choose a = the bottom left node, b = the root, then the max diameter picked in the 1 remaining step will just be the bottom right node.

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

    Got the mistake, my proof is wrong since the exchange arguments proof only considered common nodes, forgetting about common edges.

    Assume we get the above structure as one of the trees of the remaining forest after fixing the paths $$$1$$$ -> $$$a$$$ and $$$2$$$ -> $$$b$$$. Additionally let $$$c_x = 1$$$ for all nodes. Then we can consume all resources in $$$2$$$ paths ([1, 2, 3, 7, 8] and [6, 5, 4, 9, 10]), but if we take any diameter it will require $$$3$$$ paths to consume all. So taking the diameter isn't always optimal.

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

      Did I get something wrong or in your optimal solution you used the diameter of the node $$$4$$$? (path $$$6$$$, $$$5$$$, $$$4$$$, $$$9$$$, $$$10$$$ is the diameter path).

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

Created video solutions for Facebook hackerCup solutions, if interested please checkout:

https://www.youtube.com/watch?v=hjTAshY60Xo&ab_channel=AlgoShalgo

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

Question:

How do I know if I qualified for Round 1 of the hacker cup? Would there be any official communication from the Facebook team?

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

    You can check the unfinalized scoreboard here, which would tell you if you got any of the problems incorrect. We will be sending out official advancement emails later this week once the results are finalized.

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

I have a doubt that why they use 6 minute timer?

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

    Since you get to run your own code locally, if there were no timer, you could write naive solution that should be too slow, but just wait a long time for it to finish running.

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

      But you guys are also taking our code right? Also, why not just be like other coding competitions where you just submit and get instant feedback?

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

    To have enough time to sort out how to unpack this thing

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

I appreciate the step taken be facebook to provide certificates but I would like to point out that the rank cannot be seen clearly/visible.

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

    We'll get that fixed, likely within the next 24 hours.

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

I don't have any idea. How did I miss this year hacker cup :(

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

I think that the problem B had weak testcases. I initially implemented a very suspicious messy solution, which passed the validation input:

A buggy implementation in D language
A buggy implementation converted to C++17 language

I wasn't happy about it and reimplemented my final solution in a different way before submitting. Turns out that my initial implementation was indeed buggy and failed the following simple testcase (printed "Case #2: 1 2" instead of "Case #2: 1 3"):

A small testcase

But the official "xs_and_os_input.txt" input file from the contest was unable to catch this bug, so both buggy and correct implementations produced the same output. Did all participants receive the same "xs_and_os_input.txt" file or are the input files randomized to some extent?

Edit: Added a C++ variant of my broken solution if anyone wants to hack it (this code is very broken and should never pass any reasonable tests). But it happens to generate correct output for "xs_and_os_input_practice.txt" too (downloadable in practice mode now). Tagging LoneFox and SecondThread if they are maybe interested in fixing at least the practice mode.

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

    Your code always excludes some value from tmp even when it's not an optimal answer. When it's an optimal answer, the way tmp being constructed is incorrect, too.

    1
2
..
XX
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, yes, I'm interested in potentially adding a case to the practice input at least if it won't create technical difficulties if we later need to re-judge things for some reason.

    However, the small case you give isn't legal according to the problem spec. Note this part of the statement:

    In the game's current state, both players have made an equal number of turns (in other words, the number of Xs is the same as the number of Os), neither player has won yet, and the game has not yet ended in a draw (meaning that at least one cell is still empty).

    Can you please provide a case that you think would be equally powerful that satisfies these conditions as well?

    Regarding your question:

    Did all participants receive the same "xs_and_os_input.txt" file or are the input files randomized to some extent?

    Different participants may receive different inputs. We use this for plagiarism checks and validation to sanity-check participants to make sure they are submitting the right thing.

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

      Thanks for your reply. You are right. There has to be the same number of Xs and Os on the board. One of the minimal testcases that satisfies the conditions would be:

      Spoiler

      In general, the most tricky part of any solution for this problem is handling the case when minimum k = 1 (the number of Xs to add for a win). Let's call a row or column interesting if it contains all Xs except for one dot. And a test is interesting if the combined number of interesting rows and columns is at least 2 (but 3 or more is even better). I think that a strong testcase for problem B needs to include a lot of interesting tests to catch a wide range of possible bugs in handling of the k=1 case.

      I also see that the practice testcase includes 82 tests. But the problem constraints are T<=70. Maybe problems of this kind could benefit from a much larger limit for T? Otherwise it's hard to fit a lot of interesting tests in a testcase and make it strong.

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

How can I see the leaderboard for a specific country?

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

Could someone (un)justify this idea for C2? There are N * (N - 1) / 2 paths in a tree. Consider all the paths as vertices in a new graph, where weight of a vertex is sum of the corresponding path. Now, two vertices in a new graph will be connected if their corresponding paths share at least one edge. Then the problem reduces to finding maximum weight independent set in the new graph (with a restriction that at least one path must contain vertex 1 in original graph and cardinality of the set must be at most K). But the new graph is bipartite, so one can find maximum weight independent set by means of maximum matching which can be done efficiently in bipartite graphs by some max flow I believe. The thing is, I don't know if it's possible to use maximum matching for finding maximum weight independent set (it seems possible for unweighted case), i. e. by somehow tweaking the max flow algorithm. In addition, it could be hard to ensure that path with a root in original graph would be a part of the max independent set. But is this solution path correct in general?

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

    No, this can't handle the case where multiple paths share the same vertex.

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

      I think I got what you meant. Thank you

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

The rank in my certificate isn't visible clearly. Can you fix this?

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

    Is your problem solved? My rank still overlaps with the star icon in the certificate.

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

      Yes, my problem is solved :)

      I hope yours will also be fixed soon.

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

I solved C1 using information from direct children of node 1 (counting edge cases of having single child seperately). I have not done much question on tree-dp. Can anyone explain simpler method for C2.

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

what is the criteria of getting t-shirt LoneFox?

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

    From https://www.facebook.com/codingcompetitions/hacker-cup/2021

    What prizes can I win? The top 2000 competitors who solve at least one problem in Round 2 will receive a Facebook Hacker Cup t-shirt. The top 200 competitors from Round 3 will have a "Top 200" badge on their shirt.

    I would say that both of us at least have a chance. Finishing in the top 2000 is sometimes possible if the stars align right ;-)

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

Surprisingly, my C2 has passed, while C1 has failed with the same solution. I suspect weak tests for C2.

For C2 I used O(N*K*K) DFS-based DP, where for every node V, DP[V][i] is the max sum taken from the corresponding subtree using at most i paths (with disjoint sets of edges), where i is either an integer or an integer with a 'half' (the latter means 'open' path extended outside the subtree). The last step in the solution is correct interpretation of DP[1] for obtaining the result (we either add 1 or not depending on whether a found set of paths passes through the vertex 1).

Has anyone experience the same or does know why my C2 solution doesn't work for C1?

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

    Could you please post a link to your C2 solution? And also pastebin your C1 testcase somewhere?

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

How do I know if I have advanced to Round 1? When I open the Round 1 page, it shows "You have not registered for this contest". I was able to solve 1 question & it is correct.

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

Is it only me who solved C1 with LCA? LCA seems unnecessary here.

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

    I also overkilled the problem using LCA. I checked for every leaf pair and checked their LCA, if it is 1. Although I realized later that this was a simple problem that could be solved just by getting information from direct children of 1 (if any).

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

Hi, I'm trying to understand a C2 solution. I can't get the concept of extension points for the paths in the subtree. I understand that the path, which has one endpoint (extension point) in the subtree root, can be extended from the parent, by using parent-child edge. However, I noticed that there is a dp state, which has 2 such extension points — could somebody explain this situation? How could the path in the subtree be extended in 2 places?

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

I have a doubt regarding the round 1. Does the 6 minute timer appear only once and after that time, we cannot submit for that problem? I tried running my A1 solution and I use online codechef IDE and the input was too large for that and the timer ended before I could install a local compiler on my laptop and I can't submit for that problem again :(

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

    Then you are not able to submit that problem again

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

      uhoh, I was under the impression that a fresh input file would be generated which then I could run again. Nevertheless, thank you!

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

Does after solving A1 and A2 , is it guaranteed that I am qualified for round 2.

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

    Everyone who scores at least 24 points (regardless of time taken) will advance to Round 2
    Source

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

    Yes, you will qualify if both of them are correct. But you won't get the final verdict whether they are correct until the contest ends as per my interpretation

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

How to run the input files for a1 every compiler says input too large.LoneFox

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

    in linux/windows for cpp

    g++ codeFile.cpp

./a.out < inputFile.txt > outputFile.txt

    in macos/linux/windows.

    g++-11 -Wall -O2 -std=c++11 codeFile.cpp -o code

./code <inputFile.txt > outputFile.txt

    codeFile contains your code in a file name codeFile.

    inputFile contains input

    and outputFile may or may not be in your disk if it is not then it is automatically created in the same directry.

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

I was confident about the code which I wrote for A2 , it passed validation tests but while compiling the code crashed on sublime Text . What precaution should I take such that it does not crash for remaining problems ?

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

    Same happened with me too.. It was because I was not creating the N sized array globally.. After the time ended, I tried on the same input with globally declared array and it executed properly on Sublime..

    Maybe your crashed due to same reason :/

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

I got a problem in the final input file of the problem A1("Weak Typing — Chapter 1") of round 1 . The characters of the file are different from the input format of the problem.

Screenshot

Is this a problem with my PC ?

LoneFox Pls Help !!

→ Reply