erdos's blog

By erdos, history, 4 weeks 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  

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks you both.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is discussion allowed?

»
3 weeks 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...

»
3 weeks 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

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

    This is so sad, Alexa play Despacito.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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

»
3 weeks 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?

»
3 weeks 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...

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    U should make a film based on this. LOL

»
3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    How about going to University Computer lab :P

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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..

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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 ?

»
3 weeks 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..

»
3 weeks 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?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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).

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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)

      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 5   Vote: I like it -69 Vote: I do not like it

      del

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks 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?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you try to simulate the pipes in a empty grid you will see there is a pattern. if ith column is odd then pipes get diverged from the middle row to the up and below grid and if it is even then it gets converged from the both up and down to the middle row. you can refer to my code here

»
3 weeks 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..

  • »
    »
    3 weeks 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();
    }
    
    • »
      »
      »
      3 weeks 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)

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks 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 ?

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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 :-(

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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 :)

    • »
      »
      »
      3 weeks 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)

»
3 weeks 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:".

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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,

»
3 weeks 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)

»
3 weeks 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)?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Model the problem as Negative Cycle Detection problem.

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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

»
3 weeks 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

~~~~~

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks. Careless mistake again :(

»
3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you arrange all possible pipes in a empty grid you will see a pattern , for ith column if it is even then pipes converge from up and down to the middle and go to the right and if it is odd then pipes diverge from the middle row to up or down and go right wards . You will notice that if number of columns are even then there is no path that can be made so for that answer is 0. so if our dp state is like dp[row][col] which represent number of possible paths from (0,0) to (row,col) then the transition will be like... if col is odd then dp[1][col] = dp[1][col-1] and after that dp[0][col] = dp[2][col] = dp[1][col]. and if it is odd then dp[0][col] = dp[0][col-1] , dp[2][col] = dp[2][col-1] then dp[1][col] = (dp[0][col] + dp[2][col])%MOD. At last our answer will be at dp[n][m].

»
3 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

?detaR tI sI

»
3 weeks 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 ?

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone else faced the same problem as me? I got the algorithms correct for let it flow and ethan traverses a tree, but I made some errors in implementation of let it flow, which led to WA! :-(