### erdos's blog

By erdos, history, 4 weeks ago, ,

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

Let's discuss the problems after the contest!

•
• +114
•

 » 4 weeks ago, # |   0 where I can see statements of the tasks of Qualification Round?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Tourist: https://www.facebook.com/hackercup/problem/1632703893518337/ Interception: https://www.facebook.com/hackercup/problem/175329729852444/ Ethan Searches for a String: https://www.facebook.com/hackercup/problem/1153996538071503/
•  » » 4 weeks ago, # ^ |   -8
 » 4 weeks ago, # |   0 thanks you both.
 » 3 weeks ago, # |   +14 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, # |   0 Is discussion allowed?
•  » » 3 weeks ago, # ^ |   +18 Not while the contest is running.
 » 3 weeks ago, # |   +43 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, # |   +50 The problem difficulty feels like going from riding a bike to flying a spaceship
•  » » 3 weeks ago, # ^ |   +10 This is so sad, Alexa play Despacito.
 » 3 weeks ago, # |   +3 Fun problems :) took me a while. Interested in how other solved the yards and zombies problem.
•  » » 3 weeks ago, # ^ |   +25 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, # ^ |   +48 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, # |   +100 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, # ^ |   +20 Yeah, that’s dumb. Anyway, you can try the “request desktop site” option in your mobile browser. Worked on my Safari.
 » 3 weeks ago, # |   0 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 →   +3 nvm, i saw there are solutions uploadedso close lol, probably shouldn't have started this problem in the last 25 minutes
 » 3 weeks ago, # |   +3 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, # |   +139 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, # ^ |   +33 U should make a film based on this. LOL
 » 3 weeks ago, # |   +10 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, # ^ |   +1 How about going to University Computer lab :P
•  » » 3 weeks ago, # ^ |   0 My solution was N^3 worst case when zombies have strengths n/2 n/2-1 .. 1 1 2 ... n/2Not even a single test came close to worst, everything finished in seconds
•  » » 3 weeks ago, # ^ |   0 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, # ^ |   +5 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, # ^ |   +8 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, # ^ |   0 I didn't implement O(N^3) even though I had the idea for it, that's the point.
•  » » » » 3 weeks ago, # ^ |   +5 Ah, got it.
 » 3 weeks ago, # |   0 OMG, such a silly mistake i made ,for problem b i called refresh() function after returning from impossible condition,..badluck..
 » 3 weeks ago, # |   +14 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, # ^ |   +24 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, # ^ |   -54 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, # ^ |   +13 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, # ^ |   0 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, # ^ |   +3 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, # ^ |   +5 After seeing your comment I copy pasted "dp with profiles" on google to learn about it, and got this.
•  » » » 3 weeks ago, # ^ | ← Rev. 5 →   -69 del
•  » » » » 3 weeks ago, # ^ |   +19 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, # |   +1 Can anyone explain how can I solve first problem (Let it flow) through dp?
•  » » 3 weeks ago, # ^ |   0 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 →   +5 how do we apply binary search when dealing with floating point nos,related to problem c..
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +21 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, # ^ |   +20 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, # ^ |   0 okk thanx,but what if ans should have precision upto 5-6 decimal places
•  » » » » 3 weeks ago, # ^ |   0 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, # ^ |   0 makes sense , thanx
 » 3 weeks ago, # |   +8 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, # |   +18 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, # ^ |   0 My solution uses the same initial observation. To summarize, what I computed was mx[l][r] = max height of zombie in l..rdp[l][r] = probability that a zombie can go to all houses in l..rdp2[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 →   0 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, # ^ |   0 WooooW WooooooW WooooooWwhat 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, # ^ |   +13 Just read the replies upthread^
•  » » 3 weeks ago, # ^ |   +8 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, # ^ |   0 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, # |   +46 I fail on 4th problem because I print "Case %d:" instead of "Case #%d:".
•  » » 3 weeks ago, # ^ |   +28 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, # ^ |   +21 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, # ^ |   +3 It's my 8th time of competing in FBHC. I don't use template maybe I just too lazy and stupid. QwQI 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, # |   +15 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, # |   +1 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, # ^ |   +3 Model the problem as Negative Cycle Detection problem.
•  » » 3 weeks ago, # ^ |   0 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, # ^ |   +6 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 →   +3 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 →   +8 could not find the bug for "Ethan Traverses a Tree" :( anyone? ~~~~~ removed ~~~~~
•  » » 3 weeks ago, # ^ |   +19 Please wrap your code in .. 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, # ^ |   0 thanks. Careless mistake again :(
 » 3 weeks ago, # |   0 Can somebody help me in figuring out the problem in my code for problem "Let it Flow"?https://ideone.com/mADXszI 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 →   0 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, # |
-40

# ?detaR tI sI

•  » » 3 weeks ago, # ^ |   -24 metog
 » 3 weeks ago, # |   -17 How would we solve "Let It Flow" if there were more than 3 rows ?
•  » » 3 weeks ago, # ^ |   +18 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, # ^ |   +28 Oh, my bad didn't saw that comment.
 » 3 weeks ago, # |   0 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! :-(