LoneFox's blog

Facebook Hacker Cup 2018: Round 3
By LoneFox, history, 6 years ago, In English

Round 3 of the 2018 Facebook Hacker Cup is less than 24 hours away!

The round will begin on August 18th, 2018 at 10am PDT and will last for 3 hours. You can check the start time in your local timezone here.

The contest will be available here shortly before the round begins.

You're eligible to compete in Round 3 if you were among the top 200 contestants in Round 2.

The top 25 contestants will advance to the Final Round, which will take place in early November, onsite at Facebook's headquarters in Menlo Park, California! Please note that all submission judgements will only be revealed after the round ends, and that time penalty will be used to break score ties. More details about rules and other information can be found here.

Good luck!

The corresponding Facebook post can be found here.

Update: The editorial is now available here.

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

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

Does anyone have a clue why problem 4 was much easier than 2 or 3 but gave twice the score..?

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

    I guess the organizers have some strange hard solution. For me the order of difficulty was DBCA today btw.

    also: yay, I have all the finals this year :) TCO marathon+algo, GCJ+DCJ, FHC, Yandex, also acm WF. Now it would be good to win something.

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

      They probably overlooked the simple solution, but it's hard to believe — B,C were much harder.

      Also it seems like it's a common practice for them to have a disgusting problem involving case work and only case work as a first problem. That's quite annoying. (I'm bitter though, if my A had passed I'd have qualified).

      P.S. Congrats for nailing all the finals

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

The only one I enjoyed working on was D. The others were case-bashing hell and I didn't enjoy tackling them at all, and for that reason alone I found D the easiest.

Congrats to those who managed to get through all four without screwing anything up.

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

In order to present some different opinion than above ones, I really enjoyed B (my solution is definitely not casework), solved C as well, and I have no clue how to do D. However I have O(n3k2) to B which I needed to parallelize 3 times in order to make it pass within TL, maybe faster solutions are more tedious.

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

    Possibly wrong or just overlooked solution to D. Feel free to break it:

    Convert each fish to an interval of pools it can reach. Let fish i be Li to Ri. Do dynamic programming

    F[left end][right end] = solution considering only fish whose interval fits in [left end, right end] entirely.

    F[left end][right end] = F[left end][k-1] + handshakes(all considered fish that can go to k) + F[k+1][right end]

    Something like O(N3) or O(N4) but super-lightweight either way.

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

      Suppose that after all fishes finish moving, the pool k contains the largest number of fishes. Then, all fishes who can go to this pool should go to this pool (because of the convexity of \binom{n}{2}). This is the meaning of your recurrence formula and it looks correct.

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

        Yea, that's how I figured it out — I just couldn't believe it was correct since I had battled C for over an hour and did this in less than 10 minutes. The editorial seems to mention this solution or something very similar, so I have no explanation for their decision for the score distribution (even thought it was in my favor, my C failed and D passed).

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

          They may have written it during the contest :)

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

          As for C, in my opinion it is really "one way" problem. It is more or less obvious what kind of ideas should be used in this problem and we just need to pave our way through it. You just need to carefully consider whether this or this or this arrangement will work. You can't detour from the road too far. It takes some time to carefully do this (for me, it took ~1 hour), but that's it.

          However for D, there can be lots of approaches to that problem, place of start is not clear and main idea may not cross mind of even many experienced participants. I understand that this solution can be came up with quickly, but for me even in hindsight, D is the most difficult problem.

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

    We can solve B in (m^4)*t dp solution. For me , it ran within seconds

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

    Lol, I have O(n^4 k^3) and passed with no parallelization.

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

    An example of simple solution: Let's fix the interval that achieves the maximum. All undecided numbers within this interval should be either K or  - 1. Let's also fix the number of Ks in it. Now we know the maximum sum. Let's fix one more parameter X. We want to check if we can achieve m ≤ X, while satisfying the constraint (the number of Ks). This can be done by a simple DP. Do binary search on X.

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

Thanks for cool tests in D, I got OK with dp on multiset of active right borders of segments (after compressing coordinates) with no problem. However, I didn't come up with counter test during the contest, so it's an interesting challenge :)

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

    Damn, I had dp on sets of fish and I consider as meeting places only places where some fish ends. I am not able to come up with a test where this runs for longer than O * (2m / 2), but their tests pwned me.

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

      I think I implemented that solution and it seemed to work for me.

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

        Duh, then I probably did some bug. It worked on samples in no time though.

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

Challenge: solve C faster than O(n2).

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

    We can use FFT?

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

      Yup. We can use FFT to compute all the possible Parts 2 and Parts 3 of the pattern (as defined in the reference solution). The optimal solution can be then composed of all the parts in linear time, but it's probably not a very exciting part of the solution.

      I actually screwed up the strategy and implemented such a solution: https://ideone.com/oi6TEl...

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

        I realised fft solution in last 15 mins and did not code try to code n*n thinking it would fail because there was nlogn solution. A very bad judgement.

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

        Dont you think precision would be a problem here if we try to use plain fft.

        But anyways NTT with two mods and chinese remainder theorem might work.

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

          You can use exact fft. That one where you want to do fft modulo anything where you Express coefficients as aM+b, where M is something like sqrt(range) and abs(a), b<=M

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

Should've casted all the inputs in C to long long right away...

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

    And people still call me names for using #define inf long long :p

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

Another opinion: I enjoyed every problem (maybe A is not so great, but it is fine, and reminded me about cool puzzle game 'The Talos Principle' :) ). In B I have cool greedy solution which was easy to code but hard to come up with. D was brutally hard for me, and my solution is something I have never seen before.

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

    I would guess the authors have some D solution like yours.

    What is your B greedy? I got a greedy solution on B as well — relying on the (unproven but intuitive) fact that all numbers we add will be either -1 or K.

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

      The fact is easy: If we place something negative then for Ethan it doesn't matter exactly what we will place, and for us it is always better to place -1. We will place something non-negative only in segment which will be our maximal, and in this segment increasing any number by X always increases our answer by X and increases Ethan's answer by something not greater than X, so it is good for us.

      Let's fix our maximal segment (its borders) and W — maximal answer for Ethan. Outside of our segment we will only place -1. Inside: it is easy to see that we can greedily place Ks until condition that Ethan's answer is bounded by W is broken. It is O(KN4), but we can only fix left border of our segment and calculate answers for all right borders at once, it will be O(KN3)

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

        My solution actually fixes only W — the maximal answer for Ethan. Fix all values added to be K, then once again greedily just execute Ethan's algorithm and whenever he gets to more than W, change the last (or second-to-last, whichever is yours) of the processed values to -1. So O(NK) for fixing W and O(N) for simulation. Total O(KN2). Unproven once again but I had a strong greedy hunch in that problem.

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

    Seems that's what organizers thought.

    However if you consider pond with absolute maximum fish at the end, by convexity all fish who can swim here should. Then the interval is broken into two segments, giving simple O(M^4) or O(M^3) DP.

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

      Surprisingly the editorial seems to mention this solution. Doesn't make sense why this problem gives twice as more as B or C if they thought of that solution.

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

Thanks for the round!

Any chance you have concrete dates for the finals? Since it's so close to the TCO it makes sense to combine those into one trip, so it would be great to start planning that one :)

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

    I believe we’re set on Friday, November 2

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

      What about this post: link? It says "October 25 — 27, 2018". If it's incorrect, might be good to remove that info (could confuse someone).

      Also, is the location known? Or at least a country? USA?

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

      ICPC Regional contest in South Korea will be held in November 2-3. I think me and molamola. will participate in it..

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

Daaaaaamn, I forgot to add ll to ctz and popcount in D :|... That's why my very naive exponential dp on subsets of sets did not work in time. When I corrected that mistake it got correct answer for all test together in 0.02s xdddd. I would get 86 points with that. But that would be fourth contest in a short timespan when I would get high position because of pushing some shit that somehow passes. But I would gladly exchange that one for last three times on codeforces. Time to add "#define __builtin_ctz __builtin_ctzll" etc. to my macros xd

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

    Or time to abandon #define int long long and start thinking about types.

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

      Or time for you to stop talking nonsense. I remembered about ll, because I wrote 1ll in bitwise shift, I was well aware I am dealing with 64bit ints. But I just forgot that this function requires adding ll to its name.

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

        Real men use #define 1 1LL.

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

          I already tried :>>>. But it doesn't compile :((

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

My feeling after the contest

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

I solved Finshakes in , thinking that n = 50. I was mortified when the submission didn't finish in a few seconds, only to find out that n = 500. Luckily, it was still fast enough :)

Also, I didn't use anything from my codebook, which is a rare occasion these days!

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

I just received two tracking numbers from Her Majesty Royal Mail. Could they be the T-shirts? Is this real life? Or is this just fantasy?

One of them is marked as delivered (it is the first record in there, it was apparently never dispatched :-)). The second one is at Swiss customs. Expecting a hefty clearance fee for it :-D

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

    Should be OK (no fee), as I've just got two t-shirts in Zurich :)

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

      I know that it should be ok, but once I got a bill for customs inspection of a fee-exempt shipment, along with a fee for printing and sending the bill. The bill arrived three weeks after I received the item. So you never know.

      → Reply