Morphy's blog

Facebook Hacker Cup 2018: Round 1
By Morphy, history, 6 years ago, In English

HackerCup R1 starts in ~24h (July 21 12:00 PET).

Let's discuss the problems after the contest!

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

Comments Comments (72)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where I can see statements of the tasks of Qualification Round?

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

thanks you both.

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

Link to the first problem: https://www.facebook.com/hackercup/problem/180494849326631/

Links to the rest can be found on the left sidebar.

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

Is discussion allowed?

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

Nice challenges! Especially the hard two. Was a bit difficult to read problems but fun to solve. Zombies kept me awake until 2 AM...

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

The problem difficulty feels like going from riding a bike to flying a spaceship

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

Fun problems :) took me a while. Interested in how other solved the yards and zombies problem.

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

    I solved it with O(n3) solution (similar to matrix chain) but solving test cases in parallel. Otherwise couldn't get AC.

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

      At one point after having the N^3 solution, I started counting how many computers I have in my house so I can give each one a small number of tests and then generate the output file.

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

The contest page is unavailable on mobile devices, please try again on a desktop device.

Wow, I can't even read problems and see the standings from my phone. Great work, Facebook.

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

    Yeah, that’s dumb. Anyway, you can try the “request desktop site” option in your mobile browser. Worked on my Safari.

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

Is p3 a binary search combined with finding the max/min heights of each pillar? I tried that but it missed the sample case 3. Not sure if the algorithm is wrong or just my debugging skill sucks.

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

    nvm, i saw there are solutions uploaded

    so close lol, probably shouldn't have started this problem in the last 25 minutes

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

My submission was showing wrong output format for the 2nd ques can you test it on the basis of solution pls or tell me why was that happening?

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

Oh
My
God
...

This round was from 10AM on Saturday to 10AM on Sunday for me, however on Saturday I went for a long trip with friends which started at 7AM on Saturday and ended on 1:30AM on Sunday. Before that trip I planned to do these problems after coming back to home and before going to bed, but we came back home much later than I expected and I was so tired I completely forgot about it and immediately went to bed after coming back. I kinda randomly woke up at 9:30 AM and had thoughts like "Oh... I recall that there was FBHC R1 going on... When does it end...? OMAGAD IN 30 MINTUES!!!". I immediately got up, started reading problems at something like 9:33 and managed to send first problem at 9:44 and second one at 9:57. Moreover to the end of contest I was convinced that my output on sample to second problem is wrong cause I messed up manually going through fourth testcase, but decided to submit my out anyway. Imagine the thrill and tension... Fortunately I made it through...

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

    U should make a film based on this. LOL

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

For next round I will buy 75 computers and run all test cases in parallel, passing N <= 3000 with N^3.

Now, to be serious, I am a bit disappointed half the test cases had N <= 1500 and only about 10 tests had N ~= 3000.

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

    How about going to University Computer lab :P

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

    My solution was N^3 worst case when zombies have strengths n/2 n/2-1 .. 1 1 2 ... n/2

    Not even a single test came close to worst, everything finished in seconds

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

    My O(N^3) with memoization ran in 3 minutes and I submitted. (it was WA anyway because of simple mistake). It felt really weird, the slowest test cases were with N=1700 and even some N=670 took quite some time but there were only a couple hard ones overall. I guess even a single N=3000 maxtest with the same structure could make me TL..

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

    Note that, if all cases were maximum, the input would take ~6MB. So I kind of hoped it would be lighter, as my parallelized O(N3) was close to 6 minutes locally.

    I tried to improve it to O(N2), but got bored debugging the resulting mess, and decided to just parallelize the O(N3) instead.

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

    I am confused, if you are disappointed that most of the test cases are small, why you implemented solution and hoped it to pass instead of implementing ?

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

OMG, such a silly mistake i made ,for problem b i called refresh() function after returning from impossible condition,..badluck..

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

I think a nice problem to think about is the first one without the restriction that number of rows is equal to 3. Any ideas about that one?

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

    If the number of rows is not big, then the problem can be solved with profile dynamic programming. In mask we should remember connected components, which are connected to a considered column. Now some connected components can be merged. We also can start some new connected components.

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

    I think it can be solved in O(N * M * pipes * 16), where dp[i][j][k][l] denotes the number of ways when we reach (i, j) entering from k direction and leaving from l direction, where we have 4 possible directions, "North south east west", try this will all possible pipes. To avoid running into cycles, I wrote a recursive "dp" solution maintaining a "visited" array as well. I did the same solution which passed system tests.

    Code link

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

      I don't think that you can do it in polynomial time. For me this problem for bigger number of rows looks like a very standard problem for doing dp with profiles, exactly as Vladyslav explained (which is exponential or even more).

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

        Swistakk can you briefly explain why my solution is wrong, like what state can I miss? I am not able to get it.

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

          Unfortunately I didn't quite get what you meant. Recursive dp with maintaining visited array sounds to me like jest backtracking and even memoization here wont help to make this good enough. And just to make sure you realize — this loop can go back and forth and create some really complicated shape which is hard to capture by some simple left-to-right dp (but can be captured by this more complicated, exponential with respect to m, dp, which was described before by Vlad)

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

        After seeing your comment I copy pasted "dp with profiles" on google to learn about it, and got this.

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

      del

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

        Not really, the problem arises when N is, say, at least 6, then, you can go back to a column you cleared in the past and still make it to the finish. This can't happen when N = 3, that's why your solution works for the FBHC problem.

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

Can anyone explain how can I solve first problem (Let it flow) through dp?

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

how do we apply binary search when dealing with floating point nos,related to problem c..

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

    For this problem specifically you can notice the answer is always half an integer.

    In general for binary search for floating point, a nice trick is to run the binary search a fixed number of iterations, so something like:

    for (int i = 0; i < 100; i++) {
binary_search();
}

    instead of 

    while (hi > lo) {
binary_search();
}
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      Also worth mentioning: To determine the minimum number of iterations required (if you are worried about TLE because of the solution being borderline TLE):

      -It's easy to notice that the difference between lo and hi reduces to half the original difference after every iteration

      -Therefore, (original difference)/(2^[number of iterations]) <= eps. From this, you can get the required number of iterations. (I take eps/2 or less to be on the safer side)

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

      okk thanx,but what if ans should have precision upto 5-6 decimal places

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

        Add several more iterations to the number required for integer binary search.

        Each iteration halves your interval, so you need such x that 2x > 106. 20 is enough.

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

I wonder, Is there any way we can know about statistics of the Round, just like in Codeforces we can know how many users have solved Problem A/B/C/D ?

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

For Zombies I had a different idea (or different wording at least).

After the fences are set, we can see that each zombie has access to some segment [i..j] of houses. For any two zombies, such segments either do not intersect or one includes the other, because the stronger zombie is definitely able to reach the houses which the weaker zombie can.

Consider the case when all houses are unsafe. Using the observations we can unambiguously partition the whole street into segments, such that inside any segment there is at least one zombie that has access to all houses inside the segment, and no zombie can go from one segment to another.

We can compute the probability that all houses are unsafe by summing probabilities of all possible partitions. First, we iterate over the length of the first segment. Then we solve recursively the problem on the tail (i.e. everything except the first segment). However, the combination of two probabilities depends on the powers of the zombies from the first segment and the second segments (we need to consider only the maximum powered zombie inside each segment). The simplest solution is to pass the power of the zombie from the first segment to the subproblem and there use it in the probabilities computations. Moreover, we have to memoize the solution of each subproblem. There are N subproblems with M possible zombie heights as additional inputs. This leads to O(N^3) solution (maybe with extra logN if we use map<>).

I just tested it with unordered_map for memoization and it runs in 2 minutes on all 106 tests on my laptop.

I think it is possible to improve to O(N^2) by getting rid of the additional parameter. Subproblems then should return two arrays and it probably becomes quite close to the intended solution.

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

    My solution uses the same initial observation. To summarize, what I computed was

    mx[l][r] = max height of zombie in l..r

    dp[l][r] = probability that a zombie can go to all houses in l..r

    dp2[l][r] = probability that a zombie can go to all houses in l..r and no zombies here go to house r+1.

    ans[l][r] = probability that 1..r is covered by zombies, and the last segment (defined in the above comment) covered has left endpoint at least l.

    ans2[l][r] = probability that 1..r is covered by zombies, and the last segment (defined in the above comment) covered has left endpoint at least l, with the added condition that the zombies cannot go to right.

    These can be computed in O(n2) time.

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

A bit frustrating: come up with an O(n3) solution for the zombie one pretty quickly, spend two hours trying (and failing) to figure out how to get to O(n2), only to find out everyone else just went with O(n3) anyway :-(

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

    WooooW WooooooW WooooooW

    what do you mean the O(N3) passes my solution was had some factors to it but it was still O(N2) can you please explain what is the O(N3) solution that would pass.

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

    I created an O(n3) solution but after downloading the input file it turned out that it was too slow in some test cases and I failed the problem. So at least one O(n3) solution was not accepted :)

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

      Same here:)) Only solved ~25 tests in the 5 minutes that I've had for running:( But my solution was soooooo overcomplicated that I didn't assume anyone else would try it so I'm not shocked to see that I'm among the only ones that had serious trouble fitting in. On average tests it was really fast so I just hoped for weak tests (apparently when it comes to my approach they were quite strong)

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

I fail on 4th problem because I print "Case %d:" instead of "Case #%d:".

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

    That's why I have a special template for Hacker Cup (and Code Jam) which has a printCase() function just for printing this.

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

    Is it your first time competing in fbhc? If not then why aren't you reusing some old template to omit that boring boilerplate dealing with testcases?

    Btw I am surprised that their checker didn't tell you that your output is in wrong format. I purposefully tried to swap output and source code when submitting some problem from qual round and it was rejected due to wrong output format.

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

      It's my 8th time of competing in FBHC. I don't use template maybe I just too lazy and stupid. QwQ

      I didn't notice whether the checker tell me the format is correct or not. But I see I get score on scoreboard so I think all things are good,

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

The low constraints for M on Platform Parkour [Question C] allowed me to use N*M*log(Z) time instead of N*log(Z) time (foolishly did not pre-compute the up/down for the array elements and checked for every parkourist)

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

I've a simpler solution to Platform Parkour (linear — not using binary search), but don't know how to prove the correctness. Maybe it's wrong...

The idea is as follows. I came up with a pretty strong lower-bound for the answer and then hoped it's also sufficient condition. Basically, for every two indices i < j the following must hold:

otherwise, we obviously can't make the i-th and j-th platform similar enough so that the parkourists could climb them. Similar holds for going downhill. This can (quite easily) be implemented in O(N). Any idea why this should work (or not)?

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

    Model the problem as Negative Cycle Detection problem.

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

    Here's my proof sketch: after you solve that worse interval, you solve recursively for the what remains in the left part, and for what remains in the right part since they are independent — the solutions there will also be based on a worst interval, which will give a smaller time than [i,j]. We are left with the boundaries between these 3 pieces. Since the interval (i,j) was the worst, by solving it you improve the situation from i-1 to i and from j to j+1, since otherwise the interval (i-1,j) or (i,j+1) would be worse, contradicting the maximality assumption.

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

    There is a simple O(n) solution without binary search. In the official solution, there is a binary search for x, and for each value of x there is a pass over all platforms which maintains a range [h1, h2] of valid heights. It is easy to see, however, than [h1, h2] can always be represented as , where and don't depend on x. So, instead of making multiple passes with different values of x, it is enough to make one pass with x = 0.

    Since all the intervals must be nonempty, x must not be smaller than for every encountered pair . So, the algorithm makes a single pass with x = 0 and computes the maximum of , which is the answer.

    Here is the code.

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

Optimizing the modulos in my O(N^3) solution to the 4th problems makes the solution run from ~50 minutes to 2 minutes.

TL;DR I always need to be reminded that modulos are very very very slow

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

could not find the bug for "Ethan Traverses a Tree" :( anyone?


~~~~~
removed

~~~~~

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

    Please wrap your code in <spoiler>..</spoiler> tags so that it doesn't use so much page space (you can edit your comment).

    If the number of components is greater than K, you should still use only K colors.

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

      thanks. Careless mistake again :(

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

Can somebody help me in figuring out the problem in my code for problem "Let it Flow"?

https://ideone.com/mADXsz

I used an extra state for horizontal or vertically entering the cell. If it is horizontal entrance there two possible paths, i.e. up and down, but in case of vertical entrance, only one path is possible which is in right direction.

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

?detaR tI sI

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

How would we solve "Let It Flow" if there were more than 3 rows ?

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

    In case you are wondering about the downvotes, its not because your question is not proper but because it has been asked some comments before.

    → Reply