Round 1 of the 2021 Facebook Hacker Cup is less than 48 hours away!
The round will begin on September 11th, 2021 at 10am PDT and will last for 24 hours. The contest can be found here.
You're eligible to compete in Round 1 if you solved at least one problem correctly in the Qualification Round.
Everyone who scores at least 24 points (regardless of time taken) will advance to Round 2, which will take place on Sat. Sept. 25th. 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.
We wish you the best of luck, and hope that you enjoy the contest!
Good luck have fun, and see you all on the scoreboard!
Can you please tell the scoring distribution
24 points out of 100?
From the past rounds I've looked at, it's usually out of 100, and for round 1 you usually need to have gotten AC on the first two problems to advance.
May be we will need to solve at least 2 problem to advance to Round 2;)
24 points in 24 hrs!
Nice :)
Am I the only one who get "This page isn't available" error when trying to access https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1? I got that error when logged in, but managed to load the page when in incognito.
LoneFox can you help check on this issue?
It looks like you've been able to submit since. That may be some transient infrastructure issue.
Are there any prizes like T-shirts for this round?
Only for round 2 onwards.
How strong should we expect the "validation input" to be? Should we expect it to be similar to pretests on Codeforces?
My understanding is that on Codeforces, authors aim to minimize FST, so they try to make pretests as strong as possible, as opposed to intentionally leaving max-size tests or tricky edge cases for systests (aka "full input" on Hacker Cup).
I think the easiest way to find out is to just look at the input, you can even instrument your code to measure coverage.
Good idea, I definitely should have looked more closely at the input. (Though it'd be hard to see if it has edge cases that I didn't think of while solving the problem.)
LoneFox, my question is more about the authors' intent, if you know.
You guys are walking on a thin ice. This kind of communication may be interpreted as assistance in solving/debugging problems from the running contest if you push this further. And my question about the scoreboard UI probably wasn't very appropriate either if we interpret contest rules literally. So I'm dropping out of here.
Edit: As usual, there's no shortage of simple minded lemmings on codeforces :-) Come on, downvote me more! You will never understand that I just warned people BEFORE they crossed the line. Whether they would or wouldn't make an accidental mistake without this warning is another question. Better be safe than sorry.
I think the question is a good one. It's fine to ask about general things related to Hacker Cup at large.
We typically want the validation input to prevent any possible misinterpretation of the problem, but we don't usually include a truly maximum case.
Is there any way to see the total number of problem B submissions done by the other participants during a running contest? Does the scoreboard page track this statistics in real time?
The scoreboard is realtime, though it doesn't show any summary stats like how many people have submitted for a given problem. You'd have to page through to get a rough estimate.
Thanks! Are there any plans to implement summary stats? Before people start scraping web pages to automate this process and put an unnecessary burden on Facebook Hacker Cup servers.
We're indeed considering adding such a feature, either next year or possibly even this year.
Where did the compressed input form go (i.e. used here last year)? The input was huge on C and I'm not sure if that's the reason my code started to segfault (I don't think I used too much memory nor time), but it sucks to pass validation and not be able to even submit on the real thing :\
If the input size has no affect on that, then it's fine, but I was still a fan of that form of input.
The input size was quite small compared to a normal Codeforces problem, it's possible you ran out of stack space or something.
One of the reasons we added zip files this year was to avoid having you handle that relatively unpleasant format. Unfortunately the zip file for C has an issue that we're investigating. Once that's resolved, I do think the zip files are a much cleaner way of handling large input than making contestants generate the input on their own.
What is the issue with the zip file for C? My program crashed on the judge input, and I only found out after the timer ran out that it was because the zip file had an "Unexpected end of data". Until now, I assumed that I didn't pay enough attention when downloading the file, but your comment makes me wonder.
Have you guys resolved this? Would it be possible to set up the encrypted-zip-file format in practice mode so we can test?
We're still working on it. We know what the problem is and when it's fixed we'll be able to be quite confident through our own testing. I appreciate the offer though :D
That sounds good, though I wanted to test my own decryption scripts as much as your system.
ಠ_ಠ
Input generation is terrible and it doesn't allow the test data to be as flexible as possible. I couldn't submit C too and I can guarantee with you that the input size is perfectly fine.
Hey, my C also Segfaulted on the real input, and I couldn't fix it in the 6 minutes. It turned out to be a stack usage problem, because when I set my stack to 200 MB with compiler flags, it ran fine.
Lol, you are probably the first person on planet Earth to advocate for compressed input format if there is an option to do it normally
vkgainz I have faced the same problem earlier. I solved it by increasing the stack space limit. If you are on ubuntu, the command to increase stack size is
ulimit -s desired_space(in KB)
. For example, if I want to set the stack space to 1GB, I would runulimit -s 1048576
in the terminal.I don't know if you solved your problem since, but my solution was actually crashing on a (slightly overloaded) DFS for the C, because of the stack size. When I switched to a native Linux (as opposed to WSL) and increased the stack size (using
ulimit -s unlimited
in the shell), there was no problem anymore.My pc wasn't responding when I tried to run the input for 1 problem and the time expired. Did it happened to anyone else too?
same even my pc crashed for A1 and B both and now i am out even after solving 2 questions
A common issue was people writing O(N^2) solutions to problem A when O(N) solutions are necessary. You won't be able to run an O(N^2) solution in 6 minutes when N = 800,000.
Those who are using c++ and facing problem with stack size adding this "-Wl,--stack=268435456" compiler flag may help. I think facebook should reconsider their judging system as current system is extremely annoying.
where to add , i have submitted the wrong output but then also Edit- i added inside the vs code terminal where flags like c++ , a.out and more like that are given its only taking time and no output is coming and on sublime its giving wrong
"code-runner.executorMap": { "cpp": "cd $dir && g++ -DLOCAL -Wshadow -pedantic -Wall \"-Wl,--stack=268435456\" -Wextra -O2 -std=c++17 $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt", },
It is really annoying. I couldn't submit my A2 due to stack size of my laptop and it is not like I am using too much memory or time.
Facebook should consider changing their judging system to something like what Codejam is using in the future.
It is really annoying when purples can't set stack size
How to set up stack size on Windows , Sublime text 3 , MingW compiler ?
Add
-Wl,-stack=268435456
to your build file.Here's how my C++.sublime-build looks
{ "cmd": ["g++.exe", "-Wl,-stack=268435456", "-std=c++17", "-DLOCAL", "$$${file}", "-o", "$$${file_base_name}.exe"], "shell": true, "working_dir": "$file_path", "selector": "source.cpp", }
The size will be 256 MB ? What if I wanna make it 512 MB ?
Idk how to increase it further, I've never tried it. The stack size I mentioned is usually good enough.
or just use Linux.
There is limit in Linux as well , u need to use a flag to make it unlimited
Never needed it untill now. Lesson learnt. Will take care from next time onwards.
Maybe next time on you should try helping people out with it rather than passing sarcastic comments. That is what the community is for I guess :)).
There was already a solution 2 comments above yours.
Every year, every contest hundreds of people complain to the same issue (that they are unable to read comments).
Yes we all suffer from the same problem don't we ( that people are unable to read comments).
P.S : You should have read the reply to it.
So, if every year hundreds of people complain (and i guess many others that don't complain publicly) about the same issue, maybe it could be considered to include these common problems in the FAQ? The FAQ already has "What do I need to compete?" as a question and mentions problems "line endings" and "online visibility". This could be expanded with/this could link to an technical FAQ with common problems for common languages/Compilers. Like stacksizes. Pinging LoneFox, are there some discussions in this direction? Or would this clutter the FAQ too much?
Yes, I was a bit salty that my C failed because of this, although I tested beforehand with randomized $$$T \cdot N=8e6$$$, but its ok, since now I learned about this problem. Was still an unpleasant surprise.
Thanks for the suggestion, we'll definitely consider including such information in the FAQ.
You are wrong , since I was the one replied to your comment , I read the comment above and also searched through old blogs on CF , but for Windows there wasnt a single comment or blog I found describing where to exactly add the flag , they just wrote add that flag .
You could notice that Codeforces itself doesn't have this issue and find the answer on the official technical information page.
It is really annoying when a master doesn't know how to talk in public.
For the sake of completeness I'd like to note that GCC can kind-of auto-grow the stack if you specify the
-fsplit-stack
compiler flag, — see https://gcc.gnu.org/wiki/SplitStacks There's some overhead involved, of course.Got my A2 validated, but got RTE on the main tests. Figured out it was because of the stack size as I declared the variables in my main function, only after the time passed.
Same bruhhhhhh but for A1 , from now on i will declare all arrays and matrices in global scope :(
Using vector would solve the problem. As you cant make large arrays in stack memory. So either use dynamic arrays or vectors (in c++) or global arrays. Dynamic allocation stores in heap memory in which you can take big size arrays. If I am wrong please correct me.
I believe LoneFox had made problem 1 :)
My pc too wasn't able to handle the input file as it exceeded the stack_limit. After the timer expired I realized what I could have done is declared all my variables globally. So those who have low end pc can try declaring the variables globally as it worked in my case although I couldn't submit. Hope this helps.
To all the people whining about stack size on their machine: it's not about the physical limitations of your machine, the stack size is limited artificially to prevent infinite recursion that will eat up all your machine memory (or for some other reason, I don't know computers). Yes, it sucks to learn about it during a huge competition like FBHC. But believe me, many of us encountered the same issue years ago, and at that time you had to get to top-something in round 1 to advance, which meant solving all the problems. I strongly believe that organisers consciously made inputs in round 1 big so that you can check that you are prepared for running big inputs locally in a relatively safe situation: you still have 8 hours left and some problems to solve, you still can get enough points. And it's a good lesson because in the usual competitions you also sometimes need the ability to run huge inputs locally (to measure running time, for example), so go and learn how to set the stack size on your machine (one way for g++ is already in the comments section).
Does declaring all variables globally solves the problem of stack size?
No
If using global variables reduces the number of recursive function arguments, then this reduces stack usage too. Sometimes this may be enough, but I wouldn't count on it. It's always safer to use gigantic 256M+ stacks with deep recursion.
Sucks getting segmentation fault on A2 due to memory constraints and not setting up stack size. Anyways got to learn something now from this which I never paid attention to before
IS this correct ?
I had to do
g++ -Wl,-stack_size -Wl,160000000
with Homebrew GCC on MacOS.I wish I knew this before, could not submit C in time due to this.
https://codeforces.net/blog/entry/94726?#comment-838535 try this
If anyone is facing problem with cmd, then for codeblocks link
My computer shut down and I couldn't submit A2 in time :(
Me and my potato luck
LoneFox Sir, I ran code on Dev-C++ and A1 submitted successfully. But for A2 my code was correct but couldn't figure out how to set stack size in Dev-C++.
Please give a chance to all those who did the 1st question, if you want I can send my source code for A2 to check my submission.
Also LoneFox Sir, if you keep 10 points as criteria for qualifications than we will have 9000 selections out of 12,700 eliminating 3,700.
And if you keep 24 points we will have around 7000 selections. I think giving a chance to people who didn't knew about stack size but had correct solution for A2 would definitely be a great move.
If you see previous years, then only 2k participants qualify for round2. So, 42 should be kept as qualifying points.
Anyway, B was much easier than A2 imo.
It looks like 6,809 people advanced to the 2nd round. That's way more than usual.
The problems are much easier than I expected, feels like it's another Qualification round after all.
cutoff was too low, it should have been at least A1+A2+B1 imo
Maybe this is the reason: https://codeforces.net/blog/entry/94802
We do double check all similar solutions for plagiarism after the contest ends. If there were large groups of contestants using the same code structure, they will be DQ'd.
Is plag check done as I can see everyone with score >= 24 have been registered for round 2?
I see this, so I think plag check is done.
Yep, we're done :)
No solution was plagiarized
Well that's definitely not true :)
Please, can stack size warning be put into FAQ? I remember this was an issue in the past which I fixed and then I got a new computer and forgot. Problem shouldn't be scored by who remembers best and has appropriate setup.
(Side note: I guessed the issue immediately, then I found out you can't set stack size on windows subsystem for linux, goodbye C. Don't use WSL, instead use native g++.)
You can set stack in WSL2 (you cannot in WSL1). Just do ulimit -s unlimited and it's gonna work. That's what I did.
Also I feel like people should be prepared for this. It happens every single year. Especially if you hit it before.
I hit it on a Round 3 and failed the B problem, and I knew it was only my fault I didn't prepare to have stack extra command up. So people should complain even less that it's happening on a round that only qualification matters.
I was using WSL1 since 2 required more work to install. I forgot since it didn't happen to me last year.
It should be reminded to participants in the FAQ instead of giving experienced users the unfair advantage. This should not be technicalforces or "I remember having the same issue 2 years ago"forces.
I disagree, preparation for FBHC matters, and this is one of the things you should prepare for: running your solution locally. Similarly how you have a library of pre-implemented things (that's where I store how to increase stack size for different environments).
Secondly this complain is even less relevant, as I previously mentioned, considering it was on a round that everyone with >= 26 points qualifies. This happened to people on Round 3 (me for example), when actually every point matters.
A warning to keep your limbs in the vehicle on an amusement park ride is not replaceable by a trial ride at 10 km/h where you will only get a laceration instead of an amputation
Putting it into FAQ would be surely useful. But the whole situation is really weird. People, who are supposed to be competent programers, happen to be unable to create programs that run correctly on their own computers! A wheelbarrow without a wheel.
I don't think most of "competent programmers" can install new tools within 6 minutes, so this doesn't create a contradiction
Did you never test any of your recursive solutions with max constraints edge cases on your own computer when participating in other contests?
I stopped doing that years ago, there's no meaningful algorithmic insight to learn from giant cases. I only do small cases and mental checks.
Isn’t “well, my code doesn’t crash or run incredibly slow” on max test a good enough insight?
You don't need a stack to solve it.
Just in case you don't want to deal with platform specific issues, there is a way to use allocate a custom stack on the heap, and use that for the duration of the program. I found this code in some comment quite a while back, and it works on Linux at least (it would be great if someone could confirm if it works on other platforms, although I would presume it to work on Windows/MacOS as well).
It works like a charm on windows as well.
Its really the most hurting moment when you are able to find out the logic of problem and able to code it also, but a single mistake (not putting MOD at the very end step) make your whole submission wrong.
Happened today with me (in Problem A3)
Takeaways: In problems, where we have to take mod , Don't forget to take the mod again at very last step also because putting extra mods will not create harm rather than missing single one.
...Or you could generate random maxtests to check wheither your solution processes them reasonably fast and then notice that the answer overflows. That was precisely my case with that problem.
And, by the way, "always do not forget to test wheither maxtest processing fits in time limit" was my takeaway from another failed round (it's highly possible that was a FHC round).
Thanks for sharing experience:)
How to generate random maxtests in given input format?
Can you please provide me any sources...
Here are my solutions for A2 and A3. One can see that both contain testing functions.
There are a couple of ways you can avoid falling into this pit. If you look at lots of solutions from top competitors you'll see that they use a structure called 'Mint', on 'Mod_int', or something similar. The functions +, — etc are then re-defined according to modular definitions. This means you can't 'forget' to take the mod, as it happens automatically.
My solution contains a similar idea, where I define operations add_, sub_, etc. I've pasted it here for you. I think the first way is probably neater but I developed this myself before I saw that and it works for me.
I misread problem B and though the path lengths can be arbitrarily large, but you're limited to 1000 per cell. Does anyone have ideas on how to solve this problem with modified constraints?
Like it's a bit weird since you can solve
You can't solve 4 4 8 5003 (because the right path will just go through the 1s). same with 4 4 9 5003
But you can actually solve
And also 4 4 11 5003 (just switch which numbers are 1 vs 2 in the left path).
.
I'm asking how to solve the problem with the constrains modified
.
My O(N) space bottom up solution for A2.
Also can be optimised to O(1) space easily
hey could you please explain this?
Oh Thanks for reaching out. This dp[i] denotes the number of hand changes for all subarrays ending with position i. To compute this. if the current character is F we do not need to do any computation as no hand changes will be there on reaching to i from i — 1. remember dp[i-1] already have answer to all the subarrays ending with poistion i — 1. so in case current character is 'F' dp[i] = dp[ i — 1]. else if current character is 'X' and last non 'F' character is also 'X' then also we need not compute anything as dp[i — 1] already contains the moves.
if current character is 'X' but the last non 'F' character is 'O' then for all subarrays which ended at last 'O' WE need to change the hand once thus adding the answer as index of 'O' which represents number of subarrays ending with 'O'.
There's actually a solution to C which doesn't depend on the maximum capacity being small.
As with the official solution, it's easier to compute, for each edge, how much the capacities would decrease if it were blocked. Let's sort the edges in decreasing weight and insert them into the tree one at a time. Consider an edge between $$$u$$$ and $$$v$$$ with weight $$$w$$$, and let the current sizes of the components containing $$$u$$$ and $$$v$$$ be $$$s_u$$$ and $$$s_v$$$. Then, for each edge $$$e$$$ already inserted into the component of $$$u$$$, we need to apply $$$\text{ans}[e] += \text{subtree_size}_u(e) * w * s_v$$$, where $$$\text{subtree_size}_u(e)$$$ means the current size of the subtree of $$$e$$$ when rooted at $$$u$$$. It turns out this can be modeled using lazy propagation on HLD or a top tree, as the answer is a linear function of the subtree size at any point.
The top tree is a simpler interface, as we can reroot the tree by flipping the root path (this means that we need to store two lazy-increments, one assuming the root is leftwards, and one assuming the root is rightwards).
The HLD solution is more complex, but has the same ideas. It's essentially equivalent to the top tree solution, where we follow each solution with a reroot to the original HLD root; that view can help inform which pieces you need after each update.
At the end, we propagate all changes all the way down the tree to read out the answers.
I had no idea what top trees are and decided to look them up. According to Google, Penn State is very concerned about the dangerous environmental impact of a data structure this OP becoming common knowledge:
ecnerwala Do you know of any tutorial for top tree?
There might be one in Chinese, but probably not, because they're very overkill/advanced and are essentially never necessary. HLD will essentially always suffice. If you really want to learn top tree, learn Link-Cut Tree first; top tree is a (conceptually) straightforward extension. This paper describes the standard splay-tree-based implementation: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9754&rep=rep1&type=pdf
I might write a tutorial someday, but no promises on that. If I do, it'll still assume HLD knowledge beforehand, so focus on that at most.
Awesome, thanks for the link.
I fail to come up with the way to lazily propagate push to all nodes of a connected component in HLD. Usually what I would do is to just increase all values in a subtree, which is expressed as range addition. Can you provide some insight on that, please?
How come there's a logarithm in the written analysis/editorial of problem $$$C: Blockchain$$$ ?
Editorial proposed complexity: $$$ O(N \times (\log(N) + maxC))$$$
$$$ O(N \times maxC) = O(N \times 20)$$$
The official solutions suggested a traditional sort of the edges to seed the DSU at the beginning. O(N log N) -- Radix sort could have been used to get that down to N*maxC as well, but they didn't mention that.
The whole first paragraph in the solution is unnecessary. We can just compute that while we're computing $$$D_{i, j}$$$ anyway.
whom should someone contact if he think that his output is correct but the judge has give wa verdict but that also only on 1 test case, the solution is exactly the same as given in the editorial and all the test cases are passing except 1. someone please help.
We're pretty confident that the judge data is correct. Not only do we have multiple independently-discovered judge solutions which have the same output, but we agree with lots of LGMs who participated in the contest, some using completely different approaches to any of the judge solutions too.
If you disagree with the judge data on a case, please double check your solution first.
yes it was my fault i used value >1000 in problem B which wasn't allowed. sorry for any inconvenience caused.
I thought the problems were reasonably fun. Missed C due to a stupid error (was packing fields into an int64 to speed up python sorting, and now realized that 0x3ffff is only 18 bits and not 20 bits, so I missed the 800k inputs). I'll try to be more careful in round 2.
It is showing me not registered for round 2 even I scored 24 in round 1
Will show after a few days..you will get a mail also
Guys, just uploaded approach for problem A2, you can checkout here: https://youtu.be/HWv1FWrrMj0
LoneFox Can you clarify the presentation error issue? Whenever I try to submit for practice in Round1 I always get a presentation error. To investigate the issue, I downloaded the exact file that got AC for me during the contest and that too showed presentation error, which is really confusing! Imagine getting a presentation error after solving the whole problem correctly in the real contest!
I don't know the exact reason but I want to share how I resolved this issue.
You can see the template in any of my codes and notice that I use functions to input and output variables. For example, to output, the code is like this
So what it does is that while outputting the last variable, it outputs like variable_value + space + '\n'. In codeforces and many other sites, this rarely gives me a problem(It only hampers me sometimes in very old questions as I think new checkers trim the white spaces or something, IDK), but sometimes it does WA's my code just due to this.
So I just changed it to normal
cout<<variable<<'\n'
and it got accepted!Okay, it's resolved, who would have thought that the final input of the problems gets changed!. During the contest, the final input files had different inputs and the final input files for practice submits are different!
Yup, once the contest is over we use the full input file in practice mode, which is a bit bigger than the files you receive during the contest.
LoneFox In the scorecard of Round 1 many participants are named as Unknown Competitor. Is this a bug or something, or my system hasn't loaded the site properly.
Edit — fixed.