Блог пользователя bli0042

Автор bli0042, 10 лет назад, По-английски

I've seen two sources that claim Facebook Hacker Cup will begin with the qualification rounds Jan 8-11 this year, but it's getting awfully close to January 8th and I am somewhat skeptical given that the Facebook page hasn't been active since February 2014 (facebook.com/hackercup).

Anyone else planning to compete that knows some more information?

  • Проголосовать: нравится
  • +115
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

There is message dated last August with schedule, and qualification is Jan 8-11 indeed

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I'm about to ask the same question.

I remember seeing the schedule long time ago, but the official post seems to be removed.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +72 Проголосовать: не нравится

    It's actually not removed, but somehow only shows when I'm logged out from Facebook.

»
10 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Complete schedule(Only visible when logged out of FB, as pointed out by Petr]):

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does somebody know exact start time of online rounds?

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

Information about Facebook Hacker Cup 2015 has been released.

The most interesting detail is that top 500 in Round 1 receive T-Shirts (it was 100 last year). Note that this is likely not the same as "everyone in Round 2 receive T-Shirts", as Round 1 is 24 hours long and everyone with the same number of points as 500th place also qualify to Round 2.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This will be my first time competing, so can somebody confirm that from the wording on the site that once you submit a problem you are not allowed to resubmit? This is different from both codeforces and topcoder where one can resubmit if they realize that their solution is incorrect. Is my interpretation of the wording correct?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi guys,

Thanks for the useful replies! It looks like they decided to post less than a day after I posted this. The official posts are https://www.facebook.com/notes/1029173677098533/ and the most recent one.

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Why do I need to write my phone number?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Because this is Facebook? :D

    Nah, maybe as a extra precaution in case you can't be contacted by e-mail or something.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Am I the only one who does not find the link to the problems? The Qualification Round seems to have started already according to https://www.facebook.com/notes/1029173677098533/ -> http://www.timeanddate.com/worldclock/fixedtime.html?msg=2015+Hacker+Cup+Qualification+Round&iso=20150108T00&p1=%3A

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

When submitting the source file, do I have to include freopen for stdin and stdout? Or it doesn't matter?

»
10 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Is there any web page where I can see the scoreboard for my country (or for any specific country)? I am very eager to see how they are doing in the Hackercup!

»
10 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Why people under 18 can't participate???
At the GCJ and YA children can't participate only in onsite finals!!!

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    It's not "you can't participate". It's "they can't find out".

    In other words, use false info or a dummy account. In this case, the end fully justifies the means.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am new to this contest. Is there any time-limit for the problems or I need not worry about time complexity?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You have 6 minutes time to run the code on your computer.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You are given an input file, and need to submit an output file (answer) within 6 minutes. So unless you have a super computer, you need to care for time complexity, but it is not severe since you don't need to super optimise your program because of overhead.

»
10 лет назад, # |
  Проголосовать: нравится -107 Проголосовать: не нравится

Solutions For Facebook 2015 Hackercup will be posted here: http://neonos.net/hacker-cup-2015-qualification-round-cooking-the-books/

»
10 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

Если в 3-й задаче абсолютно забыть про стенки, ответ на семплы не меняется. Ну вы поняли, что я сделал.

»
10 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

How could I submit solution to check it in practice session? Now I can only download input file and nothing more

»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Lol, failed second task because of printing "Yes" and "No" instead of "yes" and "no".

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Fun fact: turning the lasers counter-clockwise instead of clockwise in Laser Maze passes all the samples and 11/20 tests.

Out of curiosity, I've investigated which test cases I've passed, and it looks like with exception of "SG^" and "SGv", I pass all the smaller tests in the data, failing only on larger ones. So I'm wondering whether it's the case of lucky coincidence in hand-crafted tests or whether changing the direction of turning for the lasers on a relatively small randomly generated field has a high probability of not affecting the answer.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Turning them in counterclockwise order instead of clockwise you mean?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry, and are are you look the results of system testing? I mean the the tests not only verdict OK/Failed.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I mistakenly took "V" instead of "v" for the laser pointing down. Passed all samples and half of the final tests too! Was a minute slow to rectify my mistake in the allotted 6 mins.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    Yeah, I made sure the sample data could be passed regardless of how you spin the turrets. In a contest like Hacker Cup with no immediate feedback, I normally wouldn't be as vicious with the sample input, but given that you can solve either of the other problems and advance, I figured it was fair game in the last problem.

    Glad someone noticed :)

»
10 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Third problem was the best BFS I have ever done in online competitions.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Such a pity to get WA because of using ArrayDeque.push instead of ArrayDeque.addLast. Always have thought that "push" means to add an element to the end of a deque. But Java documentation states that "This method is equivalent to addFirst(E)".

Be careful!

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    The same happened to me before. What I do now is just to use the add/removeLast or add/removeFirst methods just to be sure. As I normally don't remember and don't want to waste time reading the documentation during the competition.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Push and Pop work at the same end. Add works on the other end. You can pretend you're adding to the end of the queue with Push as long as you remember to use Pop if you want to take the last pushed element.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +69 Проголосовать: не нравится

I hope some organizers of Facebook Hacker cup read Codeforces, because this comment is meant for them.

Every year, I hope that Facebook Hacker cup would get better, but it is still terrible year after year.

  1. Problems are too easy. I know this is Qualification Round, but if you look at GCJ, they always have nice problems, even for this round. Do you run out of problems?
  2. No validator. Just 1 regex to check contestants' output, is that so hard to do? Having people failed because of lowercase/uppercase, or things like "Case #1" vs "Case 1" is just bad. Every contest platform I know of have some way to prevent this.
  3. I sent clarification during contest, but got no reply. Is no one responsible for answering clarification? If you found my clarification stupid, at least reply "No comment" or even "Read problem statement again". Do you just write some problems, start the contest and then left it?
  4. Problem C is too badly written. There are many ways to wrongly interpret it. In test case:
1 5
S..G<

Why is the person not killed? Is it because he cannot die at first turn? Is it because the lasers cannot pass through S cell? Is it because the laser can reach cell G but cannot go through it?

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Just curious, who are the authors for the whole facebook hacker cup 2015? If I remembered correctly, the authors in GCJ are revealed to public (most of them are red in CF as well), but I couldn't find such info in FHC.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      LoneFox and I are two of the authors. There are a couple others, though I'm not sure what their CF usernames are.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What is the correct answer to your last question?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +30 Проголосовать: не нравится

      Number 4 is clearly explained in the problem statement:

      Every time you take a step (either up, down, left, or right), every laser turret in the maze then rotates 90 degrees clockwise, and then shoots a momentary laser blast in the direction that it is facing.

      Thus before you move at all, the turrets haven't shot anything. After you move, the turrets turn before shooting. You have never been in danger of being shot as you moved to the goal. But of course, the seemingly similar testcase:

      2 5
      ...Gv
      S####
      

      fails because you're shot by the laser once you step up.

      For point 1, I don't see why easy problems can't be nice. I thought Laser Maze was a nice problem even if easy.

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks. Now I can see that I haven't read the statement carefully.

        Easy problems can be nice. But this problem is too old. I've seen this idea (bfs with maze changing each step, and you have to add time into bfs state) many times before.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I didn't read this particular sample as well and asked a clarification whether lasers fire when you enter the maze. I asked 2 hours after the qualification round start and got reply something like 4 hours later with the answer to my question and also mentioning that it is clearly explained in the samples.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится

          It's just qualification, one should store new problems for later rounds (hopefully). For people who won't get to later rounds (don't have much experience), it might be completely new.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

    Having people failed because of lowercase/uppercase, or things like "Case #1" vs "Case 1" is just bad

    If I'm not mistaken, ICPC and most online judge such as POJ/SPOJ are like that

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Facebook hackercup has no feedback but ACM-ICPC has full. Because of that I do not get the logic of your examples, especially ACM-ICPC.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      I don't understand any of your examples. You don't wait on SPOJ until... the judge stops existing (this is probably the best analogy of "contest ends")... to find out if your problem passed. You find out almost immediately if it's correct, and are free to resubmit anytime; same with ICPC.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In all of my solution, I forgot the # signs, and i got all 3 of the tasks accepted, even i sent them e-mail about that and they answered almost instantly that validator will not make a problem about that.

  • »
    »
    10 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +23 Проголосовать: не нравится

    Hey there, I'm one of the authors/judges/admins for Hacker Cup. First off, thanks for the feedback. Without feedback, nothing gets better.

    1. I agree there's nothing too tough in the quals, especially for highly experienced people. The goal of the qualification round is mainly to get people interested, especially anybody who hasn't competed before. We don't want to scare people away right at the beginning :) Definitely let us know what you think of the problems in later rounds as well. As with anything else at Facebook, Hacker Cup is the product of continuous iteration.

    2. We allow certain discrepancies in the output formatting. Whitespace is more or less ignored. "Case #1" is OK even when it should be "Case #1:". I believe we allow the "#" to be dropped as well. That said though, attention to detail is extremely important. The sample data is available, and we offer download links as well so you can run diff or fc or similar on your output for verification.

    3. What's your FB username (or user ID, if you know that)? I can look into this for you. Our policy is to answer every clarification we receive during a round, even if it's just, as you say, a quick note saying to read the problem statement. I personally answered a few hundred clarifications this round.

    4. Looks like you found the answer, as per a separate reply.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      (2). Probably problem is that someone prints "yes" instead of "Yes" and got submission failed.
      I understand that to allow a lot of different things is not that good (maybe hard and raises question why thing 1 is allowed but not thing 2), but to have feedback like:(expected "yes" or "no", "Yes"(or whatever really found) found , please resubmit correct output file) is quite easy to make and cool to get.

      (that's why it's cool to have sort of pretests like on CF or resubmitable part of a problem on GCJ)

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        Yeah, I quite like GCJ's small/large approach. The format of future years of Hacker Cup is highly mutable, so who knows what changes might come :)

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Hi, I was in bad mood that day, so now when I read my message again, I can see that I was too harsh. I'm sorry about that & thank you very much for your kind reply.

      1. Last year, I solved mostly all problems in Qualification Round + Round 1, none in Round 2, so to me the problems were either too hard or too easy.
      2. My point of view is same as riadwaw, so let's not have duplicate discussion about that here.
      3. My FB ID is Nguyen.RR
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +19 Проголосовать: не нравится

        Hm, according to my records I responded to your clarification at Jan. 9 1:21pm PST by email, to an email address beginning with "in".

        Maybe it got sent to a spam folder?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Regarding 2: it's nice to hear that (last year I've raised up a similar question here, Russian thread). But I still think that rather than allowing dicrepancies in output format it would be better to set up some kind of automatic validation on submit phase.

      Unfortunately making checker non-strict is good for those who forgot '#', but for example it is still bad for those who submitted output for previous task by mistake. It is hard to anticipate all possible scenarios of submitting wrong output. I speak about output that is wrong in the way not related to the task like unintended submission of output of other task or swapping problem source and actual answer.

      On the other hand, if you immediately perform some check for only PE-like errors (= presentation error, I mean it is pretty strange when you output n strings instead of m numbers or wrong number of testcases) and notify if the output is incorrect in this way, this would be really much more user-friendly. Seriously, each time I submitted output during the qualification round and previous years rounds I felt nervous because of what exactly I sumbitted and I had to re-check the contents of my answer to be sure that everything is fine.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        There's a limited sort of PE-checking at the moment, inasmuch as we tell you if you've uploaded the wrong number of lines. We could probably solve almost all PE problems in one fell swoop by always including the sample input as the first few cases, and confirming that you at least match those.

        Expect this for next year's contest.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

    "Every year, I hope that Facebook Hacker cup would get better, but it is still terrible year after year." — that is pretty harsh, I disagree with that, in my opinion it is well-prepared.

    "Problems are too easy. I know this is Qualification Round, but if you look at GCJ, they always have nice problems, even for this round. Do you run out of problems?" — that is only a qualification round, so chill out. In my opinion problems on FBHC are usually VERY interesting, I especially liked problems from rounds #2 two years ago (RoboElection and Permutations, here you have: https://www.facebook.com/hackercup/problems.php?pid=413074315443326&round=499927843385312) and one year ago. (Compare that to last GCJ online round last year were both problems C and D got intended solution with enormous (7?) number of cases >_>...)

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I was scared by last year's GCJ editorial to C as well, but that's just how explaining the solution looks like. The actual intuition is not so bad, when you get a 0 query you have to decide who has the highest priority for taking it, i.e. you just need to come up with a priority order:

      Who should get in if E 0?

      1. People that leave before they get in.
      2. New people.

      Who should leave if L 0?

      1. People that enter before they leave.
      2. People that never leave.
      3. People that leave before they enter.

      And the 5 items of that priority order are the 5 cases of the editorial.

      Back on topic, I felt that two years ago difficulty in the Hacker Cup jumped too quickly. RoboElection was doable, but Permutations was very hard (this is what I see from the scoreboard as well). And from what I_love_Hoang_Yen said, it happened last year as well. I hope they calibrate the difficulty ramp better this year.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I think this strongly depends on particular person, because I don't think that permutations are that harder. What is more, I would say that permutations are more standard, roboelections demanded unusual approach. If there are 3 problems then there must be a difference between 2nd and 3rd... Btw what I_love_Hoang_Yen is comparing problems from different rounds, we are talking about 2nd and 3rd problem within one round. Year ago in round 2 I have solved first problem and haven't solved second and third, but I wasn't that far and I don't see that big difficulty gap you are talking about. In my opinion difficulties were appropriately adjusted.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I was speaking from memory: I looked at the problems again, and I actually agree now. Maybe my rating graph is not a complete lie and I'm really a better coder now than I was two years ago. Though I still think election is easier (not just personally, but the scoreboard also seems to suggest so).

          The problem remains then that I two years ago felt hopeless against the gap in difficulty: the huge gap is probably a side effect from the format, 3 problems is a bit too little.

          Fixing the checker issues against stupid bugs takes priority, though.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Can you please explain how to solve permutations? I've been trying for the last couple of days without any luck and I didn't find the editorial for that particular contest in the Hacker Cup page.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            Let us slightly reformulate the statement: a < b means that a appears earlier than b in permutation. Then build the undirected tree rooted in some node.

            Let's calculate dp[v][pos] -- how many ways to arrange numbers from subtree of v in such a way that v will be on the position pos (0-based) and all conditions from the subtree will be satisfied.

            Now we only need to be able to add new child node of v and update dp[v][pos]. Say, a child to has to appear earlier than v. Then iterate over pos and howManyNodesFromChildSubtreeGoesToTheLeftOfPos. The corresponding coefficient will be some sum of already calculated dp[to] (dp[to][0] + ... + dp[to][left - 1]) multiplied by binomial coefficients and the old value of dp[v][pos].

            Also, then you iterate over some variables try to limit its maximum by size of subtree or prefix sum of childs' sizes.

            See my code for more details (it has to be correct, because I've compared my output with the output of a passed code from competition).

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится +13 Проголосовать: не нравится

              "howManyNodesFromChildSubtreeGoesToTheLeftOfPos" — ThisIsTheStandardJavaClassSoDealWithLengthOfItsName :P

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                =)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Jokes aside, of course I prefer descriptive names of variables and want rather have too long name than too short (though with some exceptions) and that's a good habit in general :).

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Solution described by pavel.savchenkov looks like O(n3) at the first glance, but take a look here: http://mirror.codeforces.com/blog/entry/10171#comment-156342 and it should become clear why it is essentially O(n2) :). I even mentioned permutations as one of the problems where that trick can be applied.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +33 Проголосовать: не нравится

        We're planning on 4-problem rounds for the timed rounds, which should help us have a smoother difficulty curve. Let us know if you think we succeeded or not after the rounds :)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Before criticizing contests, one needs to appreciate the amount of work people put into this. Creating tasks isn't easy, you know. Maybe, FB staff had some small errors this time, but that does not imply they can't improve in the future (double negative?).