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!
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 ?
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.
Thanks
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?
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.
But if the code will not be re-run, how will you know it's wrong?
Code may be re-run or otherwise inspected on a case-by-case basis.
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.
[deleted]
Thank you so much !
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 ?
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.
Thanks
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.
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) ?
There are a couple major advantages (imo) of this system:
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.
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.
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.
Does that mean they only care about the output file and not the source code?
Yeah! i think so.
We do not run your code
Above statement is from Hackercup FAQ section
Because it's way harder to setup a whole online judge?
People can use different unconventional tools. Like the things then do in Advent of code.
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.
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).
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.
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.
./file_base_name<input_file_name.txt>output_file_name.txt
Thanks for replying. Can you please tell me where to use this command. I used this in command prompt and it's not working.
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
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.it would be really cool to provide participation/progression certificates to participants like the CodeJam, ignore this if already implemented this year <3
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.
what is the password?
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 )
imagine having a supercomputer and being able to run any kind of bruteforce...
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.
It gives us 6 minutes to submit the output. I am pretty sure even my potato computer can do in this time.
I can't open the zip file by macOS default application.
https://www.ezyzip.com/unzip-files-online.html
what? It works for me, just double click in finder, it'll ask for password and extract
well, for me when I enter the password it asks it again.
If you have good internet just download the file normally, the password zip is for people with bad internet to download the data before unlocking it.
After reading "Xs and Os" I wonder: why are we being encouraged in such a stupid cheating? :)
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).
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?
What browser/OS are you using? A different browser might work.
okay thank you
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?
Yes, it worked. Before I was using Chrome but after I switched to Mozilla Firefox it started working.
Chrome on which operating system?
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?
it was correct for that test case
Solved!
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:
Check out their FAQ page. They have clearly mentioned about unzipping and tools that would work without any issue.
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.
It's indeed necessary to use this type of encryption (AES-256), as the default "ZipCrypto" encryption is highly insecure (further reading here).
Thanks for the explanation. So maybe unzip should support AES-256 (if it really is industry standard).
Oh wow, thanks for the info! It feels so counter-intuitive that
zip
andunzip
are not the right tools to handle [encrypted] zip archives.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.
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?
Hi, I've responded via a private message.
I would have preferred the source code to be submitted during validation to have a less panicky 6 minutes.
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.
Hi, I've responded via a private message.
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.
After the end of the contest , how much time it will take to evaluate the submitted solutios?
What if I submit wrong code but correct output?(I ask for people to try to escape plagiarism checker(if it exists))
See https://mirror.codeforces.com/blog/entry/94259?#comment-832918
Why do you have to make the process more tedious by adding password protected inputs? I had issues with extracting the file.
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.
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.
Hi, I'd like to suggest you could add functionality to the scoreboard to filter by country, like Google Code Jam has.
Good idea. :)
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?
It's your friends on Facebook, yes.
It would be cool if it would also show people you're Following but aren't friends with.
You can also use clist: link
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.
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
But, for that case you can choose $$$b$$$ to be equal to $$$1$$$ (root).
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.
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.
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.
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.
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).
Created video solutions for Facebook hackerCup solutions, if interested please checkout:
https://www.youtube.com/watch?v=hjTAshY60Xo&ab_channel=AlgoShalgo
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?
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.
I have a doubt that why they use 6 minute timer?
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.
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?
To have enough time to sort out how to unpack this thing
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.
We'll get that fixed, likely within the next 24 hours.
I don't have any idea. How did I miss this year hacker cup :(
I think that the problem B had weak testcases. I initially implemented a very suspicious messy solution, which passed the validation input:
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"):
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.
Your code always excludes some value from
tmp
even when it's not an optimal answer. When it's an optimal answer, the waytmp
being constructed is incorrect, too.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:
Can you please provide a case that you think would be equally powerful that satisfies these conditions as well?
Regarding your question:
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.
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:
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.
How can I see the leaderboard for a specific country?
Try this
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 mostK
). 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?No, this can't handle the case where multiple paths share the same vertex.
I think I got what you meant. Thank you
The rank in my certificate isn't visible clearly. Can you fix this?
Is your problem solved? My rank still overlaps with the star icon in the certificate.
Yes, my problem is solved :)
I hope yours will also be fixed soon.
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.
what is the criteria of getting t-shirt LoneFox?
From https://www.facebook.com/codingcompetitions/hacker-cup/2021
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 ;-)
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?
Could you please post a link to your C2 solution? And also pastebin your C1 testcase somewhere?
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.
They will be sending emails later this week according to SecondThread
Is it only me who solved C1 with LCA? LCA seems unnecessary here.
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).
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?
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 :(
Then you are not able to submit that problem again
uhoh, I was under the impression that a fresh input file would be generated which then I could run again. Nevertheless, thank you!
Does after solving A1 and A2 , is it guaranteed that I am qualified for round 2.
Everyone who scores at least 24 points (regardless of time taken) will advance to Round 2
Source
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
How to run the input files for a1 every compiler says input too large.LoneFox
in linux/windows for cpp
in macos/linux/windows.
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.
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 ?
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 :/
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.
Is this a problem with my PC ?
LoneFox Pls Help !!
This is a known bug with Notepad. Please use a different editor.
https://en.wikipedia.org/wiki/Bush_hid_the_facts
OMG this is hilarious
Should you form inputs so that they don't trigger this bug?)
I think Microsoft should learn to make a text editor :P