eatmore's blog

By eatmore, history, 8 years ago, In English

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.

  • Vote: I like it
  • +218
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problems are already accessible if we click on them. Is this a bug? (the timer shows ~6h till contest starts)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    I can't see any tasks...

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +39 Vote: I do not like it

        please add me on Facebook, I need to talk to you :D

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 3   Vote: I like it +38 Vote: I do not like it

        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!

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

          Cool, thanks!

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          On an off topic, you can't send Gennady a friends request because he has reached his limit

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I can now boast about it! I am an early bird!! :D

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        Haha, great, I can also see them :D.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +39 Vote: I do not like it

          So, you'll have 3.5 days instead of 3. Cheater11!!

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it -40 Vote: I do not like it

            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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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~

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's like the Google Code Jam "large" inputs. You can submit multiple times in the 6-minute window.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Can i get TLE after submission or will they only check if the output files match wjomlex?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You need to generate and upload your output in the 6-minute window. That's the time limit.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +31 Vote: I do not like it

              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.

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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) ?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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).

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Which means complexity of a program doesn't matter much?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it -18 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            use redirection. if you are on windows, do this a < inputfile.txt > outputfile.txt and on linux ./a.out < inputfile.txt > outputfile.txt

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hi 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 .

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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?

              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              Rev. 3   Vote: I like it +5 Vote: I do not like it

              Hello . I have Uploaded output Files & Source files for Problem C . In my Cpp Source file I didn't Comment the below's Lines "

              freopen("b.txt", "r", stdin);
              freopen("bout.txt", "w", stdout);
              

              Will it be Any problem ?? I did not get any Satisfied answer from others .

              Thanks in Advance .

              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                As others have told me, the source code won't get compiled. So it is fine. Its only an anti-plagiarism measure.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    As MathCrusader says, it's an anti-cheating mechanism.

»
8 years ago, # |
  Vote: I like it +53 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -45 Vote: I do not like it

      Why are the cash prizes for onsite participants so low this time?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      This is great! Could you add a link to the editorials post in the 'past rounds' page?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Ah yeah, that would be a good idea.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Why is 2011 qualification round missing? As well as the test round and one more round 1A.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

          Screenshot

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            FWIW, the 2011 qualification round shows up for me.

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Well.. you were able to see the tasks before the contest.. so that doesn't count :D

              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                That's why I said "FWIW" (for what it's worth) :)

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks, we'll check that out.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 =

    • Input files will be at most 10MB large, and most will be much smaller.
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      One fix for this is to provide the input files in compressed format too. So those who have slow internet can download it quickly.

»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Hi I submitted the solution of problem Boomerang but it said submission failed :| What's the problem with it ?

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's the max length of the word in text editor task, or this is unmentioned deliberatly?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The total length of all N words in each set will be at most 100,000 characters.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use ideone and then paste the output. Make sure you're using ideone in private mode though.

»
8 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I think, output for B is too large (200 tests)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Write this Two lines before Scanning Test Cases .

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    

    " You can write your desired file name at place of input & output ."

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      And the rest part of the code remains as it is? PS: Thank you so much :)

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          As far as I have heard that this is applicable in only linux. Can this be done in windows too?

»
8 years ago, # |
  Vote: I like it -49 Vote: I do not like it

My A takes 125 seconds to run on worst case. :( Is this because of sub optimal solution complexity?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it -41 Vote: I do not like it

    Ok! Edited to suit the rules.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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 .

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      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.

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Do we have to register for this contest or just submit without registration ?

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Facebook is filter in my country :( .

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Как отправить решение? How to send the solution?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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 ?

»
8 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Почему не написано что нужно пройти регистрацию у не смог отправить задачу из-за этого Это может выглядеть смешным но обидно а пишет Fail вместо того чтобы указывать что нужно пройти регистрацию "огромное спасибо!!!"

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the results be out ?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :\

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Another way to make it even faster is to use

      short has[800000001];
      

      to keep track, which fits into memory locally and took ~4secs. :)

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      "whereas my O(N^2 log N) sorting the distances and counting duplicates takes" — my version takes < 4s

      pair<int, int>  xy[2002]
      

      and

      int hyp[2002][2002]
      
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yup, O(N^2) is ideal.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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..

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Your hand-rolled open addressing solution is great, btw.

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            but, I don't understand how the find() function was working, could you explain please? ideone link

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it
              • The find function increments the counter for that squared distance and returns the previous value (which is added to the final answer).
              • It uses a hash table (hash) with open addressing/linear probing (the while loop). The hash function is the least significant 15 bits (x & MOD). counter holds the values.
              • m and the id array mark which buckets are occupied, and also clear the table when we move on to a new point.
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

                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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    mine is N^2logN too. took around 3 minute 50 seconds :v If I wasn't using ubuntu I was a goner.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There are a lot of reasons:

      1) slow input/output

      2) "slow language" Ruby, Python, etc

      3) energy saving mode on windows

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Will we have a mirror gym contest to the round to verify our solutions like the last year? :D

»
8 years ago, # |
  Vote: I like it +109 Vote: I do not like it

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).

  • »
    »
    8 years ago, # ^ |
    Rev. 4   Vote: I like it +57 Vote: I do not like 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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +26 Vote: I do not like it

          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.)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    I believe we sent an email to all prior registrants.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +75 Vote: I do not like it

      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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +41 Vote: I do not like it

      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).

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      I also didn't receive any e-mail. This might explain why the number of participants is lower this year.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      i also haven't received either mail or notification via fb. Only got post about solutions...

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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).

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    " 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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Even the facebook hacker cup official page didn't post any thing about the qualification round , weird .

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read news feed in vk.com. I've make a post about qual :-)

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      I haven't seen it. One day before exam and you're telling me about news in vk.com?)

»
8 years ago, # |
  Vote: I like it +56 Vote: I do not like it

I've added the round to the Gym: 2016 Facebook Hacker Cup, Qualification Round.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I submitted the same code I used in the official qualification and it gives me TLE on test 2!!!

    here it is 15316424

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      In the official qualification you had 6 minutes, here you have 15 seconds.

»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Hope for more and more 0AC problem...

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think in terms of longest common prefix, you will see why sorting doesnt change the answer.

»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

How to solve last problem if we does not need to delete last printed word?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    It's the same, just don't add the length of the last word to the answer.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      that's not true.

      try test a bb c

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        What 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.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +23 Vote: I do not like it

          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

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How do we solve Problem B (High Security) using max flow?

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +2 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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..

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I haven't got mine either =(

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The same situation with me. Also some of my friends did not received t-shirt last year

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

GL & HF

»
7 years ago, # |
  Vote: I like it +76 Vote: I do not like it

No FHC 2017?