Facebook Hacker Cup 2016 is starting soon. Don't miss the qualification round, which starts at midnight UTC and lasts for 3 days. To advance, you will need to solve at least one problem.
This year's finals will be in London, so this is another chance for those who missed GCJ finals in 2013.
You can enter the round using this link, but you need to log into Facebook first.
The problems are already accessible if we click on them. Is this a bug? (the timer shows ~6h till contest starts)
I can't see any tasks...
Me and another former Facebook summer intern can see the tasks. I asked a friend who didn't work at Facebook and he can't. So, maybe we are still considered Facebook employees in the platform.
I wasn't sure I was eligible for the contest anyway, so that's ok with me. I won't participate.
please add me on Facebook, I need to talk to you :D
Yeah, we encountered this bug with a small handful of former interns (fewer than 10 as far as we can tell). It only applies to the problems from this round. This isn't a huge concern for this round since there's ample time for everyone to complete at least one problem. It will be fixed before the next round starts.
As long as you aren't currently working at Facebook, you're eligible to compete. Please do!
Cool, thanks!
On an off topic, you can't send Gennady a friends request because he has reached his limit
I can now boast about it! I am an early bird!! :D
Haha, great, I can also see them :D.
So, you'll have 3.5 days instead of 3. Cheater11!!
I can tell you a little bit secret, but shhh... don't tell anyone else! First problem is a geometrical one! That additional half of a day will actually be very useful for me, there is no chance I can solve any of remaining three problems and one needs a very long code, I probably won't be able to code it in less than 3 days.
None need very long code if done efficiently :)
there is no chance I can solve any of remaining three problems
Who do you think you are -_-
A newbie, don't you see?
I had trouble seeing, because of his rating :p
I don't see :D
whatkindofsorcery.jpg
For each problem, you can only download the input once? Or is there way try again like in Google Code Jam...
I download once for A problem when I wasn't really ready, to check format~
It's like the Google Code Jam "large" inputs. You can submit multiple times in the 6-minute window.
I did not realise, you cannot open inputs twice. So I open one input without having code completely done, and can't submit again haha
Lucky it is only the qualification round, so it does not matter that much as long as I can solve correct one more problem...
Can i get TLE after submission or will they only check if the output files match wjomlex?
You need to generate and upload your output in the 6-minute window. That's the time limit.
and what about the downloading time? I can remember, in the previous year a lot of people got TLE because of not too fast internet speed in the round-1.
Download time is included in the 6 minutes. If you subtract 2 minutes for running the program and uploading the output, you'll still have 4 minutes for the download. The maxinmal input size is 10MB. So if your internet connection can handle 50 KB per second you should be fine. In the qualification round the maximal input is smaller than 10MB, so also a slower connection should be fine. Just make sure that your program is absolutely correct, so you don't waste time here.
We've made sure that the inputs are smaller this time. We guarantee that no problem has more than 10MB of input, though I think for all but one problem we have planned, it's actually < 3MB.
I'd still ask you to consider moving this limit even lower (for about 1MiB).
I agree that probably everybody will be able to download their tests, but they may have several minutes less to react to found bugs(for example runtime errors like in problem where stack should have been increased). It's huge difference whether you have 5min40sec to fix that or just 2-3mins.
What is the purpose of uploading source code along with output file. Is it okay if in the source code that I have uploaded I am reading from an input file(that was in my computer) ?
I think it is just to stop people from cheating -- if they didn't require the source code, then you could solve the problem and then send your friends your code and they could generate the output file from your program and Facebook would never know. At least this way, they can check for similar/identical code. You can implement your program's I/O however you want (so long as you use a free-to-use compiler/interpreter).
Which means complexity of a program doesn't matter much?
It isn't as tight as CodeForces, no. The difference is that on CodeForces, you get 1-3 seconds per test case, whereas on Facebook, you get 6 minutes for 50-200 test cases including download/upload time.
After i downloaded the text file of boomerang then i copied input from the file and pasted it in command line but my command line didn't detect new line. I mean if there is a test case like this
50
100
It took it like 50100 because of which it couldn't give output. What should i do in such case for next problem?
I would recommend not ever copy/pasting for contests. Situations come up like this every once in a while, and it is hard to determine that is what is wrong. I would recommend that you either use file I/O (e.g., fstream in C++) or file redirection. For example, if you are using Linux or OSX, and your program is called prog, your input is in input.txt and you want your output to go into output.txt, then you can use the command:
./prog < input.txt > output.txt. I'm not sure what the Windows equivalent is. But then you're sure that the input is exactly as Facebook sent it to you as.use redirection. if you are on windows, do this
a < inputfile.txt > outputfile.txtand on linux./a.out < inputfile.txt > outputfile.txtHi I have downloaded the Input file but I could not Submit my Solution within 6 minutes for Problem A .
Can I submit again or not ? I can't see another input file that are able to download for Problem A .
No, for the Hacker Cup, you only get one try for each problem. =(. Hopefully you can get one of the other ones so you can advance to Round 1.
Are the problems judged only after the contest is over? Like even if i submit a blank file it would show as 10 points in current scoreboard?
Also, since the code is not compiled, does that mean we are free to use multithreading to speed up tasks?
They are all judged after the contest, yeah. No checking whatsoever is done during the contest. You may use multithreading if you wish, yes, so long as you use a free compiler or interpreter.
In what manner can you use multithreading in this context to speed up tasks? I am sorry, this is the first time Iam competing in hackercup.
You run the code on your own computer and upload the output, so whatever software you have on your computer, you can use to solve the problem (once again, as long as it is free).
One naive implementation could be to find answer for multiple test cases at a time instead of sequentially processing one by one. For eg: my current program for 1st problem takes around 150 seconds in the worst case scenerio (bad algorithm prolly) in my computer (Though it should never be so slow if i go by big oh analysis).
However if i make use of multithreading, maybe i would be able to find the ans in less then 30 seconds only.
Got it. As long as its free, and because your code won't be compiled you can use anything to fit your submission within 6 minutes.
Hello . I have Uploaded output Files & Source files for Problem C . In my Cpp Source file I didn't Comment the below's Lines "
Will it be Any problem ?? I did not get any Satisfied answer from others .
Thanks in Advance .
As others have told me, the source code won't get compiled. So it is fine. Its only an anti-plagiarism measure.
As MathCrusader says, it's an anti-cheating mechanism.
https://www.facebook.com/hackercup/past_rounds/904578626288920/
Have you noticed this one? It's very nice, until now I had lots of trouble with finding old problems in FHC.
Glad you like it! That got added this year because, as you say, it was awful trying to find old rounds before. We'll try to get practice mode cleaned up after this year's contest also.
Why are the cash prizes for onsite participants so low this time?
It's the same as last year.
This is great! Could you add a link to the editorials post in the 'past rounds' page?
Ah yeah, that would be a good idea.
Why is 2011 qualification round missing? As well as the test round and one more round 1A.
The test round and the unfortunate first attempt at round 1A were left off since they aren't "official" rounds. The 2011 qualification round is there though. If you don't see it, can you post a screenshot?
FWIW, the 2011 qualification round shows up for me.
Well.. you were able to see the tasks before the contest.. so that doesn't count :D
That's why I said "FWIW" (for what it's worth) :)
Thanks, we'll check that out.
why dont they mention the size of the input file. i could only solve problem 3 and when i tried to submit, the time expired before the download could finish. if they had mentioned the size of the file, i would have used someone else's computer for faster internet.
In rules they allowed input files to be up to 10M, which is maybe a little bit too much for modem connection, but this is their decision which they properly communicated from beginning. My own input for third problem is actually 2.5M, which is like 7 minutes with good modem — for next round you definitely should search for faster connection.
from Facebook Hackercup page:
= Input Files =
One fix for this is to provide the input files in compressed format too. So those who have slow internet can download it quickly.
Hi I submitted the solution of problem Boomerang but it said submission failed :| What's the problem with it ?
What's the max length of the word in text editor task, or this is unmentioned deliberatly?
The total length of all N words in each set will be at most 100,000 characters.
Guys help needed.What are the java submission specifications?
Should the class be public?What should be the class name?Should I be writing into the output file in my code or can I run my code on Ideone and copy,paste the solution on to a file and submit it?Is there any file name specification?
It doesn't matter what is public and what's not. You just have to run it locally and send output. Filename is not important too
You can use ideone and then paste the output. Make sure you're using ideone in private mode though.
If I click on details for last submission, for problems A,C and D I get a detailed summary with Time of submission, Source Code, Output MD5, and Output for each case shown.
However, for problem B it only shows the first 3 i.e. Output for each case is not shown. Is this intentional/a bug/some mistake in uploading output file on my part?
I think, output for B is too large (200 tests)
200 integers + "case#" . How big can that be?
Yeah, we have a pretty small limit for what we'll show there, and the output for B is just over that. We'll add a download link for such outputs in the future.
What are the rules regarding using multiple facebook accounts? If the timer expires before I upload a solution, can I register from another account and re-attempt to submit? Since everyone gets a different input file with a different size, and varying internet connection speeds, it is a matter of bad luck if your timer expires, not that its cheating. But I want to be sure. What are the rules regarding this?
While registering it was said that you need a facebook account to register. Now if i am right, facebook has terms like only one personal account per user. So by that i think it would be no.
But then unless you want to go to onsite rounds (for which they will probably do verification) who cares :P
This is definitely not allowed :)
All the problems are made to be solved in a matter of seconds if your solution is efficient. The 6-minute timer is meant to give a fairly wide buffer for different connection speeds.
As I am new to c++, I need some help regarding-how to use read i/p file and store in the corresponding output file. For example, consider the program to add two nos(having several test cases):
include"iostream"
using namespace std;
int main(){
int t,a,b;
cin>>t;
while(t--){
cin>>a>>b;
cout<<a+b<<endl;
}
return 0;
} How to should I read t,a,b etc from input.txt and print it to output.txt? It would be of great help. Thank you
Write this Two lines before Scanning Test Cases .
" You can write your desired file name at place of input & output ."
And the rest part of the code remains as it is? PS: Thank you so much :)
Yes, indeed. Eventually you can redirect the input and output of your programme, such as ./a.out < input.in > output.out (your app will take input from file called input.in and output it into file output.out
As far as I have heard that this is applicable in only linux. Can this be done in windows too?
My A takes 125 seconds to run on worst case. :( Is this because of sub optimal solution complexity?
Ok! Edited to suit the rules.
Till the contest is not over , You should ask these kind of queries to the FBHC admins instead of on a public forum like codeforces .
I am not asking for the optimal complexity. I am just surprised that it takes so long to compute. I just wanted to know if anyone else facing this. Hackercup admins may not reply to all our queries.
Do we have to register for this contest or just submit without registration ?
you have to register yourself.
Facebook is filter in my country :( .
Как отправить решение? How to send the solution?
If you think that you have a solution, download the input file (on top of the page), run your program and upload the output file and your code.
Notice. Once you clicked on the download button, you only have 6 minutes to run your program and upload the solution. If your program is too slow or your output format is not correctly formated, you'll probably have no time for fixing it.
Thanks.
How many participants will be selected for next round ?
All the participants who will solve at least one problem, will be selected for next round ?
Yes. Everyone that solves 1 problem will advance. More infos here: https://www.facebook.com/notes/1029173677098533/
Почему не написано что нужно пройти регистрацию у не смог отправить задачу из-за этого Это может выглядеть смешным но обидно а пишет Fail вместо того чтобы указывать что нужно пройти регистрацию "огромное спасибо!!!"
When will the results be out ?
Latest update:
Edit: They are out
Now since the round is over, can anyone tell what is the optimal complexity for 1st problem? I did it N**2 log N. Took around 40 seconds on my computer for the input file :\
I believe the optimal complexity is O(N^2) using a hash table. However, my O(N^2) takes ~50secs on my computer (you can see the code, i'm in 10th place), whereas my O(N^2 log N) sorting the distances and counting duplicates takes ~12secs.
Another way to make it even faster is to use
to keep track, which fits into memory locally and took ~4secs. :)
"whereas my O(N^2 log N) sorting the distances and counting duplicates takes" — my version takes < 4s
and
Could you tell me how much time my O(N^2 log N) takes on your computer? http://ideone.com/gMC36H
Or share your code? Maybe I'm doing something silly..
Here is my code: http://mirror.codeforces.com/gym/100869/submission/15308495 Don't know, may be this is because of the difference of our compiler/PC Could you run it and tell me its time, please. My code isn't perfect (e.g. hyp should be 1D array, etc)
Thanks. My N^2 log N takes 7.4s http://mirror.codeforces.com/gym/100869/submission/15315251 My N^2 gets TLE
Yup, O(N^2) is ideal.
Okay, my problem was to store count for each point in a different map (http://paste2.org/pjVGYyIC) This took around 50 seconds o.O
I switched to just one map and processing for each point one by one and it took around 18 seconds on my pc (http://paste2.org/bhFK4aP6) Still TLE on cf gym
Next i decided to move to vectors instead of maps and it worked under 4 seconds for the tests that fb gave me (http://paste2.org/U2m8E35t). Now this gets an AC on cf gym too. So i have another reason now to not depend on maps/sets for auto sorting.
maybe you forgot to add "-O2" flag to your compilation string or "sync_with_stdio" to your code.
my solution: http://is.gd/5TBlSH
rust language, 6s on my PC with sorted vector, 12s with hash table.
I compiled with -O2. These are my programs: O(N^2) : http://ideone.com/YVXMBV O(N^2 log N) : http://ideone.com/gMC36H
Maybe my computer is just slow? I don't see, but maybe I'm doing something silly..
Yes, it's theoretically O(N^2) but sorting is often and usually faster than unordered_map in practice due to hidden overheads. You can get accepted easily under 3 seconds with a custom hash table instead of unordered_map.
Your hand-rolled open addressing solution is great, btw.
but, I don't understand how the find() function was working, could you explain please? ideone link
Yes that's about it. Don't use this in a regular codeforces round though. It degrades to O(N) very fast when only multiples of MOD are inserted. Also it's safer to declare MOD as a prime.
mine is N^2logN too. took around 3 minute 50 seconds :v If I wasn't using ubuntu I was a goner.
I use O(N^2 logN) algorithm too, and it ran in less than 5 seconds only. How can O(N^2 logN) with N <= 2000 run in more than 20 seconds, even with a slow computer? Impossible.
There are a lot of reasons:
1) slow input/output
2) "slow language" Ruby, Python, etc
3) energy saving mode on windows
My O(N^2 logN) solution is too much slow. I used faster I/O methods, c++ and no energy saving modes. Can you please take a look? Is this actually more than O(N^2 logN)?
Switch from maps to vectors. Your code is very similar to my first version: http://mirror.codeforces.com/blog/entry/22657?#comment-272213
I used O(n^2 *log(n^2)) and it took like three minutes. I'm sad. Edited: for the total input file of course.
Will we have a mirror gym contest to the round to verify our solutions like the last year? :D
Every year there is a qualification round, which means absolutely nothing but adds certain probability (in my case near 100%) of not competing in the tournament. I would be really happy to get some notification about this event in the next year. By the way, I heard the same story from my friends for a lot of times. Why the qualification round even exists? I hope round organizers would read this and make something about it.
P.s. In my case it's related to the exams in university which start every year in 11-12 January (so I don't visit codeforces for several days before it).
Well you may have missed round 1 in the same way, haven't you? And 3 days round is the hardest to miss
Notification wouldn't hurt, through
Well, you're wrong, I haven't missed round 1 previous year. I had something much more interesting: I solved all the problems, wrote them without a bug, but couldn't send the answer for the last one. All because I had updated the OS and my compiler options for using stack had changed. I couldn't google the new one in time, so I wrote to the organizers. Well, guys, I give you my code, use it please. They told me it's my problem, not theirs. And suddenly three problems weren't enough to get through. This year it's my fault, I agree. But isn't it true that you could have always done better?
I have to fully agree with organizers here. What is important here is not whose problem it is, but whose fault it is. People with connection too slow to download inputs should not be penalized, however setting local stack size is your responsibility. Of course I understand that this is not a typical issue you encounter when doing codeforces rounds etc. and that it's sad to fail because of such an issue and I would have probably also whine if that had happened to me, however it can't be denied that it was your responsibility to take care of that.
I totally agree with you. I understand the organizers decision but as you have said it's not something that happens to an olympiad competitor for a lot of times.
I just wrote the story as one of weird things that happened only once through my acm history. "I haven't made a single bug and still could not get through" -- never heard anything like it.)
It's like the other story of how I found the last bug in the code in the last minute but was so tired that could not figure out quickly how to fix it, So we fixed it right after the end.) Usually you either find and fix it in the last minute, or do it when the pressure is down five minutes later.)
I believe we sent an email to all prior registrants.
Let me disagree :). I have seen at least 2 complaints on my newsfeed of friends who wrote that they nearly missed FBHC this year, because of lack of notifications.
I participated in previous years, and I didn't receive the email this year.
Also, the announcements were apparently filtered by Facebook algorithms from my Facebook wall (despite I "liked" Facebook Hacker Cup page, only "Hacker Cup 2016 Qualification Round Solutions" managed to get through).
I also didn't receive any e-mail. This might explain why the number of participants is lower this year.
i also haven't received either mail or notification via fb. Only got post about solutions...
If you didn't receive an email, but you've participated before, would you mind messaging me your Facebook username / email address? We can check that against our logs and see if something's screwy.
From what I have heard you could pick up anyone who has participated before :) (including me — my name on Facebook is as it is written in my codeforces profile).
Thanks for the reports! I'd respond to you all individually, but I've hit the Codeforces limit on distinct people you can message in a day :)
" Why the qualification round even exists? "
Well, for those guys(as me) who have first experience with FHC it is great way to familiarize with such structure of competition.
Even the facebook hacker cup official page didn't post any thing about the qualification round , weird .
There were two posts beforehand:
https://www.facebook.com/hackercup/posts/1056525681046286 https://www.facebook.com/hackercup/posts/1082410135124507
I've seen neither of them in my news feed, even though I "liked" Hacker Cup page. Funny how Facebook's own posts fall prey to Facebook's filtering algorithms :-)
Read news feed in vk.com. I've make a post about qual :-)
I haven't seen it. One day before exam and you're telling me about news in vk.com?)
I've added the round to the Gym: 2016 Facebook Hacker Cup, Qualification Round.
why there's
"1 Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, than value 800 ms will be displayed and used to determine the verdict."
for these problems? They were added just now.
I'm fixing it right now.Fixed.I submitted the same code I used in the official qualification and it gives me TLE on test 2!!!
here it is 15316424
In the official qualification you had 6 minutes, here you have 15 seconds.
Hope for more and more 0AC problem...
Do you know New Year Prime Contest? It's a collection of 0AC problems.
http://mirror.codeforces.com/blog/entry/22304
What is 0AC problems?
Literally, problems with zero AC.
For the fourth problem, in the editorial it is mentioned to sort the strings first and then apply DP to get the best 'K' words. It is somewhat intuitive to sort the words first, but is there any formal proof to this?
Think in terms of longest common prefix, you will see why sorting doesnt change the answer.
How to solve last problem if we does not need to delete last printed word?
It's the same, just don't add the length of the last word to the answer.
that's not true.
try test
abbcWhat of it?
I'm not saying the same group of words will solve both problems, I'm just saying the same DP will work, but you don't need to add the length of the last word to the answer. Probably the set of words used will be different, but the same approach of LCP + DP will work.
Suppose you need to get all 3 strings. In the mail solution you'll sort them and c will be last. But you need to make bb last
Yeah, sorry. You're right. I didn't realize that.
Build trie, with path compression (leaving only the nodes which are either the end of some word, or has more than 1 son) there would be about n nodes left.
Now,
DP[i][j][0] is the minimum cost of starting with the string that ends in node i, and then going through the subtree of i , printing j words, and going back to node i.
DP[i][j][1] is the minimum cost of starting with the string that ends in node i, and then going through the subtree of i , printing j words, without going back to node i.
DP[i][0][0] = DP[i][0][1] = 0
If node i is the end of some word, DP[i][1][0] = DP[i][1][1] = 1
Now , go through all sons of node i, and for each son x, update DP[i] as follows.
DP[i][j][0] = min(DP[x][t][0] + DP[i][j - t][0]) + 2 * len[i][x] for each t between 1 and j
DP[i][j][1] = min(DP[x][t][1] + DP[i][j - t][0] + len[i][x], DP[x][t][0] + DP[i][j - t][1] + 2 * len[i][x]) for each t between 1 and j
Please correct me if i made a mistake.
How do we solve Problem B (High Security) using max flow?
I solved it by reducing it to kind of a matching problem. But I don't use maxflow as it is an overkill. Correct me if I'm wrong but I think maxflow can be used to solve the matching part.
Hacker Cup 2016 is running and a few people haven't received 2015 edition's t-shirts yet.. could someone check this? Originaly asked on Facebook..
I haven't got mine either =(
The same situation with me. Also some of my friends did not received t-shirt last year
GL & HF
No FHC 2017?