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.
Does anyone have a clue why problem 4 was much easier than 2 or 3 but gave twice the score..?
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.
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
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.
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.
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.
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.
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).
They may have written it during the contest :)
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.
We can solve B in (m^4)*t dp solution. For me , it ran within seconds
Lol, I have O(n^4 k^3) and passed with no parallelization.
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.
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 :)
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.
I think I implemented that solution and it seemed to work for me.
Duh, then I probably did some bug. It worked on samples in no time though.
Challenge: solve C faster than O(n2).
We can use FFT?
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...
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.
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.
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
Should've casted all the inputs in C to long long right away...
And people still call me names for using #define inf long long :p
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.
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.
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)
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.
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.
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.
Yes, I saw that, too.
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 :)
I believe we’re set on Friday, November 2
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?
I've also missed it at first, but the linked post says Menlo Park.
ICPC Regional contest in South Korea will be held in November 2-3. I think me and molamola. will participate in 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
Or time to abandon
#define int long longand start thinking about types.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.
Real men use
#define 1 1LL.I already tried :>>>. But it doesn't compile :((
My feeling after the contest
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!
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
Should be OK (no fee), as I've just got two t-shirts in Zurich :)
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.