HackerCup R1 starts in ~24h (July 21 12:00 PET).
Let's discuss the problems after the contest!
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 16:45:28 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
where I can see statements of the tasks of Qualification Round?
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/
https://www.facebook.com/hackercup/problem/1632703893518337/
thanks you both.
Link to the first problem: https://www.facebook.com/hackercup/problem/180494849326631/
Links to the rest can be found on the left sidebar.
Is discussion allowed?
Not while the contest is running.
Nice challenges! Especially the hard two. Was a bit difficult to read problems but fun to solve. Zombies kept me awake until 2 AM...
The problem difficulty feels like going from riding a bike to flying a spaceship
This is so sad, Alexa play Despacito.
Fun problems :) took me a while. Interested in how other solved the yards and zombies problem.
I solved it with O(n3) solution (similar to matrix chain) but solving test cases in parallel. Otherwise couldn't get AC.
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.
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.
Yeah, that’s dumb. Anyway, you can try the “request desktop site” option in your mobile browser. Worked on my Safari.
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.
nvm, i saw there are solutions uploaded
so close lol, probably shouldn't have started this problem in the last 25 minutes
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?
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...
U should make a film based on this. LOL
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.
How about going to University Computer lab :P
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
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..
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.
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 
?
I didn't implement O(N^3) even though I had the idea for it, that's the point.
Ah, got it.
OMG, such a silly mistake i made ,for problem b i called refresh() function after returning from impossible condition,..badluck..
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?
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.
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
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).
Swistakk can you briefly explain why my solution is wrong, like what state can I miss? I am not able to get 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)
After seeing your comment I copy pasted "dp with profiles" on google to learn about it, and got this.
del
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.
Can anyone explain how can I solve first problem (Let it flow) through dp?
how do we apply binary search when dealing with floating point nos,related to problem c..
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:
instead of
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)
okk thanx,but what if ans should have precision upto 5-6 decimal places
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.
makes sense , thanx
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 ?
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.
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.
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 :-(
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.
Just read the replies upthread^
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 :)
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)
I fail on 4th problem because I print "Case %d:" instead of "Case #%d:".
That's why I have a special template for Hacker Cup (and Code Jam) which has a
printCase()function just for printing this.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.
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,
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)
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)?
Model the problem as Negative Cycle Detection problem.
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.
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.
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
could not find the bug for "Ethan Traverses a Tree" :( anyone?
~~~~~
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.
thanks. Careless mistake again :(
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.
?detaR tI sI
metog
How would we solve "Let It Flow" if there were more than 3 rows ?
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.
Oh, my bad didn't saw that comment.