eatmore's blog

Facebook Hacker Cup 2015 round 3
By eatmore, 10 years ago, translation, In English

The third round of Facebook Hacker Cup 2015 will take place exactly one week after round 2: on January 31st at 9:00 PM UTC. The round will last 3 hours. Top 25 participants will win a trip to Menlo Park to participate in the final round, which will take place at Facebook office on March 6th.

Participants will be able to enter the contest using this link, and the scoreboard will be available to everyone here.

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

Comments Comments (57)
| Write comment?
»
10 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Round 3 problem statements are available on the Hacker Cup page: https://www.facebook.com/hackercup/posts/907649815933874

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Here are my inputs and answers.

UPD: they're wrong for 35 and 40 problems.

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

    "hz" in Lunch Scheduling answers?

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

      Whoops, I've uploaded wrong file. Fixed.

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

    I have different answers for Gentrification, anyone else?

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

    Me and sankear all differ in problem C. Our outputs: http://pastie.org/9877127

    Moreover, me and sankear differ only in test four, my answer is larger by 1, and your answers are larger then ours on significant number of tests.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      My answers coincide with sankear's.

      Edit: also implemented tourist's approach now, answers are the same.

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

      +1 to your answers... probably, I have the same bug :)

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

        Does it mean it coincides with my answers? Or even more +1?

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

          coincides

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

            Probably that's because you forget to replace graph with its transitive closure. Me too =(

            → Reply
»
10 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Problem 35 was clearly Dilworth's theorem. Isn't it too classical to be in qualification round?

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

    Well, you also have to find how to account for weights. Doesn't seem trivial to me.

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

      Well, it is not trivial, but so standard move...

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

      Or maybe my solution is wrong and the problem is ok)

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

      There is no need to find strongly connected components at all (and thus to account for weights). You can just use partial order (u < v) <=> (there is a path from u to v, but no path from v to u).

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

        I didn't even read the problem but I know you said something that makes people go "Wow, that is amazing, how did you think of it?" :D

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

      I agree.

      I'm familiar with Dilworth's theorem. (E.g. I have created a task about this: SRM557 Div1-Medium) But it still took me about 30 minutes to figure out how to deal with the weights.

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it -9 Vote: I do not like it

    Is it really classical and wide-known theorem? If yes, then I'm totally fine with this task. Otherwise, while not denying that it's good for me that I learned a new theorem today, I personally find it rather bizarre to give 35 points on the basis of how well can one use Google. Which, apparently, I suck at.

    UPD: I see, so it's a well-known and pretty widely-used theorem. Have absolutely no problems with the task in this case. Thanks for the feedback!

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

      Believe be, I even didn't hear the name of the theorem until now, beside of the content.

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

      There is a similar problem at Timus Online Judge: Fat Hobbits

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

      This theorem was given in at least a topcoder and one GCJ problem, see for instance here.

      I don't think it was an obvious solution, I clearly knew the theorem and couldn't solve the problem, so maybe it was okay after all...

      → Reply
»
10 years ago, # |
  Vote: I like it -46 Vote: I do not like it

Zonk. I find it pretty bizzarre that strong redcoders don't know Dilworth's theorem xd. Here you have beatiful problem where it can be applied (or rather, need to be :P) http://main.edu.pl/en/archive/oi/9/nar

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

    Since this comment is on top-level, I'm not 100% sure if this was meant to be a reply to my original question. It really looks like it is, so I'll go ahead and answer it, even though I don't consider myself a strong redcoder.

    So, you are finding pretty bizarre that there is a possibility that strong redcoder doesn't know that theorem. In fact, the theorem itself doesn't even matter. Let's consider the possible ways of how can one learn it:

    1. Was taught it in some kind of school/camp/etc.
    2. Read about it or tried solving a problem which required the knowledge of it.

    I believe that's pretty much is it in general terms. So let's consider what is required for these ways to occur.

    For the first way, not everyone have that privilege, which requires an infrastructure and coaches at schools and universities, willing to devote their valuable time on coaching. Please, do no take that for granted. Even if everything is in place, it's not guaranteed that you will learn it from this way.

    As for the second way, there are two scenarios around it. One is to invest a lot of time in training, which is usually expressed in solving problems from various online and onsite competitions on your own. I do not think it's bizarre that some people simply do not have enough free time to be willing to do this. For me personally, competitive programming is pretty much a hobby rather than the thing I seriously devote myself to ever since I changed university in late 2012. And I'm not alone at my University. It is ridiculously hard to organize anything regular here (I have tried, trust me, and still am), since no one has lots of free time available and pretty much everyone has his own schedule. And I'm not even talking about people having a full-time job — even less time is available there.

    Second scenario is to participate in competitions and encounter a problem on the topic there. Which, again, with the same reasoning of limited time available, I don't find that bizarre that for some, like me, this particular contest might have been the first time they've encountered a problem on this topic, since, again, not enough time to participate in every contest available.

    So, with this, the way I understand your statement is that you find bizarre that strong redcoders might not have the privilege to be coached or enough free time willing to invest in heavy training. Well, I don't. One likely needs to invest a lot of his time to become a strong redcoder, I'm not arguing with that. However one also likely needs to continuously invest even more time to continue learning new to them algorithms, data structures, approaches, types of tasks etc. And a vast majority of people after some point in life can't afford that anymore.

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

      Huh, that's a pretty exhaustive answer to my a bit stupid statement xD. I already saw problem like "You're given a grid with positive integers inside it, how many paths from lower-left to upper-right corner (going up and right) do you need in order to obtain an arrangement such that at least a[i][j] paths passes through cell (i, j)?" on ejudge and vast majority of teams got this problem accepted in a short period of time and that is a classical application of that theorem, so I assumed that among univeristy students it is widely known.

      Though I understand that not everybody is obliged to know all theorems on the world and that's of course understandable.

      → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

My solution for problem 35: Gentrification:

ls = {0,1,2,...,components-1}
sol=1
do
	shuffle(ls)
	curSol=0
	// from left to right, if possible, mark the component and add it's size to curSol.
	sol=max(sol,curSol)
	// same from right to left
repeat for 8 seconds
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I did DP for <= 25 components. And random_shuffle for > 25.

    There were 5 tests > 25 (28, 161, 191, 500, 500) Half of the tests were with 1 component. (these are the components after you build the graph with edge u->v if there is a path from u to v.

    I suppose their tests are weak.

    A case that can beat the random: a -> b <- c (b = 3, a = 1, c = 1) you need to choose b.

    Have lots of these. Less likely you choose b over all of these.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem 40, are there precision issues with the naive solution (Gauss over each four vertices)?

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

    I haven't found any. I've tried double, long double and eps from 1e-8 to 1e-15 and all solutions gave same answers.

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

      When I tested your solution against mine, I noticed that you output 1.0 probability in some cases when b is much less than a. While correct answers seems to be 0. So I guess the issue you had is not precision but an edge case.

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

        Exactly: I haven't added this check: if (floor(a/4) > floor(b/4)) return 0;

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

    I think so. Or at least their checker is wrong. I tested Gleb's accepted solution against mine on my testcase, and there were 41 differences, where each was 1e-6 differences of the two numbers in the output. So if his solution was correct I assumed mine would be also. But it failed.

    I also checked yours on my test case, and it gave exactly the same result as Gleb's. But yours failed as well. So I think there is something fishy with the way they tested this problem.

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

      Oh my, I know what happened here. I didn't wait until your timer was up before judging, and I ended up judging your second submission (which was WA), but then you submitted a third time afterwards and I missed it. Your last submission is definitely AC.

      I'm double-checking all submissions now to make sure nobody else was affected.

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

        Awesome! Thanks Wesley for figuring this out!

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

      Everything else looks OK. I'll update the scoreboard.

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

        So is Jakub (dj3500) going to miss the onsite now? I recall yesterday he was in 25th place, and now he is in 26th place. Is that not unfair to him, to make him think he was going and then find out that this is not the case?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          These are the sorts of reasons (along with things like detecting cheaters) why we don't send official advancement emails until a few days after the end of each round. You could say we could withhold the whole scoreboard until then, but that would probably be a bit overkill.

          I've talked to Jakub, and there's always the possibility that somebody is unable to make the onsites, in which case there'll be a spot for him.

          I wouldn't say the situation is "unfair" in the sense that Jakub is not really in the top 25. However the emotional whiplash is certainly unpleasant, and that's my fault. I'm going to be working on better judging infrastructure for next year to reduce the potential for human error in a bunch of places.

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

            possibility that somebody is unable to make the onsites

            like this?

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

              Yes, indeed. This isn't reflected on the official scoreboard because the submission wasn't uploaded through the contest system.

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

            Well, I would say the unfairness is in saying that "in 30 minutes the scoreboard will be finalized", then posting the scoreboard and claiming that top25 now advance. All of this, while not being an official email, does look like an official announcement (which then gets retracted/amended). Unfortunately I happen to have shared my joy in a Facebook post (I waited 12 hours for good measure — should have waited for the email), which now is making me look kind of stupid (unless someone drops out, I suppose).

            Speaking of which: any statistics on drop-outs in the last years? ;)

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

              JoeyWheeler: "But unfortunately I am still 17 (I hadn't realised they were unaware of this) and so cannot attend this year D:"

              Source: http://codeforces.me/blog/entry/16146

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

                Yes, but he's out of the top25 in the current scoreboard.

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

              I agree that "finalized" sounds pretty final. We could probably pick a better word.

              Sharing the later-determined-to-be-incorrect results is hardly your fault.

              I think we actually had 3 people who didn't show up last year. I don't know if this was because of visa issues or other obligations. We've invited the top 25, and they have until Feb. 5 to confirm that they're coming.

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

                Could you share any information about how many top 25 participants have confirmed/refused their participation?

                I don't expect something like official answer, just want estimate the probability of me on 29-th place being invited.

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

                  I don't know of any other contestants that have decided not to come, but I'm not in charge of the travel/visa arrangements.

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

                  I believe we have 25 confirmed finalists now, so the finals are set :)

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

                  Thanks for the info, hope one year I will be able to be among these 25 people :)

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

                  See you next year!

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

              I'm not going, so enjoy your trip Jakub! And make it count :)

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

                Awesome (I mean, I'm sorry to hear that you're not going, but... ;) ), and thanks!

                → Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Now available in gym: 2015 Facebook Hacker Cup, Round 3. Used my test data and GlebsHP's solutions to generate answers.

→ Reply