Sammarize's blog

By Sammarize, 9 years ago, translation, In English

Round 1 FHC starts in January, 17, at the 18.00 UTC.

Look this and other information here. The top 500 finishers will advance to Round 2, as well as contestant who gets the same number of points as the 500th contestant.

Round 1 will last 24 hours. This is not virtual contest, when you can choose moment when you start during these 24 hours, but 24-hour contest of full value. It is unusually decision. It is clearly that organizers wants all participants to find the convenient time to solve the problems. I hope the problemset we be completed such a way so how many times does participient can spend to solve the problems, 2 hours or 24, will not have a big impact to his result. Perhaps it is assumed that a certain set of problems will be solved by large number of participants, much more than 500, but very few people will be able to solve something else.

(I will glad to see the remarks about translation mistakes)

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

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

I've been wondering — why do we need send output file AND source code? Why not only source code?

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

    Probably for finding cheats out.

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

    If we send only source code, they'd have to run it to produce output to verify it, and that would inevitably limit the # of languages available (and increase implementation complexity on their side). This way we can use any language/tool we want at no cost for them.

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

      So why do we need send source code? o.O

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

        To make sure you didn't cheat! cuz otherwise you can just take someone else's sour code and use it to produce your output, they would have no idea whether you cheated or not.

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

          what about sending a correct output with source code only print Hello World :D

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

            You will likely get WA on that problem. They hopefully do some simple checks, plus you can be reported by the community. It won't be immediately, but somewhere in the process between preliminary and official results.

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

              #pragma comment(linker, "/STACK:134217728") It works for Visual Studio.

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

These rules seem slightly weird. Regardless of problem difficulty, if there are at least 500 participants with lots of free time, the round turns into "advancers == people who solved everything". And if there are hard problems in the problemset, this gives huge advantage to people with lots of free time.

I wonder how do they come up with such rules, and did they have any meaningful discussion (because discussion would definitely make this problem obvious).

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

    Well, last year it turned out fine. The 4 tasks weren't too hard, but they had some corner cases, so lots of people failed some. Still, everyone who did any 2 tasks (except for the easiest two, that wasn't enough) passed to the next round. Even just the hardest task alone was enough to pass.

    Yes, either of the scenarios you mentioned are possible and is highly undesirable, but I hope that organizers are aware of that as well.

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

    Yeah, our 24-hour rounds are a little bit different. They're kind of a stepping stone between the qualification round where you merely need to solve something, and the actual timed rounds.

    The idea is to make sure that there's another round in which all time zones can compete comfortably. We aim to make the problems at a difficulty that doesn't require all of them to be solved to advance. Right now it looks like 60 or 75 points will be the qualification cutoff.

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

who can hack facebook in this round this is important

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

    Whoever succeeds to hack Facebook during round deserves to pass to the next round, right? :D

»
9 years ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

(I will glad to see the remarks about translation mistakes)

Not a native speaker, but I think you're missing some articles. Maybe this makes it better:

FHC Round 1 starts in January, 17, at t̶h̶e̶ 18.00 UTC.

See this and other information here. The top 500 finishers will advance to Round 2, as well as any contestant who gets the same number of points as the 500th contestant.

Round 1 will last 24 hours. This is not a virtual contest, when you can choose moment when you start during these 24 hours, but 24-hour contest of full value. It is an unusual decision. It is clear that organizers want all participants to find a convenient time to solve the problems. I hope the problemset will be completed in such a way that how much time the participant can spend to solve the problems, 2 hours or 24, will not have a big impact to his result. Perhaps it is assumed that a certain set of problems will be solved by a large number of participants, much more than 500, but very few people will be able to solve something else.

(I will be glad to see the remarks about translation mistakes)

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

    Translation is pretty OK though I'm somewhat puzzled by:

    This is not a virtual contest, when you can choose moment when you start during these 24 hours, but 24-hour contest of full value. It is an unusual decision.

    I thought it is usual way of conducting Round 1 over several last years (i.e. like Qual but 1 day instead of 3), but probably I'm missing something.

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

      Some contests open for a long window, but each participant can only use a part of it. If I recall correctly, this is similar to USACO. The contest is open for around 72 hours to let participants choose their most convenient time, but upon starting, they only have 4 hours to solve the problems. Compare to this Facebook Hacker Cup round where the entire 24-hour window is also the entire time to solve problems.

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

To the experienced Facebook Hacker Cup people, what can we expect from Round 1 problems? About the same difficulty as a Div 2 round in Topcoder/Codeforces? Slightly more difficult than the Qualification Round problems?

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

dis like me pls

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

Best of luck to everyone participating!!

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

Is participation in the qualification round required to participate in round 1? I didn't realise it would be held so early!

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

    Yes, one solved problem in the qualification round is required.

»
9 years ago, # |
Rev. 4   Vote: I like it -45 Vote: I do not like it

..

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

I upload both output and source of first problem
simultaneously when I tried to click submit my lab suddenly freezes with unexpectable behaviour from windows :( :(

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

I guess contestants with slow Internet connection already have some special feelings about those 20mb-large input files...

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

    My internet downloads 20 mb in 18 minutes, I have a great problem... xD

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

    Probably the best solution is to allow participant download encrypted input archive at any moment and display password when he starts 6-min timer.

    This doesn't work for 18mb output, though. But I don't remember tasks with large output on FHC before.

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

      For outputs, jury can just ask to upload some cryptographically secure hash of the output file.

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

        If the output is (almost) unique.

        But there still will be problems with different endlines, extra spaces, #'s etc

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

          Ask for hash in 6 minutes and for the actual output in unlimited time. All such problems are trivially solvable in cryptography.

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

            Nice idea, agreed

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

            This is getting too complicated, at least compared to the solution: just don't ask for large outputs.

            Are there even programming problems that require huge outputs and aren't extremely technical? I don't remember any.

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

              Sure there are such tasks. For example these 4 tasks from my rounds on Codeforces:

              321C - Ciel the Commander, 388B - Fox and Minimal path, 472E - Design Tutorial: Learn from a Game, 472F - Design Tutorial: Change the Goal

              They are all about construct a valid solution, so the output is far from unique.

              And, well, there is always a solution by cryptography: we can use interactive proof system -- I remember there are methods to transmit few bits to check if x makes f(x) = true for a function f.

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

                You're misunderstanding. I'm asking about problems that require && huge outputs, not allow || non-verysmall outputs.

                The difference being: your examples don't really go beyond 2-3 MB of output size (not even my code on 472F, and considering how sloppy I usually am when such constraints are loose...). That's roughly an order lower than 20 MB. 30 minutes vs 3 minutes of uploading? That's a huge difference.

                Random query/update problems would be examples as good as yours, but that's not what I'm looking for. (Specific IPSC-styled problems aren't either.)

                I was wondering about problems which have output size comparable to the 20 MB that were the problem this time. Even by including several large cases in a single input file, the point is that it's really huge per one execution of the code, and ideally, that it actually matters.

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

                  Oh, I see. But if there are 20 test cases there will be huge amount of bits to upload, right?

                  "Random query/update problems would be examples as good as yours" -- I will argue this a bit: for this kind of problem, we can just ask the hash of the output. But for my examples, this will not work.

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

    I know this doesn't scale, but just a trivial zipping the inputs reduces the size from ~19MB to ~3MB. I guess organizers just didn't consider the possibility that someone doesn't have fast internet connection.

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

      Judging by the bandwidth that the facebook mobile app needs, it's safe to say that facebookers ignoring the possibility of bad internet connections is not very unusual.

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

    Yeah, we obviously made a mistake with the input sizes in this round, and it won't happen again. For this round we're letting people email us their solutions if the download doesn't finish in time.

    We like iterating and trying new things, but obviously this wasn't a good choice :)

    In the end everybody should end up with the right score though.

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

      Does it mean just before the deadline (before an hour or before a few minutes), because I don't see any changes in the scoreboard and would like to understand that it's the wrong solution/answer, or the scoreboard hasn't changed yet. Thank u!

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

        The manual submissions will be added to the scoreboard before the round ends. It will probably be close to the end of the round so we can compile the results and put them in in one batch.

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

          Oh. Ok. I understand the situation. Thank u for your answer!

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

          i got the input file when only 10 seconds were left & couldn't submit ultimately. i've sent feedback immediately but as this happened at the last hour, i'm afraid i will be asked to submit the source code before the round ends. what do i do? :/

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

      How do you justify that a person using this "send-solution-by-email" was really not be able to download, not a person that exceeded the 6 minute timit limit and used it as a hack?

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

        We have logs showing the download times, and we still require that people submit their source code which we can check manually.

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

          I had to do the e-mail thing because really my lap-top couldn't download and process the whole input thing in time, after that I kept working on my pc, when I got the input file on the mail, I sent my source code and output, and screenshot of that job being done in 6 seconds. I really couldn't think of better way to prove that I didn't have something like WA or my program was exceeding time limit, hope this should be fine.

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

          How exactly do you plan to use the logs to tell you if a contestant has tampered with the source code after the 6 minute timer ? By how much time has passed between the moment he downloaded it and the moment he contacted you ? That doesn't seem very reliable.

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

          I have used File Input/output (freopen) in my manual submissions.does this affect my result while you use a batch to run ? by the way,after send my feedback request,i go out to have my dinner .....So i send my source codes a period of time later...does this affect?My source codes can finish tasks in several seconds,but the mail time is not following closely to the download time.

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

      How to email to you my solution for task Autocomplete? The download process for me took more than 6 minutes. I submitted feedback a few hours ago but I didn't receive any answer!

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

      I'm interested to know how you will compile and run the manual submissions for the last problem. Will you use the default stack size or you will increase it? Will you use the C++ optimizer or no? In all cases, it will be totally unfair, because many contestants failed to submit the correct output because they couldn't increase the stack size. And if you are going to keep the default stack size, what if who sent the solution manually was aware of this and prepared his machine to run with a large stack?

      I wasn't affected by the stack size issue, and I wasn't affected by the the large inputs. And I might be qualified by just 60 points, but I believe this round should be canceled and make another one next week or so. I don't see any way to make it a fair round.

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

        We're using a large stack, and I agree that this may give a few people points they otherwise would not have received. We'll be using the 500th place cutoff before considering manual submissions (should they be different), so anybody who would have qualified before considering manual submissions will still qualify.

        I don't think this should be a huge concern to the eventual top 100 who will advance from Round 2. If there is anybody who did not legitimately succeed in Round 1, their chances of ending up in the top 100 in Round 2 are extremely slim (in my opinion). That said, we have records of all of these manual submissions, so if any such people do make the top 100 in Round 2, we can make sure they're well audited, and we can always make provisions for a couple more advancers from Round 2.

        I know that a lot of people don't have ambitions for the top 100, but do have winning a T-shirt in mind (like me in GCJ every year). We can probably expand the range of competitors that receive T-shirts as well so nobody feels that they were beaten out of a T-shirt by some illegitimate competitor.

        I definitely don't like the situation any more than you. It's a mistake we won't repeat. Running a new round introduces a different sort of unfairness in that we've already announced the schedule, and people may have planned for it. Adjusting the schedule would be unfair to anybody who would be unable to compete in a make-up round. Another alternative is tossing Round 1 and advancing everybody to Round 2, but that's just more false positives.

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

          Good. I agree that this is the right thing to do at this point.

          Any estimate on when the results will be up?

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

            My current estimate is about 6 hours.

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

          Do you plan to give T-shirts for top500 + top500 after excluding people with manual submissions?
          And, anyway, it would be great to know stats about how much people got AC with manual submissions(and got 75+ pts).

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

            There are about 725 competitors going to Round 2. I would estimate that we added about 100 ACs to Autocomplete, and about 40 for Corporate Gifting. The number of people that advanced only after considering their manual submissions is probably around 50-70.

            We're increasing the number of T-shirts for Round 2 to 550 so nobody should feel that they failed to get a T-shirt because of somebody who sent manual submissions.

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

              First of all, thank you for the problemset — it was good yet not ideal.

              Secondly, if rules already changed so many times (more T-shirts, more advancers to the next round, manual submissions), why not to change it one more time and set manual cut-off to be equal to number < 75 points? Let's say, 40 points — then in total only 1944 contestants will advance.

              Such decision will have several advantages:

              • No more complaints about Stack Overflow issues.
              • No more complaints about manual submissions.
              • Several strong competitors who were finalists in previous year will advance.
              • Stronger competition for T-shirts — if there will be 550 T-shirts and now 731 person advanced, then there's basically no competition for T-shirts at all, right? No competition leads no motivation.
              • Facebook Hacker Cup gets more popularity because so many people will not be annoyed by unfairness.

              Anyways, emails with final results were still not sent out so there's still possibility to make a lot of people happier and make competition more fair.

              Thank you for the attention.

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

              Hi Wesley, Just wanted to check if you guys had a chance to look into the logistics of the T-shirts yet. I didn't make it to round 3 but I qualified to win a T-shirt (a first for me!) and I am a bit too excited about it! :P

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

                The T-shirt design was finalized yesterday. I'm not sure about the ship date at the moment.

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

    It was unfair, I spent almost 20 minutes to download the input file, close to 1 minute to open the file plus running time of my code, resulting in a Time Exceeded.

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

What is the time limit of the questions in the contest? And i am not talking about the duration of the contest, but the time limit of the problems.

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

    You have 6 minutes to send the solution.

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

      I was talking about the 'time limit' of a question, which if my program exceeds, my program gives time limit exceeded (TLE). That is usually 1-2 sec in codeforces, is that 6 minutes on hacker cup?

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

        There is no explicit time limit. You should solve all tests cases downloaded on your computer during six minutes and then upload answers and source code. Source code won't be run, but they still need it so it'll be possible for jury to check that you're possibly not a cheater (i.e. your solutions looks like correct one for the problem, it is not same with someone's, etc).

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

        They don't run your code locally so there is no such verdict as TLE. You have to produce and upload the output in 6 minutes, this is the only limit.

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

I have solved the second question. I want to download the input file , BUT my internet connection is poor. I'm afraid that the 6 min time limit will pass before i get to download the input file. its about 20 Meg.

Not Fair :(

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

    There is a clarification there to contact them in case if you had problems downloading huge input file on slow connection.

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

Remove all expired time and change 6 min to 15 min ;)

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

Facebook should know that internet speed is not good in many countries. I heard that many coder got timeout but couldn't finish downloading the inputs. This is totally unfair.

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

    Actually, in my case, I had to solve at mid night because of downloading the input =))

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

    Locally solved all 4 questions, but could submit only solutions of problem 1 and 3. Due to huge sizes of input files of problem 2 (12.4 MB) and 4 (18 MB), the 6 minute timer expired for ever in downloading of input file itself and hence I couldn't upload the solutions and output files. (can't say if they are actually correct before system testing)

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

I passed to Round 1, I solved the first problem, but lost the submission time. I'm a loser, I already know :( . The next year I hope to be more preparated for this event.

»
9 years ago, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

Sorry.

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

    Please do not discuss anything regarding content of tasks before the end of the round.

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

      I don't see how this is different or any worse than people discussing the large testcases, which is happening. Anyway, I apologize for bringing this topic up, was just curious to see what people thought.

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

        Large testcases do not relate to content of tasks, it's rather technical issue, so there's nothing wrong with it. Talking about estimation of cutoff can include something like "Many people will fail task XXX, because there are tricky corner cases", which is obviously not what we want here.

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

      I don't think it has to do with the problems' content as much as the point values and generally sorting by difficulty. To me, it sounded like a reaction to this comment.

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

As it has been mentioned already, an input file for one of the problems is almost 20 MB in size. I find this unfortunate, as this puts contestants with slow Internet access at a significant disadvantage (and there are many people with slow Internet access, for some of them, downloading a 20 MB file will take much more than 6 minutes).

Unlike Facebook, Google seems to have considered the problem of slow connections, so input files in Code Jam never exceed 200 KB in size (their problem preparation guide is worth reading). If they need to supply a large input, they generate it using a PRNG, as in this problem.

A suggested alternative approach is to let the contestants download input files in advance in password-protected archives and then provide the passwords instead of input files. This approach is used by IPSC, for example.

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

    At least they realised it doesn't work as well as intended and are trying to fix things (?).

    The IPSC solution is probably the best as long as there aren't different input files, since its only requirements are an unzipper and a working Internet connection (let's define "working" as "can download several megabytes at all") and doesn't put limitations on the set of usable problems. For the more interactive GCJ format, it probably wouldn't work, but it seems usable here in case it was seriously necessary to use large input/output files.

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

      For a contest similar to GCJ, it is possible to encrypt different files in one archive with different passwords. This way, it is possible to put all the input files into the same archive and maintain fine-grained access to individual files at the same time.

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

    My computer couldn't handle the large input files. On BOTH the second and last problems :(.

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

      What do you mean by "can't handle"? I've never seen a modern (<15 years old) environment for which 20MB file is very big to proceed.

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

        Microsoft Notepad))

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

          You can't install anything better?

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

            Install? No I mean I got a certain error due to something related to the computer. I went and tried my program on my Toshiba computer, and it worked :\ :(.

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

              Then why did you say "MS Notepad"? I know it has trouble opening large files, so I assumed it was the problem.

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

                what?

                I did not say MS notepad (though i used that to open my file.)

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

                  Oh wait. It wasn't you I was initially replying to... I didn't notice because your previous post seemed like it was.

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

    Yup, we overestimated what a reasonable input size would be pretty badly, and it won't happen again.

    We're not particularly fond of using a PRNG as it takes away time from solving the actual problem. Downloading input in advance is interesting, but a little clunky. We'll probably just aim for problems that don't rely on large input in the near future.

    For this round, we're letting people email us their submissions if the input doesn't download in time, so hopefully everybody will end up with the score they deserve.

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

      To who am i supposed to mail the solution, please clarify??

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

        "If you're having trouble downloading the input for Autocomplete or Corporate Gifting in 6 minutes, please submit a feedback request by clicking "Give Feedback" at the bottom of any problem page."

        So you have to send a feedback and follow instructions.

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

          Was anyone lucky to get the response for such "feedback"?

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

            Yes I got a response, and sent my solution. Now, waiting for adding the problem before the round ends(as they said).

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

              What? I sent them a response but got none back :\

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

                You should have sent the feedback before the round ended. I did send a feedback before the round, and received a response within 20-30 minutes. You may receive a mail soon, because of the load at the current moments(testing, grading, manual submissions...etc).

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

                  I think i sent it ~40 minutes before the round ended.

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

      I found these GCJ problems that use PRNG-generated input, and these PRNGs don't seem to add much complexity. They even have a problem where the contestants had to download and run a program that generates the input locally.

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

My god! I nearly had a heart attack!

I coded a solution, checked it locally, and it worked OK with the small cases. So then I proceeded to download the input file. When I ran it, my program crashed. "Damn! What's wrong!?" I thought. I immediately realized it was the stack size on my local compiler, which was too small. Then I rushed to Google and searched for a way to increase the stack size. I tried one, it didn't work. I kept on searching, found another one, tried it..... didn't work. Only 1:30 mins left by that time, I was getting really desperate. Finally, with less than a minute left, I found another linker option, tried it out and it miraculously worked! I submitted the problem with only 40 seconds left. Now I know the next time I have to try out the bigger cases as well before downloading the input file.

Let's hope it was not all in vain and I get correct answer for that problem!

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

    Same here :D D:

    I tried ulimit on OS X, and it didn't seem to work. With only 3 minutes left on the clock, I quickly decided to switch to my good'ol Linux virtual machine, ssh'ed into it, and moved all the necessary files to it.

    I realized that I forgot the command to compile, as I always run my program with a prewritten script :D, and had to look up for it, which costed a lot of time...

    Then, for a couple of seconds, I had to think of the size I want to give ulimit... 64MB, 128MB? In the heat of the moment I just entered ulimit -S 100000000 (or a couple more zeros in it :P). I compiled my program, ran with the input file, and could submit my answers at the right time.

    This ulimit trick is something I learned two years ago, which pales a little bit, when compared to some linker options that I've just discovered because of FB Hackercup!

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

      ulimit -s unlimited should help

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

        Nice. This actually worked!

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

        That moment when you discover the solution to your problem on codeforces comments

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

    What was the fix? I had the same story but with a different ending. :'(

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

      I wonder how many more people will fail because of this stupid reason :'(

      The fix is somewhere in CF already, I don't want to help people during the contest more than we already have by hinting that this is a problem.

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

        This problem is not really related to the actual programming.. :\

        It's not really fair to fail people for this reason :|.

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

          i have failed because of this and i think i must wait for another year :/

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

    i think it's unfair to share such thing in codeforces. I had the same issue. If i noticed this before i could get accepted from that problem.

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

      true sad story

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

      yes the same for me; my timer expired because I couldn't fix that damned stack overflow error in time! This is completely UNFAIR!!

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

    Same for me in D. I managed to rewrite my DFS to be iterative, but it was intense ;)

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

    Same here, but with memoization you can do this:

    for(int i=n-1;i>=0;i-=1024)
       calc(i,...);
    

    print calc(0,...);

    Or random calls if you still get RTE.

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

    I'm surprised that many very experienced people (that replied to this) didn't face with this problem in the earlier competitions... I definitely learned this one the hard way.

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

Will I get WA if I use file input/output?

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

When will see results? Right after round ending?

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

    Soon after we should have tentative results. We still take a bit of time to weed out cheaters and look into suspicious submissions before sending out the official advancement emails.

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

some people might love the 6 minutes timer kind of submissions, until unless they come across situation like: Download inputs -> run the code -> minor bug -> correct it(while praying timer doesn't goes off) -> again run the code -> HURRAY correct output -> try to submit -> KABOOM...Timer expired (few second back) :(

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

    When I downloaded input for last problem and run it I got Stack Overflow error and spent a some time searching how to increase it in Java, and then there were some errors with stack size >= 256 Mb, but luckily it worked with 128 Mb and I did submit it 10 secs before time expired :)

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

BTW, It would be cool to see in scoreboard problems failed due to time limit to better understand current situation, wouldn't it?

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

Guys, how did you solve 4th problem?

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

    i'm not sure it's right solution, but i did DP on tree DP[V][COL] = minimum sum for subtree of vertex V, if vertex V have color COL. 1 <= V <= N, 1 <= COL <= 10 i did.

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

      I did the same, but took 50 instead of 10.I think 20 is enough, but took 50 for insurance.

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

      I think 10 is not enough for COL. Try running your test case by using 20 to see if the results change (mine did). If they don't you got some lucky test cases then :P

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

        yes, i tried it yesterday, and in 1 testcase answer decrease by 1 xD with COL == 15 or more.

        COL == 11 is good enough for AC!!!! WTF Big Fail :\

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

          If you swap colors, you can use 5 colors or even less — look at my comment above and my submission at Gym

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

      I'm pretty sure that COL <= log (N) + 1. But in the given test case, I just need about 10 or 11 distinct colors. N is the number of employees.

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

    my solution crashed on 5th test case))

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

      Mine too on local machine, but passed here in Gym. May be stack size? (I am talking about Corporate Gifting)

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

    dp[v][j] -- minimum amount of money when we would have j in node v.

    One can prove that in a correct answer j must be  ≤ degree[v] + 1.

    To calculate it quickly one can precalculate the first and the second minimum among j for each v.

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

      What if we have 1 in all leaves and minimum excludant from labels of children in other nodes? Is it wrong?

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

        i also guessed it at first. But when I simulated it , it gave more value . So its probably not right way .

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

        Suppose root has 2 children and one of them has 1 child. You'll get 1 + 1 + 2 + 3, while you can draw it 1(root) + 2 + 2 + 1(child of child)

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

        Your coloring is 3 1 2 1 1 while we are able to make 1 2 2 1 1.

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

    DFS bottom up. Keep track of the first and second optimal answers for each nodes.

    With the first and second optimal answers for all your children, you can then compute the first and second optimal answers for the current node.

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

    For N vertices it's not necessary to use presents more expensive than log(N).

    Proof: Let a[x] denote the minimum amount of vertices for which it makes sense to use present with price x in a root. To put x in a root, clearly we spend one vertex on the root itself, and then its children have to give presents with prices of 1, 2, ..., x-1 — otherwise we can clearly use a price smaller than x in a root without conflicts. So we get:

    a[1] = 1
    a[x] = 1 + a[x-1] + a[x-2] + ... + a[2] + a[1]
    

    It's easy to see that a[x] = 2^x.

    So we can do a DP: a[x][y] — what is the minimum money that can be spent to process subtree with root in vertex i and so that vertex i buys a present with the price of j. To calculate these DP values fast enough, it's sufficient to remember for every vertex x after calculating all the values for it, what is the minimum value in a[x], on what y it's achieved and what is the second minimum value in a[x].

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

      Once you prove that lemma, a straightforward a[x][y] dynamic programming which stores the answer for all would suffice. Unfortunately, I didn't notice this and did the minimums idea which was not easy to code, at least for me.

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

        Well, I stored the minimums because I got scared of O(T * N * log^2 N). By storing the minimums you can get down to O(T * N * log N).

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

      but what if there are more than a child that give you present with price x-1, does it change the recursive formula? i mean:

      a[1] = 1 a[x] = 1 + m * a[x-1] + a[x-2] + ... + a[2] + a[1]

      where m are the number of people that give you presents with price m

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

        oh sorry, now i get it, is the minimum so you need the minimum in each child, thanks

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

      Is your assumption of the vertex with color x have exactly x-1 children valid one?

      By the above assumption you are assuming a particular kind of tree structure.

      http://imgur.com/vqssnWe

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

        It needs to have x-1 children with all prices from 1 to x-1 for us to be forced to pick a price of x in the root. If it has more than x-1 children, those children subtrees are dead weight and do not limit our ability to pick a price for the root in any way. Since we are looking for the minimum required vertices, we ignore them.

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 4   Vote: I like it +6 Vote: I do not like it

      I think there is: a[1] = 1
      a[x] = 1 + 2 * (a[x - 1] + a[x - 2] + ... + a[2] + a[1])

      At least 2 v values must appear in children. If there is only one v < x value, you can swap it with root and you have v in root.

      So a[x] = 3x - 1 I assumed second y <  = 13. I hope it's enough. (curiosity — When I set y <  = 5 it doesn't change results for my input).

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

        Yeah, log(N) is a really rough estimate, you need a lot more vertices than 2^x to actually have x as a price in the solution. What I wrote was just the easiest proof I could do without going into tricky details of swapping the prices and it was enough.

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

          My friend (Ralph) pointed out to me that the required sequence might be the number of order-consecutive partitions of n. So, the required sequence is:

          For the Corporate Gifting problem, in order to find the maximum $gift used, we need to take the inverse of the sequence.

          I have not completely verified it in full (i.e., I do not have a rigorous proof yet of the precise bijection between the two ideas), but it seems right to me and I followed the intuition behind the correspondence. If you have another way to look at this problem, let me know! Also, I want to point out that the sequence is related to a pot-limit poker.

          Any comments from the community is welcome.

          I had to chew around each of the problems after the contest (i.e., upsolving) to make sure I digested the solution techniques and here is my first attempt at it :)

          Edit: click here for my CF blog entry about 2015 Facebook Hacker Cup Round 1!

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

      Nit: did you think about cases where a node has 'cost' x, its parent cost x-1, and then only existence of x-2, x-3, .. , 1 children costs are implied.

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

    I do not know whether it is right or wrong. As my program crashed with stack overflow and i failed to find a way to increase the size of the stack during my 6min time...... half of the time gone only to download the input file.

    My idea was .... Dynamic programming... We can convert the problem to coloring a tree, we only need to use log(n) colors to minimize the cost....

    How to increase stack size when using gcc ??

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

    The problem asks for what known as a "chromatic sum".

    This paper E. Kubicka and A. J. Schwenk. 1989. An introduction to chromatic sums. http://dl.acm.org/citation.cfm?id=75430&dl=ACM&coll=DL&CFID=619242039&CFTOKEN=73545678 has a linear-time algorithm for finding a chromatic sum of a tree.

    Unfortunately, I couldn't find the full text of the paper on the Internet for free, but you can preview it here: https://www.deepdyve.com/lp/acm/an-introduction-to-chromatic-sums-74F705JQIj?key=acm The algorithm is on the last page.

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

What is the solution of 40pt problem? I could not get it may be because not solved too much graph problems. Have surrounded around bfs/dfs, types of tress , and vertex coloring but could not come up with solution. All idea were wrong I think. And I think only one who solved all 4 problems will reach 2nd round.Congratulations to them.

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

Irrelevant, I wrongly assumed that large files are the same.

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

    Aren't inputs different for every participant?

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

      Hm... I believe they are the same in Code Jam, not sure about Facebook Hacker Cup actually. Post your hash of any of the input files?

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

        They are different; according to a comment on the qualification round; they said that they have a total of 48 test cases from which they select 20 random test cases for every user. Some test cases are included in all files though :D

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

          UPD: No, they are different in Code Jam as well. I have no idea why I was under the strong assumption that they were the same.

          OK, I thought the whole point behind the system was to test your code on as large number of tests as possible and then to avoid just sharing the output file, you need to submit the code as well.

          This is better in a way that it eliminates randomness. In Code Jam small tests, where they are unique for every attempt, you can quite easily get lucky even with an incorrect solution. You can resubmit though, so it's not a huge deal. However on large input, where you can't resubmit, if it's the same, you can't get two participants with the same wrong solution, where one gets AC and the other gets WA just because one is more lucky and didn't get any bad test cases.

          I still believe Code Jam's large input is one for everyone for these reasons, unless someone can show that I'm wrong.

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

    How to simply calculate this hash?

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

    A: d0ee7647ad6dd0014a1dd5d197805964 B: 57664116c970da2d8be396e36c872a61 C: 24da720c50105b958cd5ae9129c2653b D: dd04084a224c69ea300931f1fca8ef69

    Indeed it looks that there are at least two different inputs :)

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

      And here are my inputs (the larger ones are still uploading): https://drive.google.com/folder/d/0B2d37tm1YmE3a0xMLTJFdDZyams/edit

      If somebody is not lazy enough, please post the MD5s of your outputs on these inputs :)

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

        Note, that endlines(win vs linux), extra spaces, #s will affect md5 but not correctness. Solutions are quite small so its easier to compare them directly

        Would you share your outputs? I get both hashes different:)

        My outputs

        Hashes with \n as newline

        ac78b81e3db66c301db1fd4d847543eb  autocomplete.txt
        d1a57df20500e6fcab12d1a9b30f4734  gifting.txt
        1a126e2363aa662c1749fe174d3a0b94  homeworks.txt
        3e6c597d827ad5779b8df450b3dfd20b  winnings.txt
        
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Mine have Windows newlines, no extra spaces, and have #s.

          I'm doing this from a phone, copying outputs would be cumbersome :(

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

          Got the same output with these 4 inputs.All i need to do next is bless the manual judgement will give the correct answers.....

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

          all outputs match :)

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

        I got the same hashes for output files (\r\n after every case, including the last one) with your input files for all problems.

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

        OK, got same hashes with \r\n newlines

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

        Either we made similar mistakes...

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

      I have the same hashes for A,B,C)) Thanks for sharing!

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

    All my hashes are different from yours. So let's hope our inputs are different :)

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

Note to self: 1<<20 is smaller than 1e7.

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

    Rule of thumb for quickly estimating powers of two:

    • pow(2,10) == 1<<10 == 1024 > 1000
    • now estimate e.g. 1<<23:
    • pow(2,23) == pow(2,10) * pow(2,10) * 2*2*2 > 8.000.000
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the answer for the 3rd problem's input: 1-0

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

    1 1?

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

    1-1

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

    it should be 1 1 cause only one way to achieve this

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

    1 1. Since there always is a way to meet the requirements (AA...AABB...BB for first and BB...BBAA...AA for second) and there is only one way irregardless of any restrictions anyway.

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

    Thanks, I also think 1-1 is the right answer.

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

    OK, looks like I made a dumbest mistake ever. My output is "1-0". But at least I believe I solved D. Congratulations to all advancers!

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

    So a victory of 1-0 is stress-free and stressful at the same time?!

    This makes no sense whatsoever :)

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

      1 1 makes sense for 1-0:

      stress-free: you score the first point. Only 1 point, only one way.

      stressful: you score higher only when opponent reached final score. He never scored, so he reached 0 points automatically.

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

        Formally yes, when considering this part of the statement: "In a stressful victory, you never have more points than your opponent until after their score is equal to their final score."

        But it is rather difficult to follow a transition from "The two most extreme kinds of victory are called stress-free and stressful" to "well, they can actually be one and the same thing" :)

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

          Well, it's also quite difficult to imagine a match with score 2000-1999, if we want to think this way...

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

    It can be "1 0" also.

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

Why thinking bottom-up is so much harder than recursive DP :(

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

    Because u need to then know the order in which uhave to run the loop in a directed way, but when u have a recursive dp this order is already maintained by recursion, It means that having the recurrence with you you just need to know the order in which to evaluate in bottom up, well both are same , choose what u like, i prefer bottom up dp..

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

      I prefer recursive DP, but there is a big cost of doing that. Sometimes a O(n^2) recursive DP can be achieved via a O(n) bottom up dp.

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

Almost 1000 people answered all four problems.... looks like you can't make any single mistake in order to go to the next round...

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

    Last years showed near 50 percent wrong submission and two any problems were enough.

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

    Submitted on != answered correctly.

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

      I know... but given that there are 1000 people...

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

        If only 499 don't fail on at least one of the 25pt problems, 75 will be enough to go to the next round.

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

          In my opinion, the sample tests for the two 25pt problems seem pretty strong. Especially the last test case for the third problem. Also, the Trie and DP implementations seems pretty standard as well. I don't think the fail rates would be high for these two problems.

          I guess most failed submissions would be on the last problem because of the weak samples and more corner cases. But I still wonder the fail rate could reach 40 to 50%....

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

            One test: 1-0.

            I found that one when I manually tested my solutions (strategy) and I think a lot of DPs can fail on it.

            Autocomplete doesn't have a truly large test and, while the samples warn about one word being a prefix of another, they're not that strong. It will probably have a higer AC rate (discounting possible download fails), but failing it means losing as many points as when failing Sports, further increasing the number of people with exactly 75 points.

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

              I also thought about this testcase. It's both stressful and stressfree, right?

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

              Eh, it's kinda bad if the difference between passing into Round 2 or not is in handling that corner case, to be honest, it could be included in sample tests.

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

                You have 24 hours and are free to use them however you want. I tested my solutions manually, using bruteforces, checked if they don't fail on large random tests etc. It's about an hour or two more, but finding that missing case was worth it. At this point, anyone can pass as long as they deserve it (can solve the problems) and aren't careless.

                (If you don't have the time — that's your choice of time management.)

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

                  Nothing about the format selecting people basically based on how much time they had available, then?

                  I thought you were the guy complaining about how topcoder was supposed to be more about thinking and less about avoiding dumb mistakes.

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

                  There's a HUGE difference between 1.25 hour and 24 hour contests.

                  You don't see me complaining about tight time limits or this troll problem (find the missing piece of information) in Codechef Long contests. It's the same thing — there's a place for everything. Just as short contests aren't the place for overly technical problems or little given info, long contests aren't a place for no hard problems.

                  Just imagine that you assign a score to each contest — the chance of getting a good result. That chance depends on the quality of samples, syllabus, feedback, the problems' intended difficulty distribution, name what you want — but also contest duration. You can't cast judgement without taking into account a lot of these things, and that's what I did in my recent rant against the recent low success rates of TC problems.

                  Tl;dr if SRMs were 5 hour long, I would shut up.

                  UPD: And no, "I don't have enough time because I'm doing something else" is not a valid complaint, since you got something out of doing that something else. There were like, 3.5 hours intersecting with other programming competitions (1.5 out of which was the Cookoff server crashes).

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

                  Well I ain't saying that it's okay to make mistakes like one I mentioned, but sometimes you just skip that corner case, by accident(it surely happened to you a lot of times, maybe before you became that good), the pass to Round 2 shouldn't be that hard achievement, and some really silly mistake can take it away from you, if the 0-case got included into pretests, everyone with correct C solution would have all the points required, like in D task, they included the test where bottom-up strategy didn't work and it prevented a lot of possible wrong answers.

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

                  If you notice, I actually started out saying that many people failing this could get them and more people to round 2, since 75 points (for example) would be sufficient. We don't know the results yet; it would seem that I have a full score, but I can still fail and... well, I did my reasonable best (I checked my solutions a lot, but didn't spend the whole 24 hours on it), but there's still a possibility of failure to deal with and it's kind of silly to attribute it to thinking "it's just round 1, it will be easy to pass". Last year, user:WJMZBMR failed the qualification due to trying just one problem and getting it wrong. That's also negligence.

                  We get such lessons sometimes.

                  And 500 isn't much, that's like passing from GCJ round 2. Except there are time tiebreakers there (and the problems are harder).

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

              According to you, what should be the correct answer for this testcase should it be 1-1 or 1-0.

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

                Read the comments above.

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

      I'm guessing that many people will fail on C and some will fail on D. It seems hard to fail on A or B. I'm not sure if 75 points will be enough to qualify; I'm curious to find out.

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

        (many people will fail on C) Why do think so? what's the deal? :D

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

          Tests like 1-0 or 1000-0.

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

            Correct answer is "1 1" for both, right?

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

              Yes.

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

                Why do you think there will be many wrong answers with these test?

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

                  People first iffing out the j = 0 case, then the j = b case. :)

                  I might be wrong though.

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

                  lol and I'm proud to say that I'm one among them who will fail this case , good case and silly mistake didn't think about it and yes I think many will fail in this case .

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

                  I'm very curious on what were your approaches. I mean, I had no need to handle any kind of strange case explicitly (they were implicit on how my DP was built), but it seems the aforementioned mistake is, in effect, made by lots of people.

                  I'll be glad if you share them with me :)

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

Please note that we will not accept any manual judging requests after the round has ended.

How did some contestants guess that they should submit their code for manual judging?

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

    There was a notification for majority of the round:

    If you're having trouble downloading the input for Autocomplete or Corporate Gifting in 6 minutes, please submit a feedback request by clicking "Give Feedback" at the bottom of any problem page.

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

      "Feedback request" doesn't mean "manual judging". In particular, it doesn't say anything about submitting just the code, which is the main problem here.

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

        I assume that this meant, please write to us and then we will explain to you what to do. If they made a public announcement "if you had problems, please send your code to this e-mail", I fear that they would receive enormous amount of non-legitimate submissions, which would have taken ages to process correctly.

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

          Yes, that's possible, and could be the answer to Rubanenko's question. Under "manual judging", I imagined just submitting the code without the output, since judging these could be made a lot more automated than a few admins answering a lot of mails.

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

i have sent a clarification due to submit issue in last 10 minutes but no answer tell now?!!

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

Let's judge our solutions in Facebook Hacker Cup 2015 — round 1: http://codeforces.com/blog/entry/15864

»
9 years ago, # |
Rev. 6   Vote: I like it +48 Vote: I do not like it

It will be a long day at Menlo Park. :)

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

    Indeed, it's been a long few days this round :)

    We made a lot of unnecessary work for ourselves and others. Luckily, we've learned a valuable lesson that shan't soon be forgotten.

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

      when you show us the results?

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

        The tentative results should be announced later this evening.

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

      Now you'll be testing future rounds on a typical internet connection? ;)

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

Last problem is same as one of the boi 2003 problems. I assume you expected few accepted from last problem since it was the hardest one.

By the way why limit of N is 200000. Anybody get hurts if it was 50000 or something? You could have get rid of 20MB issue.

What I am trying to say is from my point of view Facebook hacker cup is the worst online competition I participated in this year. I have never encountered interesting problems, just technical situations!

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

    Except from looking at the solution, the expected solution at BOI (Baltic OI, for the reference) 2003 was O(N^2). Which eliminates the need for understanding that you can limit the numbers you are using, which is exactly what makes the task interesting and challenging, in my opinion. Also I highly doubt that a lot of people knew exactly the same statement was used there (I didn't, and it was from my region, although before I competed). Including the organizers. Coming up independently with exactly the same task isn't too difficult.

    As for N = 50000, I believe O(N^2) could pass with these restrictions.

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

      You are wrong. Just because constraint of N is 10000 you can not say expected solution was O(N^2). You are judging like in 2003 we had same computers. 10 years ago computers were much more slow. Also official solution of the problem is O(N).

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

        All I can see regarding the solutions for BOI 2003 is the archive from the former Lithuanian IO website. My claim that the intended solution is O(N^2) was from the fact that there is a quadratic array and I assumed was used for DP. I was wrong. Inside it is a "solution" for the task, which uses constraint <= 1000, stores the graph in O(N^2) memory and assumes we won't use number greater than 3, which is incorrect. I have no idea about the origins of this archive, it looks like it's rather unofficial but I cannot find anything else. Still, to do a quadratic DP, we actually need to store all of the values, and they had only 64 MB of memory, so yeah, likely not O(N^2).

        I claim that you're also possibly wrong, though. For O(N), the restriction is way too small (they had N <= 10^6 restriction in one of the other tasks). If you can show any proof that the official solution of that problem was O(N), please kindly do so. I believe it was O(N log N), in this case.

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

          As tom pointed out upper bound of colors is not log N it's 5. So we can assume it as constant factor. Official solution uses 3 colors too. So why do you think complexity of solution is O(N log N). It is obviously O(N).

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

            If the problem in BOI is exactly the same, for my input of FBHC the results changed when I increased the number of colors until 20 (e.g between results using 5 or 6 colors, 6 and 7 colors, and so on), some other people needed 15. So I think around 20-25 should be the minimum number of colors to be sure it is correct, which is approximately to log2(200000). Also a friend found a thesis manuscript about the subject proving that it was O(lg n), I'll try to find it to link it here.

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

              It's obvious that log n is enough. But I'm not sure it is necessary. Is there a proof that we need at least log n colors?

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

                Unfortunately I cannot find the paper I mentioned, but if 3 colors were enough for the other contest with lower limits and at least 15 are needed for this one with higher limits then the number of colors seem to depend on N and not be constant, but I am not sure how to prove the exact growth rate.

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

                  It looks like number of necessary colors is polylog n.

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

                One obviously can construct an example where k colors are required for any given k. Just start from 1, and on the k'th step attach lots of constructions for k - 1, k - 2, ..., 1 to a new vertex.

                Besides, your arguments like "As flashion pointed out upper bound of colors is not log N it's 5. So we can assume it as constant factor" are ridiculous. It almost seems like you have no idea what is a rigorous mathematical proof.

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

                  You are right 5 does not have to mean constant. But in practice it is close to log log n which is too little.

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

                  Where did you get log log n from? Please stop making random statements out of nowhere and try to prove what you're saying (or at least read the comments above). It is O(log n), as pointed out multiple times in the comments, e.g. here.

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

                  In fact, at the k-th step it's enough to add 2 (k-1)'s, 3 (k-2)'s, ..., and k 1's. With this construction, the size of the tree at the k-th step is given by this sequence: http://oeis.org/A007052 which grows exponentially, and therefore the log N bound is tight.

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

            Let me translate what you said:

            "As tom pointed out, on his input data his answer doesn't change if he uses only 5 colors. So we can assume that if we have N vertices, amount of colors used is O(1)".

            I'm not sure if there's any point in continuing this if you're making arguments like that. Also you keep mentioning official solution without ever providing a link to one. Writing "obviously" doesn't make one right.

            I'm not saying that you're wrong, I can imagine that the actual bound might be different, but you need to provide valid argumentation for your points, otherwise this whole conversation is a complete waste of time.

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

              Here is link to the solutions Link There is no proof tough.

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

                No, this is an archive (which I have posted a few comments ago *), and as I mentioned a few comments ago *, this archive doesn't look like an official solution, since its author is a Lithuanian (whether BOI 2003 was organized by Estonia, perhaps things have changed recently, but as far as I know (and I was on the organizing team of BOI 2012) other countries submit tasks only, whether actual task selection, test generation and solution implementation are left to the organizing country). He also participated in online contest of BOI 2003 and scored 0 on this task.

                (*) Are you even reading replies to your comments?

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

            Imagine you have n trees that you need 1<= i <= n : i colors for painting those trees with min cost.

            Lets form the tree with n+1 colors with min cost:

            You get the root node.

            you will connect to it ((n+1)+1) nodes with cost 1,

            You will connect to it ((n+1)/2+1) nodes with cost 2. ... you will connect to the root: ((n+1)/i+1) nodes of min cost:

            The root will have n different colors connected to it. So the root need to be painted of the color n+1.

            What about try to swap colors? You can figure out that is is more expensive. With this I conclude that you may need variable colors for painting the tree with min cost. I haven't prove that you need lg n colors. A friend did research and found an algorithm O(n) in time but anyway you need variable colors for painting it with min cost.

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

    It was also given at CERC 2 months ago as a problem on testing session. And its significantly harder version was present in snarknews new year's contests (problems -> http://newyear.snarknews.info/files/2014/prob_p.pdf ) (that fact implies also that this was given on some Russian ACM-ICPC style contest)

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

I've added the round to the Gym: 2015 Facebook Hacker Cup, Round 1. Feel free to submit your contest solutions in practice mode to get expected verdict right now.

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

    Memory limit exceeded on test 2 (Autocomplete) However it runs fine in my 8G machine :)

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

    Hi mike , what will be the running time for each and every problem ? does the 6 minute timer means that your problem will be allowed to run for 6 min ? if there is time limit applied to the problems in FB hackercup can you mention them here ? thanks .

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

    My solution for A (Homework) runing more than 2 sec on my computer (4Ghz processor) and les than 1 sec on codeforces (3.5Ghz). How it's possible?

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

      I think it is because of the options you use for compilation. For example, codeforces uses the '-O2' flag, maybe you aren't using this.

»
9 years ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

For problem 4, this paper explains a simple O(n) algorithm — http://www.public.asu.edu/~halla/papers/OCCPWG96.ps

My implementation — http://codeforces.com/gym/100579/submission/9468814

This problem on uva is pretty similar http://uva.onlinejudge.org/external/113/11307.html

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

Problem #3 is a problem dating back to ~1880, with a very short closed solution:

"In combinatorics, Bertrand's ballot problem is the question: In an election where candidate A receives p votes and candidate B receives q votes with p > q, what is the probability that A will be strictly ahead of B throughout the count?"

http://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem

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

Solution to problem 4 was dp + dfs.

Here is mine accepted solution of it in codeforces gym. http://codeforces.com/gym/100579/submission/9474632

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

    It will be great if you could post your solution somewhere else since users who did not solve this problem can't see your solution. In codeforces gym, you can't see solution by other people unless you have solved that problem.

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

In the 3rd problem "WinningSports" for the case of x-0 the number of stress-free win should be 1 and stressful win should be 0 or both should be 1.

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

    both one

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

      I did this mistake during the contest :(

      There was no chance to debug our code or correct our algorithm in proper time. That's not a good idea I think.

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

        Actually, there was time for "corrections", which has caused my failure in this competition: implemented solution according to the formal problem statement ("1-0" -> "1 1"). Downloaded test file, generated the output, had some time to inspect test data and my results. Noticed those "n-0" cases. Intuitively my response seemed wrong (how can the same sequence be both stressfree and stressfull at the same time, I thought), so I went to fix my solution to return "1 0". There was enough time for that, and for submitting the "fixed" solution:(

        It's all my fault, I know. But I just hate when formal problem statement contradicts common sense.

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

        There was no time for what?

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

          I speak about getting WA on some pretests like codeforces, or on small input like codejam.

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

... Then, Do you think that 60 points is enough to advance to Round 2?

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

Guys... ranking has been changing... I hope it's final migration of manual submissions

»
9 years ago, # |
Rev. 6   Vote: I like it +81 Vote: I do not like it

UPD: While 500th place got 100 points, if manual submissions are omitted, 500th place have 75 points, so as promised by organizers, the cutoff will be 75 points. It's a reasonable cutoff, allowing contestants to fail one of three easier tasks, so my original comment below is a rant about what could've happened. Still, I'd like to organizers to remember that in the future, to avoid having rounds with cutoff of full score, as it would've happened if not for the whole saga with 20 MB inputs.

Since there are now 1140 people with pending 100 points, I believe the most likely scenario is that the cutoff will be 100 points — I don't believe there is a case so tricky that more than half of the people will fail something. Don't really think that even selecting top 500 before adding manual submission will help the issue here. In case it's miraculously not 100, everything said below is irrelevant and I apologize. I also apologize for technically speculating on the cutoff, however I believe that it's the most likely scenario and would like to express my opinion before official results are released, especially since the organizers are reading Codeforces.

The cutoff of 100 means that the organizers screwed up big time and turned this round 1 into "whoever doesn't make a silly mistake" contest. With that in might, I find the organizers claim:

"I don't think this should be a huge concern to the eventual top 100 who will advance from Round 2. If there is anybody who did not legitimately succeed in Round 1, their chances of ending up in the top 100 in Round 2 are extremely slim (in my opinion)".

rather hilarious. Yep, guys, if you made one tiny mistake in one of the four tasks (and keep in mind, this is not Code Jam, where you at least can be semi confident in your code by small test case), your chances of getting to top 100 are extremely slim in their opinion. Setting aside all input data size disaster, I believe the organizers should admit that they screw up qualification round, potentially eliminating lots of strong candidates in early round and at least set the cutoff to 61, essentially allowing people to go through with bugs in A and (B or C).

Before comments claiming I'm just rage posting start to flow in, just want to mention that I myself am passing all the tests at Codeforces, so I expect to get a 100. Which doesn't eliminate my opinion above that this round failed to fairly select 500 participants. Some people were worried even before the round due to the format, however last year Round 1 didn't suffer from any of these problems and distribution was really fair despite it being 48 hours, so I still believe it's possible to have a fair elimination round with this format, it's just difficult to pull it off.

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

    In this case I will be a saaaad panda with 90 pts.

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

    You were heard. :)

    "The manual submissions have all been entered, so the scoreboard now shows the pre-judging results. Before the manual submissions, 500th place had 75 points. But afterwards, the top 500 all had 100 points! In the interests of maximal fairness, we'll be using the pre-manual submissions cutoff of 75 points for advancement. We'll be revealing the judged solutions in about an hour, so stay tuned!"

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

      Well, they promised that they'll use pre-manual submissions cut-off beforehand. So yeah, cut-off ended up being reasonable purely because of the problems with downloading times. In essence, they avoided a fail by having another fail.

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

        We were hoping for a cutoff of 60 or 75 when we made the problem set, so we definitely misjudged the difficulty of the set. Last year I think the cutoff ended up being 40 so I guess we overcorrected. Let's call it binary search :)

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

    it's possible to have a fair elimination round with this format, it's just difficult to pull it off.

    And you'd think someone who showed clear inexperience would pick one of the "reasonably easy to get right" format options... This is just asking for trouble.

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

    While you do have a point, overall your comment is way too aggressive IMO. I understand that one can be very frustrated because of some troubles with a contest (I myself did such a mistakew in the past, aggressively criticizing contest because of some issues, and then re-reading my own comments and being ashamed of them), but try to put yourself in the shoes of organizers: they've spent lots of their time preparing the contest, and now participants post comments like this one. It must be very demotivating.

    IMO the critics should be mild and constructive. This time, there were two issues:

    • Large inputs. I wouldn't even blame FBHC organizers for this: if you look at recent products build in Bay Area, most of them suffer from this problem (i.e. they're not slow-connection-friendly). I think the whole industry would benefit a lot if there is a mandatory "dial-up day" in the whole Bay Area once per month :) With bandwidth 56Kbits/s for everyone, so that developers experience their glorious creations over slow connection.

    • Round structure: 24h, cutoff is the score of the 500th person => tiny mistake leads to failure. Indeed this was pointed out before the contest, and indeed many strong participants and finalists of the previous years did not advance (e.g. niyaznigmatul, Jacob). Yes, this was a mistake, and people should learn from such mistakes. But stating something like "organizers claims are hilarious" is a bit too much IMO — we should be respectful to organizers.

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

      I have tried to be fair and did not make claims that it was "worst online competition" as some people did in this thread. As I mentioned in the beginning, I no longer have such a strong view of the situation, since the situation would be much worse than if the cutoff would have been 100 points.

      Still, I have the same position on that quote, and I can't really see anything disrespectful in pointing out that their claim was hilarious. I rather find it disrespectful from the organizers to release this quote under any circumstances with or without imo clause. In this particular case, when the task selection was inappropriate for the purpose under the given format, I found this quote to be funny as well, since it was clear that some really strong participant would be applicable to this (when at least D was definitely going to be mandatory). So, turns out that wjomlex made an indirect statement that ACRush and niyaznigmatul in his opinion have extremely slim chances of getting into top 100. Which is obviously not true, and obviously wjomlex wouldn't ever made this statement in this form. This is why one needs to be careful about what he says and how it can be interpreted before publishing it, especially if he represents one of the biggest programming competitions in the world.

      And I didn't blame organizers for large inputs, since I can understand that this issue might be completely overlooked by accident. Not thinking about the fact the given problemset might quite possibly be solved completely by more than 500 people is much less understandable. I haven't also heard any apologies or reflections on problemset or format in the end. For all we know, the organizers might think that the problemset was reasonable under this format.

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

        Ah, I think my comment was misconstrued. For ease, let me repeat it here:

        "If there is anybody who did not legitimately succeed in Round 1, their chances of ending up in the top 100 in Round 2 are extremely slim (in my opinion)."

        By "did not legitimately succeed", I mean anybody that managed to get into Round 2 because their manual submission was accepted even when they wouldn't have succeeded themselves under normal circumstances. As people have pointed out, there are likely a few manual submissions that would have not been ACs because of stack overflows if we weren't handling them.

        I definitely didn't mean "anybody who failed to advance to Round 1 would definitely have no chance advancing from Round 2". That would be silly. I've been in this situation before when I failed to advance from Round 1 of Hacker Cup because I was modding by 0xfaceb00c as an integer, and not as a long :P

        As mentioned in a comment above, we did overestimate the difficulty. We were aiming for 60 or 75 to be the cutoff. Would we have adjusted the cutoff if everything went well and >= 500 people scored 100? That's tricky. On one hand, following the rules seems decent. But I'm pretty consequentialist, and I think that lowering the cutoff to 75 anyways would be a better plan in such a situation.

        60 was definitely the cutoff I was rooting for before we started. This was my first time helping build a problem set for a 24-hour round and I think we ended up with something that would have been pretty decent in a 3-hour round, so now I'm better calibrated on this front.

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

          Thank you for your clarification. I do get what you meant now and it indeed makes sense. I apologize if I offended you due to my misinterpretation of your quote.

          In any case, one of the solutions I suggest if you want to keep 24h rounds in the future is to adopt Code Jam's approach to long rounds and avoid selection by rank and just define the cutoff yourselves, stating that everyone who gets X points advances to Round 2.

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

            Yeah, I'm definitely interested in doing multiple sub-rounds like GCJ or, like you say, simply picking our own cutoff.

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

          I can easily see a very good coder using the loophole to fix the stack overflow, so I still don't agree 100% with the quote. But as Swistakk pointed out below, you handled this issue in the best way possible, so that was a positive point.

          I think for the ideal cutoff you would need 3 problems to pass (so A+B wouldn't pass, but A+B+C would, and D is there for some buffer room). One of the issues was that you picked easy problems, but the biggest problem is that you picked a format which does not allow you to misjudge the difficulty. Hopefully we'll see some improvements in that front next year.

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

            Yeah, 60 would allow for any 3 problems, which I would generally prefer. I would imagine that next year we would just set the cutoff.

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

Daaaaaamn. Cutoff is 75 ;____;. I'm so sad :<.

That problemset was too easy to fairly choose 500 people :(.

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

    Fully agreed. A textbook trie exercise (I can't even call that a problem), followed by an amazingly obvious DP.

    How did they think this would work to select 500 people? Just look at the problemset for Code Jam Round 2, which was a lot harder to select the same amount of people with a much smaller duration.

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

      Maybe this problem set is easy for you but I see a lot of people failing the first try of few problems here

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

      registei ca só pra dizer que vc ta falando MULEKADA. Fácil pra vc, não para milhares de pessoas.. Seja mas HUMILDE quando FALAR em PUBLICO...

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

        It's obvious that people that didn't train for these kinds of contests would not find the problems easy. I did not mean to imply otherwise.

        However, precisely because difficulty is such a relative term, it needs to be properly calibrated for the event in question. You wouldn't use the same standards to select members for the running team in your school and to select runners for the Olympics. Similarly, a round that proposes to select only 500 people from the whole world and in which more than 500 solved all problems is definitely too easy. My and your relative skills have nothing to do with that.

        Now that you found this awesome website, maybe you can train harder for Hacker Cup 2016? :)

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

    At least I am not sad at all, because for me it means just losing a t-shirt:)

    But still it looks like organizers screw up this time. Lot of guys who usually participate in onsite rounds of such competitions — haven't qualified at all.

    And GCJ looks much better in picking top-contestants for late rounds, comparing with this edition of FHC. FHC don't have to copy GCJ contest rules, but maybe they should look for some ideas there. I don't know actual goals of FHC. On the one hand, good performance can give additional motivation for beginners, increase popularity of competitive programming and so on. On the other hand, I don't think that they really want to see some random folks in next round, instead of Endagorion, ACRush, niyaznigmatul...

    I think they should provide some "not div2" problems next year (at least like last year... or maybe even a bit harder; not just 4 textbook exercises), if they want stronger field in Round 2. Last year netkuba got 55 points in round 1 (failed both B and C) and later got #18 at Finals; niyaznigmatul was #4 in Final round with 55 points in round 1 (only A and D submitted). RAVEman got 7th place in Final with only 40 points in Round 1 (A and C; failed B and D). andrewzta is ranked 6th in Final with 60 points in Round 1 (B and D; failed A and C).

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

      Best algorithm for goal "picking top-contestants for late rounds":

      sort(contestants.begin(), contestants.end(),
        [] (const Contestant& lhs, const Contestant& rhs)
          { return lhs.rating > rhs.rating; });
      
»
9 years ago, # |
  Vote: I like it +111 Vote: I do not like it

The only good thing so far about FB Hacker Cup is that it has shown us to appreciate Code Jam.

»
9 years ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

Apparently, in the first problem, a lot of people decided to combine 2 steps of "finding primes" and "use them to calculate the number of prime divisors for every number" into a single step by using the same approach as in Sieve of Eratosthenes and forgot that unlike in sieve we do need to consider primes greater than sqrt(N) in the second step.

»
9 years ago, # |
Rev. 2   Vote: I like it +72 Vote: I do not like it

The manual submissions weren't fair at all. There are people who claimed they didn't have time to submit in the feeback form when, in truth, they suffered from stack overflow and modified the solution before sending it by email, while other people resigned themselves with this and didn't cheat. I don't think Facebook had the means to check whether such a feedback form was a valid complaint or a scam. At least they tried to compensate by taking the pre-manual-submissions cutoff, otherwise I'd call this entire round a joke.

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

    True, but anyone who went to Round 2 like that won't get t-shirt or advance even more, so nothing bad happens, and they even set the number of points to advance without manual submissions, so noone gets anything bad because of the manual submissions, right?

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

      There are people in the top 500 who have pulled this off and will get a T-shirt. And advancing to round 2 is a reward in and of itself, which has been denied to some and granted unfairly to others.

      EDIT: My bad, I now understand that the top 500 people in round 2 will receive T-shirts. Still, my second argument holds.

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

        Well, maybe they granted advancing unfairly, but it's not denied to anyone, and the guys who cheated to advance like that won't be able to succeed even more, right?

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

    Once bad stuff happened, what they did with that mess was pretty wise. Taking premanual cutoff was a very good decision.