Round 2 of the 2021 Facebook Hacker Cup is less than 48 hours away!
The round will begin on September 25th, 2021 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 24 points in Round 1.
The top 2000 competitors who solve at least one problem in this round will receive a Facebook Hacker Cup t-shirt! We'll begin shipping out t-shirts by early 2022 or earlier, at which point the winners will receive emails with tracking information.
Furthermore, the top 500 competitors will advance to Round 3, taking place on Oct. 9th. 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!
See you on the scoreboard! Good luck, have fun, and go win a tshirt!
When will the solutions to some of the Hacker Cup editions be made available e.g. 2011? It would be great if they could be added to the solutions tab just like solutions are posted this year.
Speaking of the scoreboard, we just added the ability to filter contestants on the scoreboard by country and/or by a user's name! If you'd like, you can set the country you wish to represent in your coding competitions profile.
Hey SecondThread, Could you also add the ability to navigate to any page in score board (page number feature)
You can do it changing URL query.
The country filter is really nice! However, I think selecting a country should reset the page to the first one. Otherwise, you can occasionally encounter the bug where the number of pages for the filtered country is less than your current page.
Also, one feature I'd like to request is the problem statistics (how many solved/tried a problem).
Good idea! I'll add it to the list of things to work on after we have finished up round 3! :P
Will there be a 6minute submission timer here too? And only 1 submission rule?
That's right, the contest format will be the same as for past rounds.
Hi, I am not able to update my competition profile. Whenever I click on the "Save" button, it shows a message — "Error performing query". Can you help?
We apologize for the issue, it should have since been fixed.
Can someone tell how to increase stack size in Sublime Text-Windows
I tried by this comment but not able to do it correctly ..
https://mirror.codeforces.com/blog/entry/94726?#comment-838535If you have an existing build, head over to
C:\Users\username_other_than_public_and_default\AppData\Roaming\Sublime Text 3\Packages\UserThis is my build, you can paste it and change to whichever version of C++ you prefer:
{ "cmd": ["g++.exe","-Wl,-stack=268435456","-std=c++17", "$$${file}", "-o", "$$${file_base_name}.exe", "&&" , "${file_base_name}.exe<inputf.in>outputf.in"], "shell":true, "working_dir":"$file_path", "selector":"source.cpp" }If you want to make a new build,
Tools -> Build System -> New Build System (last option)Paste the above build and follow the same process and save. Next time you build, you have to manually choose the new build, and then onwards
Ctrl+Bshould work.I created new build file and pasted your build. It is showing the error: g++.exe: error: : No such file or directory
Maybe your input file and output file are not named as inputf.in and outputf.in as mentioned in the build
semicolonised Sorry to bother you during the contest but I tried your build and changed input names too but still it show no directory found
Here is the site from where I set up my sublime text, the build is also given, I just added the stack manually. Sorry for any inconvenience caused!
Sad, I should have googled this trick earlier in the contest and would not have wasted 1.5hours debugging B trying to figure out what's wrong. In the end I changed my code from recursive to iterative out of desperation and AC. But, because of that, I did not have time to do C....
I wish I had given enough attention to this after round 1. Will never forget this in life :))
Why my input file had some stupid gibberish. I was not able to compile it.
It sounds like you're using Notepad. Notepad has this known bug: https://en.wikipedia.org/wiki/Bush_hid_the_facts
This is why we explicitly recommend against using Notepad in the contest FAQ.
It takes quite a bit of time to download the input, and i think my internet isnt slow.
Looking forward to when FHC actually employs the standard CF/CC/AC rules
Same thing happened with me man, notepad crashed when I tried opening the input file, as a result I wasn't able to submit. What nonsense is this.
See my comment here: https://mirror.codeforces.com/blog/entry/95264#comment-843301
Edit: Actually, this sounds like you may have just tried to open a large file, which is also something Notepad is really bad at.
Same. I was able to open large file using WordPad. But was not able to copy it.
Why trying to copy it? You can read from the file instead.
Yeah I did this but it was too late. I always wait for 1 min and still 5 min remains. Today even 6 mins wasnot enough for WordPad to copy file.
I later tried using Sublime Text to open the input file, the file opened, but I was unable to copy the input, selecting all the text took a really long time and Sublime Text became unresponsive. Thank you for clarifying though, my bad for not seeing the FAQs properly initially. Apologies if my message sounded too harsh.
Yeah! The point is to use file i/o or input output redirection(using either Get-Content or redirection symbols ">" and "<") and not copy paste the whole input. It is bound to crash. The only case for opening the input file is to have a look at the testcases.
Ahh I see, I'm actually not at all familiar with input output redirection, so I didn't really understand what you said :P
But yeah I appreciate you explaining your method. I can see in your above comment that you've used some Git bash commands, I'll try and learn this if possible. Thanks a lot.
Can anyone help me with the stack overflow error...I am unable to pass even the validation test case for problem B.
SecondThread
same issue
Same issue in c1, somehow manage to get rank under 2000
3rd time failed Facebook Hacker Cup(being able to solve problem).
2018: stack overflow in round 2
2020: started too late and didt pass to round 2
2021: can't copy 46mb file OMG
2022: stackoverflow because 1.5Gb isnt enough
2023: can't download input because my HDD has no 200Mb free space
Well, it was another Facebook InfiniteStack FastInternet HugeFiles Cup for me xD. Why the f**k did i wake up at 02:00 a.m. xD)))
What a shitty contest it is! So, many issues with downloading input and submitting soln files. Moreover , the problem statement for A is also not clear. Total waste of time!
Sounds like your problem, not the contest's. I found the questions to be enjoyable and the process went very smoothly. I am quite sure this is the case for many others as well.
this is a smurf account, but really had a bad experience with the stack thing even after figuring out soln in just 25 mins — 30 mins for B
Very true :))
The tasks were very pretty, and the contest was so educational. For example, I discovered that my stack size is 8 Mb) And also discovered how to increase it =). (Spoiler: pragmas didn't work). By the way, it is sad that there are so few only-output type contests, because I really like this format(.
lol
I agree; this format is very fun! This is the first contest I've done where it doesn't put me at a disadvantage to use Java.
Wrote solution for C1, submitted, passed pretests, made final submission.
Realised bug 5 minutes later while implementing C2. Compared fixed code with old code and output was greater by one in exactly one test case.
As expected, I FSTed in exactly that test case by 1. Took my rank from less than 150 to greater than 800. RIP.
(PS: I really, really don't like this format of checking. Too many ways to mess up from extracting to piping input file to stack overflows to whatnot, and the 6-minute-to-death timer for imposing this weird format)
Did anyone else used $$$O(S \cdot \min(n,m))$$$ approach for $$$C2$$$ :)
Just here to commiserate with everyone else that couldn't figure out how to increase Mac OS stack size above 10 MB :(
+1.
Does anyone have a working solution for increasing stack size on macOS?
I didn't find any useful result on basic googling.
to your compile line
https://mirror.codeforces.com/blog/entry/94726?#comment-839042
I use this flag on my macOS. I increased it to 512MB just to be safe.
-Wl,-stack_size -Wl,0x20000000
Imagine having AC code for the second problem but you can't submit because you have a stack size error in the last minute.
I also had similar issue with problem B.I converted the recursive soln to non recursive using two stacks(postorder traversal) but sadly after 14 mins contest ending.
I am new to C++. I was getting segmentation fault with recursive dfs. But I realised it after the contest that recursive function may use a lot of memory. Then wrote bfs using queue and I didn't get any segmentation fault... It's so sad :(
Can FHC consider changing the contest so that tests are run on a FB test server instead of on the contestant's computer? (Or have a validation input which can trigger max-stack-size issues?) Ran into stack size issues on B and my solution was fully correct (submitted for practice shortly after the contest ended).
Based on how many "Submission timer expired" I see on B, it looks like this was a very common problem: https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-2/scoreboard?start=1350
I am very sure that my solution to Problem B was correct But my system doesn't allow that much memory which was required for test cases. (nlogn memory).
I tried a lot to somehow manage it but can't overcome the issue.
At least you can warn about it in this blog post .
Test in D were weak, greedy (wrong) solution that fails on my tests and bruteforce for small inputs passes. Maybe it was impossible to create good tests for such problem.
It's very hard to create tough data, but I suppose how likely it is to break the greedy depends on the greedy. Also, if you shuffle the input before hand that makes it even harder for us to make you fail.
When I saw B I remembered the threads from the previous round of people complaining they couldn't figure out how to make the stack bigger in 6 minutes. (Since the stack breaking tests were in the BIG test). I was thinking people will complain again about this and was mildly amused.
Then to my surprise I see that there's actually a line test in the validation, how nice of the authors to do that, that will make people stop complaining.
Then to my ultimate surprise I come in the CF thread, and still see people complaining about the stack.
You'd be surprised how many people we had submit clarification requests saying things like "Why did you make validation data so big for problem B??? It doesn't run on my computer!" lol
do you know how to increase stack size for java? I have 8gb heap space in intellij still got stackoverflow.
I use this thing called stack trick. You can change your main method to a different method like M(), and then this in your new main method (which just wraps your old one):
Yo someone please tell me there's a clean way of doing C2 or else somebody ought to be fired from problemsetting.
My idea: you first shift up or down some number of times, then perform single remove operations on what's left on row $$$k$$$ (so same idea as C1). Let's assume we only shift up for now (down is analogous). I precompute the cost of each shift. The thing is, when shifting, in certain columns you might no longer be able to shift because there's too many cars and no room to keep pushing. Thus, for each column I compute the number of shifts after that column gets stuck and you can't shift it anymore. After a column gets stuck, the state of the $$$k$$$ th row will no longer change.
When we introduce spells, changing one cell only affects that column. Specifically, the number of shifts at which the column gets stuck could move up or down. So we use sets to find that, and range update operations on a segment tree to change the cost values.
Thing is, this is way easier said than done because there are quite a few cases to consider, and my implementation ended up being disgusting. Here's the code, don't even bother trying to understand it lol: https://ideone.com/iv4U5d
EDIT: Ok there are definitely cleaner ways of implementing C2. I still can't say I like the problem, but I'll cool off on it.
We don't need to shift more than min(R, C).
Agreed, although that's the change of one constant in my code.
So just do brute force, only need to consider rows [k — min(R, C), k + min(R, C)] and maintain fenwick tree is enough.
Do you mind sharing your code?
https://ideone.com/D6QNxt
Oh never mind I see what you mean, $$$\min(R, C) \leq \sqrt{RC}$$$, so just naively doing it is $$$RC \sqrt{RC}$$$.
Yeah I also was trying to code that solution, mine was a bit cleaner but also didn't manage to finish it in time. I was using M fenwick trees to calculate blockage, and then one interval tree to compute best rotation.
One way you can cut your code in half is just write code for downward, then reverse all column in M, and compute again but for K = N — K + 1.
Ah that's a good point, I was in a rush in contest and just copy pasted the whole thing again.
My implementation. There are a few cases, but in general I think it's pretty clean.
Looks like we had very similar implementations, down to the quirk of using both a segment tree and a Fenwick tree :P
Couldn't complete this mess up in time though :(
I think there's a pretty clean way, plz don't fire me :)
There are only a few squares in a column that might change. In particular the first +/-5 things in a column and the last H-K +/-5 things in the column. Sure, you can case all of that out, but that sounds annoying. Instead, why not just remove all of their contribution to the answer, add the new space in, and then add their new contributions back in?
Lol you only shift up or down at most $$$O(min(n, m))$$$ times, so you can replace segment trees with for loops and array
Others already mentioned the $$$min(N, M)$$$ observation, which makes everything much easier.
But I didn't have it, and my code (with the approach very similar to yours) looks manageable: link.
What are the cases to consider? What I did was: For each column we count cars, from top to bottom. The moment we got at least $$$k$$$ cars, we fill the remaining places downwards with virtual cars. I also add an additional row at the end with no cars, it will only virtual cars (this removes the case if we push cars as much as possible). Now I check all rows $$$k$$$ to $$$r+1$$$ for the sum of cars/virtual cars they have plus the distance to row $$$k$$$. The minimum sum is the answer.
Here is my implementation: https://pastebin.com/QJSdbs87
The main logic happens in Lines 353-374, which is pretty short. I think this has a very small amount of case work here.
For the other push direction I just turn the parkings around and repeat everything (Line 332-341).
For the spells I use segment trees. A Minimum-Tree to find the answer, and $$$c$$$ trees with range updates but only point queries, to manage the virtual cars. (line 391-404 and line 408, 409)
I didn't use $$$min(R,C)$$$ as the minimum amount of operations needed.
Huge congrats to Radewoosh for clinching Round 3 fourteen seconds before the end of the contest!
Seems there are a lot of possible solutions for B.
Mine is to just count the number of bridges on the tree but add a long cycle for each of the same frequencies, which I found very interesting.
I tried the same thing but didn't have enough stack size for the main tests :(
You can also count complete subtrees(ones where any node $$$n$$$ with a distinct color contained in the subtree, $$$n$$$ is also present in the subtree) then combine the sums from children with small-to-large merging.
Similar problem: Link
My Solution: Get LCA of all nodes v having same frequency. for ewach v,LCA pair do sum[LCA]++ and sum[v]--. This will activate edges between v,LCA
Do simple dfs by adding sum[i] to curr at each point and when cur = 0 increment ans. O(NLogn) time, O(NLogn) space
Yeah I did something similar. I constructed a graph with the following bidirectional edges :
A. Real edges given in the input
B. Edges from vertex i to i+N
C. Edges from vertex i+N to j+N iff i and j have the same frequency.
Now if a1,a2,a3..ak have the same frequency, only connect a1-a2,a2-a3... So that there are O(N) edges of type C. Aka construct trees of same frequency.
Now just find the bridges of the graph in O(N+M), [M = O(N) here] and only add the bridges which are real edges to our answer.
My approach (couldn't finish in time though) For each frequency, calculate the first and last discovery time of any node having that frequency and also the in_time and out_time for each node. Now for each node excluding the root, the condition for the edge between the node and it's parent to be removable is that there should be no frequency for which the interval [first_discovery,last_discovery] intersects with the interval [in_time,out_time]. This can be achieved using 2 segment trees and binary search.
You can actually check if there are any intersections without segment trees and binary search.
Let's observe that for each node U the edge between U and its parent being removeable only depends on the frequencies that occur at least once in the subtree of U. We're not able to remove the edge if there exists any frequency F in the subtree of U such that first_occurrence[F] < in[u] or/and last_occurrence[F] > out[u] , So all we really care about is minimum of first occurrences and maximum of last occurrences of all frequencies in the subtree.
This can be done pretty easily in O(n). you can check the code here.
Let $$$S_x$$$ be the set of all vertices $$$u$$$ such that $$$F_u = x$$$. We want to add a path from each element of $$$S_x$$$ to the LCA of the set. Just compute the LCA and for each $$$u$$$ in $$$S_x$$$ go upwards connecting $$$u$$$ with each element you find using DSU, stop when they are in the same component. To guarantee it will work you need to eval $$$S_x$$$ with lower LCA depth first.
why hackercup can't follow similar format like google codejam ? why this 6 — min timer and output file upload shit ?
Why GCJ can't give us a multiple-choice test with a/b/c/d answers instead of this coding shit?
TFW you attempt to solve C2 by writing code for the case where you shift cars up, then flip the board and run it again, but you forget to flip the updates too :(
Well, that was fun, thanks! :) Adrenaline. I guess Radewoosh has the same emotions :)
Screencast https://youtu.be/nGCeL0y2T1Y
Here's my heuristic solution for D. (passed 5 minutes after the contest end)
I want to focus on two types of elements. The first type is those that are not divisible by a number that is a divisor of many elements. The second type are elements that are far away from other elements (like 500 in a sequence 1, 2, 3, 500, 1000, 1001, 1002).
I put aside top elements of those two types. Greedily assign all the remaining elements. Then run knapsack on those few special ones.
Iterate with $$$T$$$ from 0 up to infinity. Try $$$T$$$ elements of first type, $$$T$$$ elements of second type, then $$$T/2$$$ elements of both types at the same time.
This way, I didn't need to hardcode any value.
Anybody sees a way to break this solution?
D: If we have a set of $$$K$$$ numbers such that max number is $$$M$$$, and $$$2^K \gt K*M $$$ then we can choose two non-empty subsets with the same sum (pigenhole principle, pigeons <- subsets, holes <- sums).
For M=200000, K=23 works.
If N is small do bruteforce, if N >=25 it is always possible.
Use the following schema again and again:
1. take 23 smallest or random (both seems to work) untaken numbers
2. start generating subsets and computing their sum (stop when you detect two with equal sum).
Why does it work fast enough though?
My intuition is the bday paradox. Usually you will need around 10 elements or less to find some subsets with equal sum. So this will be around 1024n ops.
You can have a stress test for small set of numbers like 1,2,4,...,2**17 but good luck finding one with 200k numbers.
These problems are good, but I just blow it in this round.
Problem A is my nightmare, I tried to implement it by DP, but failed from time to time. I then jumped to problem B, but cannot find any hint.
After one hour and half, I found I can use greedy in problem A, then I move back to A. However, there are two bugs and miswriting in my code and it spend another hour to correct it.
I submit the answer 2 hours 30 minutes, and I move on to problem B, but still cannot find any hint. Finally, I find problem C1 are much easier, so I jump to problem C1 in last 20 minutes. I thought I must do it before the end of the contest, so typed very fast, and made many silly mistakes.
When I correct all of the mistakes and try to download the full input, the contest has ended 5 minutes ago, and my final ranking is 2700+, a result that cannot even win a T-shirt. My answer just get accepted in the practice mode. I cried at last, very very sadly.
I really cannot accept my current result, I am too nervous, and I think I can do better. In order to prepare for this contest, I practice nearly every past round 2, and can pass most of them.
The most reason I failed in this contest is that I was too eager to win, since Facebook is my dream company and I want to behave well in the contest to get an interview. I am about to graduate this year and looking for jobs afterwards. That is my main reason. If I just do for fun, I can behave much better.
Afterwards, I need to move on, and delete my hacker cup experience in my resume. Thanks for this contest, I find so much to improve.
I don't want to rub in your feeling but how well does one need to perform to get an interview? I'm still assuming that these results don't matter much unless you get all the way to the onsite finals.
Last year, all T-shirt winners received an invitation in the T-shirt email to submit a resume/request more information on jobs at Facebook. I don't recall receiving any additional recruiting-related communication as a finalist (though I could be mistaken), but obviously, I can't say with any certainty whether finalists were prioritized for interviews/opportunities at Facebook in general.
Cheer up! You don't need to be top 1000 or get into round 3 to get into Facebook. The correlation between interview result and codeforces rating is not linear and tends to be less as your rating rises
during this round i dowloaded input file to submit problem A but it contains wrong words not test cases and my time is expired, but after the round ended i download this input again but it contains correct format of test cases ,why this happened to me ??
I don't like the statements. I hope they will be shorter in further rounds.
A is unnatural and difficult to understand.
B is very long. In particular, why do you need this paragraph in the middle?
Mining is a dirty business, and not just among blue-collar workers. Executives of a new mining project are plotting to sabotage their rival company's presence in a given town by disrupting its transportation operations. However, in trying to actually build the blockade on the aforementioned roads, their plan was foiled.
I would appreciate the diff between C1 and C2.
Finally, D is such a cute problem that you could describe in one paragraph... and you butchered it with an unrelated story. Making a nickname-related pun isn't cool if the original problem had nothing to do with it.
In the solution section of C1. There is a sentence "It cannot be better to combine both upward and downward shifts, nor to perform car removals before the desired shifts are done.". I think to combine upward and downward is possible to be better. For example
*X*X*X*X*X*X*X*X*X*X*X
X*X*X*X*X*X*X*X*X*X*X* // this is the k'th row
XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX **********************
We need to free up the second row
In this case one upward and 2 downward is the better solution. What do you think?
Two downwards alone is better than one upward and two downwards I think
Oh I see, I misunderstood. Regretting
Thanks to authors for the contest!
Plus, thanks for maintaining a non-mainstream format, and working to improve it on top of that, like validation and pre-downloading large inputs.
Advancing to Round 3 (ranking 201~500) doesn't matter if you won't qualify to the finals. Change my mind.
It matters a little then?
Oh you're right. My point still stands for those who ranked top 201~500 though lol
It's in round 3. So everyone (even 201-500) get a chance at a better tshirt
Ooooooooh. My dumb ass read that as top 200 in Round 2.
Last year, there is no "top 200" in my "top 200" T-shirt.
Just a small suggestion: Show the number of test cases in input files so that I don't have to open large input files just to ensure that my code runs on all the test cases.
You can output it in stderr.
EDIT: Fixed, turns out the input is randomized each time
So happy to get a T-shirt in hacker cup. It's my dream since I started to learn CP last year. (＾ω＾)
Those with ranks 501 and 2001 would be so happy.
501th would be unhappy for sure.
@Facebook Hackercup admins please disqualify the people who have not written a single line of code in their source code and just submitted the output file in both source code and output files. Like the person now ranked 1490 has not written a single code in his source code. Pls look into this matter and disqualify these type of people.
SecondThread, LoneFox, wjomlex please look at the above comment by 10_11_12.
Thanks, such competitors indeed get disqualified.
My rank with 10 mins left was 1900 something and seeing the rate at which it was increasing I was worried ill miss the cut by just a bit, with this motivation I debugged my C1 superfast and submitted it with 5 mins left on the clock. Felt extremely happy to see both passed and even more that I've won the T-shirt with a final rank of 1405 !!
Also, when will the T-shirts be shipped, I am too excited to wear it!
I solved problem B in a different way: Do an Euler tour (single occurring). Now your aim is to just count the number of such nodes whose subtree contains all the occurrences of a certain value,i.e., no value should be there which is in the subtree and outside that subtree as well. Subtree denotes a subarray of the flattened tree. Hence, you will have n ranges to query for and for that you can apply Mo's Algorithm to compute the final count of such nodes.
Time Complexity : n3/2
Code : https://ideone.com/hlTvaM
That's a cool idea!
In your code: you can also do updates of "moving L, R boundaries of [L, R] interval by +/-1 and maintaining array tot and variable cur" (using your notation) with this helper function:
and using it by calling
update(what is a[freq[EITHER L OR R]], delta is EITHER +1 OR -1, curr, cnt, tot);Oh yes, Thank You!
I did something for B that i havent seen and i think it was a cool solution
Basically i used DSU on trees, so for each node i had the number of times each frequencie appears in its subtree, and i also had two more values: how many different frequencies the subtree has and for how many frequencies of that subtree the number of times it appears in the subtree equals the numbers of times it appears in total, finally to delete an edge coming to the current node from its parent you need these two values to be equal, because it means you are not separating any two nodes with same frequencie.
Does anyone receive an email from [hackercup2021-33527 at eventsatfacebook.com] about job opportunities? It requires me to login into a strange website so I don't know if the email is legitimate or not.
That email is indeed legitimate, thanks for checking!
wrote about my experience in hacker cup 2021 in this medium blog article: https://shadek07.medium.com/facebook-hacker-cup-2021-experience-519f594bec7e
What will be the inscription on the t-shirts? "Facebook Hacker Cup" or "Meta Hacker Cup"?
it's "Hackercup"