The Qualification Round of the 2020 Facebook Hacker Cup is less than 48 hours away!
The round will begin on July 24th, 2020 at 10am PDT and will last for 72 hours (3 days). The contest can be found on Hacker Cup's new competition site.
Everyone who solves at least one problem correctly will advance to Round 1, which will take place on August 15th. 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. Starting this year, you may also choose a Display Handle for yourself there, to be displayed alongside your real name on scoreboards.
Look out for an upcoming announcement regarding this season's prizes as well!
We wish you the best of luck, and hope that you enjoy the contest!
Update 1: Facebook post announcing greatly increased cash prizes for 2020 can be found here, with more details available in the FAQ!
Update 2: The round has ended, thank you for participating! The scoreboard can be found here, and the solutions here.
Wait, There's no partial verdict? Like pretests passed?
There aren't partial marks nor an exact equivalent to Codeforces' pretests. However, starting this year, there is a process of validating your solution before making an official submission, which is like a cross between sample data and pretests. There are more details in the FAQ, and you'll get to try it out soon during the qualification round.
Excuse me, but can people below 18 participate in the Qualification Round?
Yup! You need to be at least 13 to have a Facebook account, so 13 is the age requirement. Due to legal issues around travel (not this year) and taxes (every year), you do need to be at least 18 years old to participate in the Final Round.
Thanks!
Yes,they can. :)
Time to create facebook account
Do we still have a 6 minute window between downloading test case then submitting our program?
Yes. To know more, just visit their facebook page, and click on the FAQ!
Hi. I don't know if this is the correct place to ask this: I permanently deleted my Facebook account because I rarely used Facebook and I thought that I wouldn't need the account anymore. But now I want to participate in FBHC but I couldn't use my name or original email to sign up for a new Facebook account. Everytime I try to create a new Facebook account, I always receive this message:
Does anyone know how to resolve this issue? Is there any alternative rather than creating a new account with random name? (I couldn't open the FAQ because it requires me to login through Facebook)
Edit : I have not ever done anything that violates Facebook Community Standard (only account deletion which I think is a normal thing to do)
You can make a new gmail account and use it to make a new Facebook account to participate with
Thanks. Actually I had already tried this, but Facebook somehow knew about the new alternate account and I received the Disabled account message again.
It will be removed once you verify your phone-number
If I tried to verify my original phone number, Facebook will say that my number has already been used to verify another Facebook account. (and that is my real account which got disabled)
alwyn, please email hackercup@fb.com with your Facebook account name, and we can look into your case and hopefully have your account be re-activated. Thanks!
I am having same problem, but don't think I ever made an account before. Tried with two different emails. Now three. Also cleared cache and stuff.
I tried signing up for a new account on my phone, using my mom's phone number and fake birthdate, and it works (I didn't use a fake name though). After signing up, I logged in on my laptop with the new account and everything seems to be working.
Before trying this method, I have tried the following methods and all of them failed:
Signing up using real name and birthdate, but with different email. This didn't work. Maybe because the name and birthdate are exactly the same with my disabled account's name and birthdate; and the email that I used to sign up, contains my name on it. (eg: fullname@gmail.com and fullname1998@gmail.com)
Signing up using my real name, real birthdate, and my dad's phone number. Still didn't work.
Fake name, fake birthdate, and my sister's phone number. This initially works, but after successfully signing in to Facebook, I changed the name and birthdate to my real name and birthdate. And I add a new email to the account, but this time using my university email. But around several hours later, the new account suddenly got disabled again.
Edit : I also cleared cache and saved passwords before trying each of these steps
SuperJ6, please email hackercup@fb.com with your Facebook account name, and we can look into your case and hopefully have your account be re-activated. Thanks!
I think this facebook way of telling you "Ohhh so now you need me. Where were you when I needed you!". Facebook is showing ego.
I would be really grateful if someone can explain clearly, the submission process in facebook hackercup? I am unable to understand it from the internet or the FAQ
Just try it with the archived problems. In C++ you are changing from reading and writing from standard input/output, to reading and writing from/to a text file. Then you submit the text file.
I have solved one of the problems and also downloaded the input test file . But what to do after that?
Run your program locally (on your laptop/pc) with the input from the input file, save the output of your program to a file, and upload the output file.
Thanks.After reading this, I added those lines, compiled and ran the program. Cmd doesn’t take input from me and neither terminates. Checked the output file and it is showing some random output for all test cases. Even though, input file had only about 1350 test cases , output file is showing much more than that. What could have gone wrong?
Maybe your solution is wrong? Hard to tell from the distance. Post your solution on ideone or pastebin, and I'll take a quick look.
Here it is.
That's not how file I/O works.OK, it works — I confused it with some other function. Thanks for the correction, Jakube.Anyway, don't do file I/O at all. Just write a normal program as you would for Codeforces problems, and when executing just do
./a.out < name_of_input_file.txt > name_of_output_file.txtWorks on both Linux and Windows (replace
./a.outwith./a.exe) .Well, actually it can be done like that. I don't like it either, but it works.
And on Windows it's probably
a.exeinstead of./a.out.Thanks, edited.
I just wrote a simple program without File IO, and uploaded that as source code. Will that work? Or should I use File I/O for other questions?
Yes, for source code simple program will work. As long as your output file is correct, there should be no issue.
How are you running the program? What do you mean with random output?
I just compiled the program, and ran it with the input file (1050 test cases), and it outputed 1050 results. Everything worked, and even submitting the
output.txtworked.I figured the problem. I changed the file name from "leapfrog_ch__input.txt" to "input.txt". It worked and got accepted. But I don't know how that made a difference.
I think your code gives wrong o/p in 3rd case in sample test case
It gave correct on my mine and also got accepted. So, I don't know what you are talking about.
Same problem is happening with me what to do ?? even for running hackercup how to generate output file without problem..I am using Dev Cpp
Copy those lines inside the main function from link I provided above in my comment if not already done. Download the input file and put it inside the folder where all your programs are saved. Compile and run. Your folder should have the output file with the output of your program. That's all I did and it worked in gvim. Should work for dev c++ also.
can you help i am getting Presentation Error while validating output file
i have taken simple input and output simply by print(ans) in python
Did you add the text "Case #(test case number):" in your output?
i have tried after adding test case no it is giving (presentation error) then also ex. my 1st try :
YY YY YY NY my second try: Test: #1 YY YY Test: #2 YY NY
The output should be exactly in this format: Case #1: YY YY Case #2: YY NY
Please observe the output format. It should be like this Case #1: YY YY
should be new line after ":"
in clear words output must be in exact format as provided in sample test case on site. example:
Case 1#: NN YY
I don't think it is necessary to read input from file and write output to file, we can simply paste input in input box of IDE and after running the program copy the output to another file.(Should I read input from STDIN or from a file? Should I write output to STDOUT or to a file?)
That’s true, but my laptop sometimes crashes with large output or even just copying to the clipboard
I submitted with standard IO and it validated. Should I resubmit with reading and writing to files?
No you don't need to do that, you can read the input either from stdin or from file, it doesn't matter, they don't run your code, as given in the FAQ.
i use this in my cpp code, and it cause compilation error on some judges. Will this be a problem on hacker cup?
No, it should not, as I said they only check the output text file, they don't run your code, just check it for plagiarism.
Hope, there will be no karangreat234 in this round
I keep updating the display handle but it always resets to nothing whenever I check back.
Are you clicking the Save button below after entering your Display Handle? If so, is it possible that any error is showing up when you do, for example due to an invalid phone number or other field? Thanks!
Yes, my phone number is blank, do I have to put it in? My facebook account was registered through referral so it has no phone number.
Leaving a blank phone number is fine.
But it won't let me click Save.
For the record, this has turned out to work after all.
Oops looks like I missed the round.
Not anymore, we've traveled back to the future of 2020 :) The post no longer mentions 2019, thanks!
Is the system of checking solutions to codes similar to that at Topcoder in Facebook Hackercup?
You'll need to write code to solve similar sorts of problems, but differences include the fact that you'll need to write a full program capable of processing input/output and execute it yourself. Please see the FAQ for more details, and consider practicing on past Hacker Cup problems to get a sense of what the system is like.
I have a couple of questions:
Does the time penalty of a round affect the qualification of the rounds other than the next? For example, does the ranking/penalty from round 1 affect qualification to round 3?
Is it possible to get TLE?
$$$ $$$
Can I deactivate my account after I'm done with the contest?
Petr does it every year
Maybe he isn't happy with his rating :D
I don't get it what the hell just happened?? I downloaded the input.txt file for D1 and funny I wasn't able to read the input... Refer this screenshot
Does this mean I won't be able to submit solutions having input files of similar size using current lappy?? Tagging LoneFox
Does the file look OK in a different editor than Notepad? I saw somebody else with the same issue, but it was a file they had created and then opened in Notepad. When I viewed it, it was fine. I think there are some encoding settings in Notepad you can play with as well.
I think there's a problem with the text file downloaded as I tried viewing the file on different editors and even systems ... but dint work out!! Most of them stopped working and so I am in a dilemma of whether to submit D2 or not?? It worked just as fine till C but again the dataset size was smaller for A, B and C
Please send us a clarification with the file and we can discuss further.
Actually I tried uploading the file in clarification but showed memory limit exceeds 200 KB....
I faced the same problem. The downloaded input file consisted of all those weird characters, and thus I couldn't run my program. Eventually my submission timer ran out and I can't submit anymore.
I also faced the same issue. Quite frustrating it was!
In problem C , can there be multiple trees at same position ?
Read the problem more carefully.
What does wrong answer indicates in validation phase ?
It means your solution to the validation input was wrong.
Can it be because of error in format ?
Nope. That yields presentation error.
I have one serious doubt- Should the code I submitted also read a file and create a new output file if they will run my code on another testcase or just it should print output like Codeforces or Both or doesn't matter. Anyone please? Actually I have submitted the code that read a input file and create a new output file. Have I submitted it wrongly?
Either is fine, as long as your submitted source code is what you used to generate your submitted output.
What if I used a different filename for input.txt? For e.g. the official filename for the test-cases is input.txt but I take the input from, say, txt.in in my program.
EDIT: Nevermind, I saw the FAQ, it seems this is fine.
Look like you really need a fast enough network because the counter countdown while you downloading the testcase. I failed problem C because I couldn't download the whole testcase in 6 minutes, crazy contest.
That's unfair. Maybe Facebook should improve the way to submit the solution.
If you have any trouble during the contest, please send us a clarification and we can help. We do try to keep the input files as small as possible without sacrificing the integrity of the data.
We hope to move to a format where we actually execute code for next year which will solve this problem once and for all.
Yes, please make it like other coding competitions.
Thanks for your reply, I'll try to send a clarification later. And it's really a good news if the contest run like other platform in future.
Noooo, FHC is the last big contest with this unusual format, which sometimes forces you to look for a bug quickly in that 6-minute frame because something crashed or it's too slow. Don't make every contest the same :(
+1, Google Code Jam lost a lot of its appeal to me once they changed the format to be like every other contest :(
Ah, these are both interesting opinions, thanks for the feedback! We'd be interested in hearing any other things that you like about the current format compared to a more "normal" approach.
The current format does have some downsides such as
limited data size
a general concern around unfairness re: different hardware and internet stability
time spent fiddling with files instead of coding
I liked old Code Jam format because it allowed to have some fun.
Like submitting everything in Excel.
Or racing for the top of languages used leaderboard (hard-core players would deliberately fail Rounds 1A & 1B to get more languages in).
Or just looking at what crazy languages did people use and their submissions.
Or just solving the problem in two parts in two different languages if you really wanted it (say in the first part you wanted to use C++ STL, but for the second part you wanted to use Python long arithmetics).
Or if you really need it, you can even use multi-threading to get just a bit more performance.
The current format doesn't limit you in anything, it's basically just use your computer to solve this problem, in whatever way you want without limiting your tools in any way. When Code Jam used this format, it had this unique feeling for it, which it lost when it became exactly like the other contests. Which in my eyes, was a shame.
The biggest downside to this format I see is Internet stability/speed. But that can easily be addressed by distributing tests in advance in a password-protected archive. When the you start the timer, you could just reveal the password. IPSC has been doing this for years.
As somebody who's solved some GCJ problems in non-standard ways, I definitely understand where you're coming from.
It's possible of course to combine code execution with the same "one-shot" approach. As a random idea, imagine getting full feedback (we tell you whether you got AC/WA/TLE/PE/RE), but if you don't get AC the first time, you have 6 minutes to try to get AC :)
Open to suggestions!
What would TLE mean here? Bc what if my solution is actually supposed to take approx 3 minutes (bc my mind is small and I can't come up w/ intended solution). Then how do I like avoid the TLE verdict. Also maybe some progress bar showing time left on cases would be good (if we're submitting to online instead of local). Finally, maybe don't include AC or WA. Only the other answers, bc well that's another added layer abt this contest -- we don't know if sol is correct till grading. Tagging Errichto, eduardische, and ffao from above thread for their much greater experience than mine.
Please do so. My computer got a blue screen when I tried to submit for Problem C (I was copying and pasting to stdin which I probably shouldn't have done). Nevertheless, I ended up missing the submission window which was a bit disappointing.
If I needed more than 6 minutes to download 30MB, not advancing in FHC wouldn't be on top of my life issues list
B
Fullmetal Alchemist fans LMAO
Seeing that reference was nice :)
I have a question: I didn't add
#include <string>in my source code submission for problem A because it is not necessary in my computer, will it be ok or it will be Compilation Error ?We don't run your source code. It's used for plagiarism detection.
If you don't run our code then what happens if instead of submitting code I submit something else like anything. wjomlex
Just because we don't necessarily run it doesn't mean we don't look at it.
But how it can be done without running the code on test cases to check whether it is the valid code or not?
They look at the code without running it as a cheating deterrent to try and make sure that you coded the solution on your own.
Ok, but how they know that this is the valid code for the problem without running it on the test cases of the problem?
They trust that there are a strong number of test cases that will close to guarantee that your output must be valid, just like CodeForces, they just allow you to run the code yourself and self report. They also give each participant a subset of the test cases and enforce a 6 minute window to inhibit sharing of output.
Is TLE not possible in the qualification round (if I managed to submit the output and source file within 6 minutes timer) ?
The problem description doesn't mention time limit at all.
Nope, as we don't run your source code.
Does that mean the final grading input file is all the testcases? There won't be any new hidden testcases?
Almost all of the cases. Everybody gets a slightly different subset of the full set.
do we need submit source code in text?
in which extension we submit the output file,i have tried in .py extension but it gives invalid file based on the extension(.py)
both code and output should be in plain text.
as seperate text files or in same text also in which order?
for validation submit output and then for submit, submit output and code separately
Why do facebook keep 6 minutes window? How does it help?
I think it is for stopping bruteforce approaches. I mean if u consider the 72 hours window, you can easily have the time to run an O(N^2) solution which gives correct answer.
Everyone who solves at least one problem correctly will advance to Round 1Does that mean I will surely qualify if I solve only one problem? Is there any benefit of solving more than 1 problem other than improving rank in the leaderboard.
There's no benefit of correctly solving more than one problem. U will qualify if u just solve 1 problem.
thanks
There's always the benefit of personal growth and learning :)
Given that you don't know whether the solution is correct before the end of the contest, I'd say there is a pretty big benefit. No one wants to miss FHC because of a silly mistake in the only problem you solved during qualification.
Yeah, this is a huge benefit. :)
I think there should be a change in way of submission.For C and D1 and validated my code, but couldn't submit in time, just because wasn't able to download the file. It's unfair. No motivation to try D2 and fail again.
This really very frustrating I solved C and when I downloaded the large test file my computer froze and I was not able to submit in time and now I cannot submit, it really feels bad
May be your code complexity is too high and it's not able to produce output for large text file within less time.
I didn't even get the chance to run my code , my PC froze while I was setting up the input files
shouldn't the submitting time be more than 6 minutes. I solved D1 but couldn't submit in time as it has taken more than 4 mins on my local machine.
If you can't submit in time, because your program is too slow, then you shouldn't receive any points. It's the same as on any other online judge, on which you would receive a TLE.
Any problem (at least in the qualifying round) has a solution that runs in less than 10 seconds. Together with the overhead of downloading and uploading, you should be able to submit any problem with 5 minutes still on the clock. 6 minutes is really generous.
I created a new FB account for Hackercup. But it keeps getting disabled. I uploaded my phone number to get my account activated 2 days ago. Today, my account got disabled again and it is asking me to upload my photo. Is this happening with anybody else? And is there no other solution than to create a new account everytime this happens?
I also get the same issue.
I think this is the issue.
For people too lazy to click on the link, this is what that comment says : I believe FB wants only users that actively interact with the cashcow: marketing, or bring other users that will. Accounts created solely for the purpose of competing once a year, with no indication of engaging in regular social media activity (or even worse, with adblocks) don't fit there, so they're promptly autoblocked as "suspected bots". Getting people to give FB extra private info to sell is just a bonus.
This is why FB keeps disabling new accounts with no activity.
mayurmaga, please email hackercup@fb.com with your Facebook account name, and we can look into your case and hopefully have your account be re-activated. Thanks!
Can we have different login-registration process for FB hackercup from next year onwards? Something independent of FB profile. I think lot of people (including me) are either creating new account or enabling disabled account they don't use anymore.
Can anyone please clarify my doubt regarding time limit for running of a problem. Like in codeforces for some question it is 1 s and for some it is 2 s as there is no mention regarding this on the hackercup's problem page.
Everyone who solves at least one problem correctly will advance to Round 1Does that mean I will surely qualify if I solve only one problem? Is there any benefit of solving more than 1 problem other than improving rank in the leaderboard.Improving your skills?
That's fine but I was quite busy this week, so I am afraid I won't be able to devote time to all the questions. That's why I asked...
You will surely qualify if your submission is correct, which you will know when the contest ends. But i do actually recommend solving other problems, other than the first one, they are good for practicing for next rounds of FHC.
OK thanks, I'll do that
Are there any constraints on the time complexity of the solution? For example here on CF. I can get an idea that expected solution should be in O(n) or n(log(n)) or so on.
Problem C input file was big (>27mb) that it took more than 6 minutes to download it with my super-fast internet speed. Yikes!
Same thing happened with me. I think I had the correct solution for C, but my internet betrayed me T_T. Now I don't have the will to do problem D.
Facebook should have some mechanism to start the timer once the input file has been downloaded.
It seems practically impossible for them to check if the file is downloaded or not unless we have some browser extension. But I think they should avoid big files (compressing?) or find another solution. People with slow internet might lose significant time (big disadvantage) because of that.
On top of that, someone who has a poor internet and a slow machine is at a significant disadvantage. It feels bad not being able to get an AC because of such reasons.
Another issue is that someone might have power/internet loss for some minutes. I'm sure these issues are already discussed, but I like the idea of having password-protected zip files as inputs, and the timer starts when you request the password.
Adding another Pre requisite for hacker cup in FAQ
) Good internet
Does validating solution also tell us if our code gives correct output on the input file? Might be a dumb question to ask but this was my first HC and I have never participated in codejam.
Well, where are the time limits? :3
Since they only check the output file. I think that only thing that matters is if you can get your output written to file and submit it in under 6 minutes.
LoneFox Sir, I ran into a problem during the Facebook Hacker Cup. I validated my solution on Problem D1: Running on Fumes — Chapter 1. However, when I downloaded the final test case, the text file was filled with random characters as below,
input file
So I ran out of the 6 minutes time in which I was supposed to submit the output. I would request you to look into the problem, and if possible, restore the access to that problem. Thank You
I had the same problem. By the time, I copied the input,time had run out.
I faced the same problem.
The issue was resolved after I sent a clarification with sufficient proof.
I asked for clarification and attached a screenshot of those random characters.Do I need to do anything else?
Wait for them to reply.
Where did you send it ?
Go to the clarifications page and request a clarification.
can anyone tell me why it is showing presentation error ? how should i print the output ?
Look at the sample output.
thanks , got it
anyone had problem with stack size in d2?
I did. It was a nice problem, would have loved to get AC on that. :(
Same lol. What's the g++ compile flag to increase stack size?
I don't know. I was not in a very good mood. Haven't searched yet.
https://mirror.codeforces.com/blog/entry/60999?#comment-449312
Also a bit more about it here but apparently the link isn't working for everyone.
Thanks, that worked.
Also for ppl
who are too lazy to click the linkunder a 6 minute time crunch, here's the command:g++ -std=c++17 -Wl,-stack_size -Wl,0x10000000 main.cppany idea how to increase stack size in sublime Lol, it took me one day to come up with the solution and still not able to submit it. But learned something new
Edit: I guess will need to use terminal for this
ulimit -s 1000123in ubuntu. Or you can do it at the beginning of main() in C++ as described hereulimit -s size is going to work for only one login session. For most computer i guess default stack size is 8mb. I changed the default size from 8 mb to 1 gb at /etc/security/limits.conf
I did said changes to /etc/security/limits.conf and it somehow broke my chrome :( had to revert it.
Please add this to your linux setup wiki.
Same happened to me... It irritated me a lot .. Wtf it was
I personally think that it is unfair ... I was so happy on solving that problem .. Only dfs and bfs(it would be iterative and therefore pass) made a difference
Suggestion: have password-protected zip file. Contestant downloads it, and then indicates he would like the password. Start the timer then.
Password protection is very good idea, but zip protection is not that secure, I have used some tools(2 or 3 years ago),which are easily available on internet for bypassing security and unzip/unrar password protected files.
See: https://security.stackexchange.com/questions/33410/can-password-protected-zip-files-be-broken-without-brute-force
TLDR; long, random password with non-ancient encryption cannot be cracked easily
I guess then, I might have done it for weak encryption system, hence I could got access to inner contents.
Hi.In problem D1, I tried running my code locally on large input file(~11MB) but my PC froze and I had to forcefully shut it down.By then, the submission time of 6 mins had already expired.Is there any tool using which I can run my codes on large input files online? Thanks in advance
Sounds like you used too much memory (too big memory complexity), and you ran out of RAM. That usually also means that your runtime complexity will be to big, and your program will not finish in time, even if you rent a server with >100 GB RAM. You need to improve your solution.
This is weird testing. In D2, my local system got hung on this large input. And timer expired. -_-
Same thing happened in my problem C. Input file was 30mb. Downloading it took 5 minutes. After running it my local system got hung on this large input :/ I mean why can't they have a system similar to Google Codejam for example? :/
Same here buddy I lost my motivation to solve any further after I failed to submit C in time, I wonder if our job is coding or testing
If you're not talking about downloading speed, most likely your solution was just not efficient enough. Treat this as TLE or MLE in a normal contest.
Actually, I think my time(and memory) complexity was well enough to fit in a reasonable limit. I guess allocating a huge memory(something like 300MB) caused an overflow in local system.
But sir what about dfs_stackOverflow .. there's no point of judging solutions on the basis of this ....
then increase your stack limit
Yup I did it now
Can you tell me how to read a large input from a .txt file and outputting in some other .txt file? I tried but i could not read more than 1e5 words.
Same here. My stack was not huge enough to work with a graph with $$$10^6$$$ nodes(
Increasing the stack size didn't help, so sad
After the 6min timer I replaced DFS with BFS and now I have the answer, but who cares now..(
To authors: Isn't $$$10^5$$$ or $$$2 \times 10^5$$$ vertices enough? I believe it would hurt people much less than it actually does.
I'm a bit reluctant to talk about the contest while it's still running, and I think we all should at least a bit. You're still giving information about the solution and an unfair warning to some before starting the 6 min.
Nevertheless, I'll do a similar thing and explain your questions with my opinion.
You're right and it's another challenge, not exactly related to the problem. But those things happen and now you can consider it in the future. Or maybe you can find a proper way to increase your stack limit that'll work and use it later. I had this problem in previous years and I learned how to do it and now I didn't need to change anything.
For the part for the authors, I don't think that they could safely assume that it'd be okay to have lower limits. I'd be pretty sure to solve it in slower time complexity but in an optimized way that it'd work pretty fast in the general case.
Also, I think I'd be comfortable with another few testcases that would take several seconds. I would've given it a shot before finding a better solution because it's not required to solve that to pass the round and trying to squeeze it to fit time limit sounds more fun.
But more importantly, people that couldn't find a solution would try it and again I'm pretty sure that some non-negligible portion of them would fit in into time window.
If I were an author I'd do the same.
And finally, that number of vertices wouldn't solve the problem for most. I think you still should do something different to be not challenging your stack limit.
Exactly .. why not 2*10**5 ???
My take is on the upper comment.
Simply, it wouldn't be safe to assume that slow solutions won't be able to generate the output in 6 mins in that case. You or the most probably could've solved it in, let's say $$$O(n^2)$$$.
Sum over all test cases can be kept same .. but in individual can be reduced to disable low solutions like o(n**2) ones
For those who solved D2, how you would rate it in codeforces?
What would any of you rate the other problems? I solved everything up to D1 and I would rate:
Errichto I saw you solved it super fast, what rating would you give D2?
Edit: Does anyone agree with my ratings? just curious
Not for B, I think B is much easier than A(or maybe my solution is wrong)....
Stop discussing problems from an ongoing contest. (unless the rules say that it's ok to discuss the qualification round publicly)
And now that it is over
A: 1000
B: 1300
C: 1600
D1: 1600
A: 1400
B: 1100
C: 1900
D1: 2200
D2: 2600 (I didn't solve it)
A: 1400
B: 1000
C: 1900
D1: 1700
D2: 2100
D1 is definitely not 2200 — I solved it within a relatively short time and I have never solved a 2200 rated problem.
I'm curious how A and B should be compared. It took me much longer to think of a solution for B (although it passed, and I have some intuition, I don't really know how to prove abs(countA-countB)==1 is sufficient) but A was straightforward. I know A requires knowing about DFS/BFS which a lot of lower rated participants won't know, but still.
I don't think A requires knowing about DFS/BFS ..Its an implementation problem and for B my solution which is quite intuitive as well just keeps count of A and B and if u encountered a>1 &&b >0 or b>1 && a>0 then just decrease a and b both ...and finally if we have a=1&&!b or b=1&&!b then print Y else N..
Regarding problem B, thanks for the explanation.
Regarding problem A, yeah, you are right — it can be done without knowing about DFS/BFS. I think it's appropriate to say A is a very standard problem for anyone who did even a few problems about graphs, whereas B is an observation/ad-hoc problem, requiring at least some thinking.
For question B, the placement of As and Bs will never prevent a sequence from collapsing. For any 3 char sequence you pick such as "AAB", it will collapse to "A", which ultimately results in subtracting 1 "A" and 1 "B" from the sequence. To fully collapse, the end result must be "A" or "B", so the difference in counts must be 1 in order to achieve this.
Makes sense, thanks.
.
Yeah , that's why I tried to submit second question first so that atleast I know how to run that input file but I couldn't find out till now ? Help me if you know how.
So where can I run that input file to get output?? Please tell me if you know...
I use VScode for CP, but for D1, the input file was so large,my system did not print anything.Timer expired.My query is how to deal with these large files for the other questions?
how do i run a c++ program having array input of size>10^5,because i failed to submit the facebook hacker cup question d1 sol because my pc failed to compile/run their input files.please suggest any online compiler which takes such a large in put file
.
I don't understand even when you have full 72 hours, why don't you guys read the question carefully?
Reread the question and keep thinking.
Why can't Hacker's Cup use a separate account? My account has gotten "deactivated" twice in the past two days and it's simply annoying. It's not like us programmers even use the account in the first place. We usually end up deactivating it so why bother go through the trouble.
Welp. Now my Facebook account is deactivated because "it violated community guidelines" (just a reason to force me to upload a picture of myself, I surmise, as it's hard to violate any community guidelines when all you've done is submit problems to Hacker's Cup) and I can't submit anything. Another reason why Hacker's Cup should use separate accounts.
Is there supposed to be a time constraint for each problem?, since the problem statement didn't explicitly mention it. Or does it only check the correctness of your output file?
I am getting a presentation error while submitting my code. How to remove it. What is format of the submission file?
Guys can you please tell me why rank doesn't change even after i submitted my first solution?
Your score and rank will update as soon as you make a validly-formatted official submission. Please confirm that you're making a full submission (not just validating your solution), and that you didn't receive a Presentation Error verdict due to submitting an improperly-formatted output file.
Yes, i made the valid submission, they accepted it , i uploaded the test case output as well as source code and they have given me 10 score but my rank doesn't change. Why?
Imagine these standings:
1st: 100 points
2nd: 50 points
3rd-5th: 0 points
We show that as 1, 2, 3, 3, 3.
If you go from 0 to 10 points, then you'll be in 3rd place still, as the rankings will be 1, 2, 3, 4, 4.
By the way, the new system looks very nice and clean! Probably the nicest looking competitive programming website right now?
Thanks very much! We've been working on the redesign for a while.
Can someone please help me to solve "Presentation Error"? Even Though My code has same format as mentioned in sample test cases.
it means u got wrong answer
Presentation Error indicates that either the format isn't quite as expected (though there is some leniency), or your file includes the wrong number of test cases. Please double-check that you're uploading the correct file.
What we have suppose to submit, code, or output file?
When validating your solution, you should only upload your output file. After that, when making an official submission, you should upload both your output file and source code file.
The increased prize is awesome, but what are coordinators' thoughts on cutting it down to like $18k or something so that you can spend the extra $2k on tshirts for top 500 or something like in previous years?
As someone who probably isn't going to beat Gennady this year, it's inspiring to have the more realistic goal of earning a shirt instead...
T-shirt shipping is unfortunately a little trickier at the moment with the global coronavirus situation, but stay tuned for a prize announcement later :)
Lol,
This is not the appropriate forum for clarifications.
Lol, 2
Wanna clarify? Read the question again.
Is this how USA deals with coronavirus? Would explain a lot :P
Also happened to me. Exactly why Hacker's Cup should use a separate account other than Facebook.
How did you fixed it buddy I cannot even see my results please help I've been trying to fix it since 2 hrs
Haven't fixed it. Been 24 hrs, no solution. I already submitted to all the problems I could solve though. Not too sure what to do now.
Yeah I wonder if I qualified for the next round or not, please tell if you figure out something
We apologize that you've run into such issues. We're working on finding out more about whether some accounts have been disabled in error and, if so, what might be done about it.
Thanks a lot for replying I hope this will be resolved soon
Lelouch.Lamperouge, please email hackercup@fb.com with your Facebook account name, and we can look into your case and hopefully have your account be re-activated. Thanks!
I have mailed to the Email ID you provided with my name(Achintya Eeshan) and the email at which my FB account was registered, please tell if any further action has to be taken from my side
I tried everything. but is showing presentation error. can anyone please help me ? Case #1: YY YY Case #2: YY NY
Download the sample output and use diff to compare your output with the sample output.
In problem D1, there is a test case of 999946 size of array which cant be process on my system. What to do? I have tried declaring vector/array globally.
Exactly my problem too....
how to overcome stack overflow error? I can't get any output now. How can I increase the Stack-size in c++?
se this link :)
The Input File for D1 was too large, I think my solution was correct, it got validated, and I ran it on 96 cases (basically repeating the validation input several times), but when I ran my code on the main test cases, it crashed my Sublime IDE, and I could not submit, despite everything.
Why can't they have normal input and output, like some pretests or something? Why do they put contestants through stupid things like "download this" and "validate that". Just take the damn source code man.
Exactly, it kinda frustrating, our source codes, would be perfectly right, but, we're not able to get points, because of all these formalities.
There are benefits and drawbacks to both, with pretests the codeforces servers have been seen to sometimes have a long queue recently, although I suppose 72 hours to submit on your own time would make it less of a big deal.
I personally prefer submitting code (because I find it more convenient), but the cool thing about downloading the file is that you can use any language and libraries you want (like you could implement your solution in Mathematica or use numpy or something else), or even combine multiple languages or have a manual step in some rare circumstance.
If the person hasn't cheated and has passed the validation as well as full input file ? Are there any chances that he will get it incorrect after the contest ends ?
I mean the full input file are the total test cases ?
On grading input they don't show you result ,so after the contest they will show that ouput you submitted was correct or not. :)
Errichto Could you please explain how to solve C and D2? Was able to do D1 but have no idea on C D2
I explain visually here, but here's a quick TLDR: you can turn D2 into D1 except with the constraint that different gas stations give you different amounts of gas, and then use a segment tree to speed up the dp transition.
For C, you can do a dp with a hashmap. On the first pass through, you can consider the farthest right you can go from each position assuming all trees fall to the left. Then on a second pass, you can consider how far you can go from each tree's base if it falls to the right. You know your answer will be a prefix of trees falling right, followed by a suffix of trees falling left, since no two trees start at the same position.
Solutions are available on the contest site!
https://www.facebook.com/codingcompetitions/hacker-cup/2020/qualification-round/solutions
my screencast (2nd place) https://www.youtube.com/watch?v=91IAQUCbs14
I would win if I didn't misread problem D first and implemented a solution for cos-per-gallon version. Also, I overcomplicated D2 with centroids :)
Watch me if you want to see my performance with some live commentary. If you want solutions, just watch the end of SecondThread's video.
Errichto Kudos on getting second place ! I am a constant subscriber and supporter and I urge that it will be great if you upload intuition and idea of D1 and D2 problems in a little more concise way to explain them ! Tried watching the screencast and got nothing :( ! An explanatory comment would also suffice !
My solution was D2 was centroids to find all unvisited vertices within some range, plus smart Dijkstra like in https://mirror.codeforces.com/problemset/problem/786/B so that there would be a single logarithm in complexity.
Thanks for the reply ! I will refer this problem while upsolving D2 :)
can you share D2 Dijkstra solution code ?
Me too!!
Cost per gallon variant (D1) was an old problem, in fact it appeared in Distributed Codejam 2016: https://mirror.codeforces.com/blog/entry/45377
(unfortunately Codejam team took down the old contest website and I couldn't find the original statement anymore).
Video solutions to all problems, for people who are interested.
Thank you man, I was desperately waiting for your and errichto's video solution.
The contest has ended, and I placed 191 on the leaderboard. Here are my solutions: https://www.youtube.com/watch?v=yxG_zMZ34uc.
Adding my name to the list of people supporting a change in grading system after I got WA on D1 (pushing me out of 1st place in the round) because I accidentally ran my C code on the D1 input :p I just tested the source code I uploaded with my submission on a new input file and passed the tests. Obviously, it's entirely possible to upload the wrong file on CF, just as it is to run the wrong program in FHC, but in those contests you have the chance to resubmit (usually without penalty) after your answers are absurdly wrong and you fail the first test. Unfortunately, the validation system doesn't deal with this edge case, since I had the right file pulled up to deal with the validation input but somehow ran the wrong one on the real tests.
Thankfully I didn't have any issues this time, but I very nearly uploaded the input file instead of the output file. I'm also a strong supporter of the 'submit your code' system instead of the 6 minute timer running things locally as well (preferably with single-testcase problems as well). It just makes everything easier for the competitors.
You would've gotten PE if you uploaded the input file.
We intentionally have a different T for each problem to help alleviate this to an extent (so we can tell if you've uploaded output for a different problem as opposed to just egregiously wrong output for the current problem). It's unfortunate that your code is successful on both input formats XD
I suspect the issue was that my D1 input included few or no huge input values early on; there was a case with 100,000 small values before any massive inputs appeared. As a result, since C reads a different number of values per test case than D1, my C processed a large number of tests with small values of N that corresponded to gas prices in the D1 tests; as a result, it was able to finish processing the appropriate amount of tests based on the D1 input.
I was screwed because problem C's input file was ~30 MB and downloading that took away 4 minutes. I replaced my input.txt with the downloaded file, then stupid Codeblocks crashed because I keep input.txt open in Codeblocks. Froze my system for 2 minutes. No time to run and upload files.
Don't work for Facebook bruh, unless you care about the money part
For how many years have you worked with facebook?
I accidentally submitted my template code in problem C but my solution passed :facepalm Will it affect final standings?
Is it possible to solve the problems after the round is over? (And submit them for practice.)
Yeah it's already open for practice.
oh, I see, the button wasn't available on mobile
For problem D2 I submitted a rather naive brute-force solution which I think could run in O(NM) worst case. All my solution does is use a priority queue to sort by current cost and then by fuel remaining. Then it just tries all the states in that order, and fills up on fuel if possible. It runs on my computer in around 15 seconds, but I feel like tests could be constructed to make it take much longer.
Would anyone mind looking at my submission and see if this is the case?
Can anyone help me figure out why this code for D1 has a runtime error on CodeBlocks before I increased the stack size to 256 MB? Does it have something to do with my least_cost set?
My logic is very similar to your one , just for finding least cost in a range I used segment trees instead of sets and it worked efficiently.
Declare the cost array globally
You may need to either declare
cost[n + 1]as global or dynamically allocate it.Does someone have a more detailed explanation for how to solve D2 using Centroid Decomposition? It's not super clear to me how to relate the centroid tree to this problem at all and the explanations above are kind of short.
I did something like this :
1) We need to calculate dp[i], which is the minimum cost to reach vertex i from A. C[i] = 0 can be replaced with a large value (infinity) to allow fuelling in any node.
2) First we build the centroid tree of the given tree and for each node u maintain the distances to all it's children in a sorted order in a vector (say dis_child[u]).
3) Maintain a priority queue of active nodes from which we'll be relaxing the dp values. The priority queue will be sorted accoring to dp[i] + c[i] values. Initially the priority queue will only have node A.
4) Now we need to pick the best node ( say x ) from the priority queue and relax those nodes which are reachable from x and have not been visited and make them active.
5) Step 4 can be done using the centroid tree. For a node x, travel to it's parent (say p) in the centroid tree and let the distance from x to p in the original tree be d. Then we need to remove the nodes from dis_child[p] which are at a distance of <= (m — d), relax their dp values and make them active, if they've not been visited before.
Total Complexity : O(NlogN).
Here's my submission : Link
Awesome, thank you!
I did the same thing but in a simpler way. Initially, A will have some set of active nodes (nodes at distance m from A) in the priority queue, now as you remove the nodes from the priority queue you'll be unlocking further nodes (for examples nodes at distance m + 2) and you'll add them to the priority queue. For doing this, I will maintain a list of nodes that will be unlocked when A will be able to reach some distance x. In this way, we can avoid using the centroid tree.
Hi wjomlex, I have been unable to view the friend leaderboard since the contest ended. It just keeps loading without any result. Is this a known issue? I'd be happy to DM my FB username if it's useful for debugging.
Thanks!
We've had a few reports of this, yeah. Was it working for you until the contest ended? We're looking into a fix now.
Yeah, I definitely remember being able to view it yesterday while the contest was running.
Thanks for the info.
Mildly interesting: this problem is nearly identical to D1 (even in flavortext) except for the fact that you don't have to fill up your tank entirely and you pay for gas relative to how much you get.
This one also.
one more
Now I see, this is absolutely identical except for the fact that there are test cases in the FHC problem and there is no difference between mileage K and tank capacity M whatsoever!!
Hi all, I wrote a simple O(N) deque solution for facebook hacker cup problem D2, I'm wondering if many other people knew there is a simple O(N) solution, or perhaps I should write a post about it if people would be interested? The editorial suggested O(NLOGK) rather than O(N)
Thanks :)
@robertkingnz code link: https://www.facebook.com/async/codingproblems/download/submission/source_code/?submission_id=1611307992378413
Me too! my code
Yes, describe please.
@errichto, my girlfriend is very impressed you replied to my comment since she sees me watching and learning from you on youtube :) Maybe we should collaborate someday, I want to make a game-theory website and platform. Also i'm very strong on Full Stack Development so I could help you with web development or I could sponsor your video sometime :)
My code runs in 7 seconds using PyPy which i was happy with since python is usually a bit slow :)
I used an increasing deque called "q", that contains increasing (i, cost) pairs. 'i' represents the ith value in the path from A to B, cost is cheapest cost to get to i. If there were no subtrees hanging from the path, we could delete all the code below the line "k = 0". However, if there is a subtree from a node in the path, we iterate the best costs (costs_below yields the best cost at each level of the subtree as needed), from these subtree costs we build another ordered deque called "better", that also contains (i, cost) pairs.(this time we insert right to left instead of left to right). The idea is we can fold this "better" deque onto the original "q" deque (pivoting at the ith node (merging to maintain sort order by 'i' value)). We then merge the two deques together, we only want the best values from each. However, the trick is that this merge still gives us O(N), we will never need to pop more than H values from 'q', where H is the height of the subtree. This is because worst case our queue 'q' has increasing values from ~ i-H to H. (think folding subtree back onto the path, it will only overlap at most H). So the cost of the last few lines of code that fix the queue is the same as the cost of traversing the subtree, which is O(N) on those nodes, so the overall complexity is O(N).
Yes,share your idea pls.
Can anyone explain what are the updates being carried out in D2 while using segment tree?
Hey, suppose the path from A to B is this-
A-C-D-B
Now D has a branch from it, D-E-F
Suppose we know min cost to reach each vertex from A (except B) and we are now going to calculate the min-cost for B.
From B, C and E are at an equal distance and F and A are also equidistant from B. So from both these pairs we actually only need the ones with min (cost_to_reach + cost_of_refill). So when we are at E, we will update the segment tree for C's position (taking min of C and E) and when we are at F, we will update the segment tree for A's position (taking min of A and F).
I hope it helps.
Thanx
I submitted NlogN solution to C, but it didn't gave output on their testcases. Is it due to so many recursion calls increasing stack size? Please if someone can look into it and help.
It's frustrating. Thank you :)
Submission Link
It did pass their initial testcase check.
I have a short MIN-HEAP solution to D1 (with code) that has a conversion to D2 (which I didn't really have time to code).
I go from right to left (end to start) and I maintain a min-heap containing elements that had their cost distance from B already set, if you refuel at their position. I DelMin from the heap, and I go M indices back in the array, and then I move forward, setting the distance to all the elements until I encounter an element already in the MinHeap. I finish when "M indices back" reaches the first city. This works because the elements with already set distance from B (which means they were inserted in the heap) are contiguous from an index i to N.
An example of the first two iterations — the heap starts with only N with distance 0, and then it's popped, we go M back, and the cost of all the last M elements is now set as their cost. Now you get DelMin = (i,cost). You go to index i-M and update all the elements until you reach index N-M.
D2: If anyone actually got here and wants to know the conversion to D2, just ask and I'll explain, it's simple enough.
pls explain your idea for D2.
Edit: I found a small problem. I'll correct and re-edit. I know how to correct, but it might be annoying.
OK it got accepted! Yahoo! I debugged and found some errors and at the end it was for the best because now the explanation will be much simpler.
In my solution to D1 I set the cost to all not-set elements from index i-M to i. The generalized idea is basically instead of index i-M to i, set all not-set element with distance from B of i-M to i (and then it's an exact generalization of my solution to D1). More specifically if the element popped from the heap (v) can reach v at distance K, then set the cost of all the element from i=K...dist(v).
To understand the code though, I need to explain what I transform the graph to ( In the end this transformation big transformation wasn't needed at all, and really all I needed was the distance to A and to B, and I actually have lots of redundancy in my code, but it's already implemented and I'm not about to change it xD) :
I transform the graph to an array A of lists L=A[i]. (this is the part I wasn't in the mood to do). For the sake of understanding, imagine the array A going left to right (A to B) and any list A[i] going from top to bottom.
I look at the path from A to B as an array, where each cell in the array has a rooted tree (the subtree branching out from a node in the path, that doesn't include other nodes in the path). Then, since there is no point to refuel more than once in each of the these trees, I transform each of these trees to a list L, where at L[d] I keep the node with the minimum cost at depth d (of course the list is only as long at the tree's depth).