Hey community!
Round 1 starts less than 24 hours.
Let's discuss problems here after contest.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
https://www.facebook.com/hackercup/round/1825579961046099/ Link for round 1, if somebody needs
Интересно, а использование Полигона для тестирования задач во время раунда ничего не нарушает?
Let me guess the title of one of Round 2 problems: Umbrellas, bitch!
What is the memory limit in Hacker Cup?
As long as it runs locally it's fine.
people : How's the contest going?
me :
I am getting the links for the contest only from CF. Where are links written on the official page? I can't find it.
This is the post for Round 1, on the official Facebook page.
They posted it here (along with the point cutoff) shortly before the round started: https://www.facebook.com/hackercup/posts/1384524328246418
Does anyone have any idea about file size or memory constraints? I need to use about 10^9 integers :v
It's okay to use it, if it runs locally.
I believe it is fine just as long as you manage to produce the output file. (does not have to run locally. i.e, if you use a online compiler and such)
Note to self: Always check if you swapped the output/source files.
Out of 5297 participants:
How did you manage to get these numbers?
Probably by just clicking through the standings page, takes 5 minutes at most.
2 if you involve binary search (provided you have a fast net too) :v
For A: Pie Progress, wouldn't O(N**2 * M) DP be too slow? I see that it is mentioned in editorial as a solution. Did anybody get it to run?
Yes, in 2s it passed the input file.
I solved it that way as well.
N and M are only up to 300, so a cubic solution is perfectly fine.
There is a O(N * M * log(N)) solution using divide and conquer DP optimization.
You can use winner tree data structure and it would take n*m*log(m)+n*log(n)
I managed to solve it greedily: solution.
I can explain if someone is interested.
N^2*M is too fast for 6 minutes.
Poor network.... When I finish the coding of A, and click the "submit" button. It costs about 5minutes for downloading the input about 5 MB input. Fortunately, I run and upload as quickly as possibly. I suddenly realize why the problem C has a DP solutions with O(N^3+K) but K is only 5000, not 1e6.
I also have problem downloading the input files. Because Facebook is censored in Iran I have to use VPN and it slows down the network. It takes me minutes to download the input files.
Now that the round has finished, what's your output to the following testcase? [Problem B]
Of course, it is 4.
Edit: saw the editorial, it's quite neat. However, I guess many contestants (including me) answer 3 on this test. :)
I didn't really expect to get AC with this solution, but somehow I got it.
This is indeed the intended solution.
Yes, I already read the editorial and was surprised. With this solution the task becomes easier, than first.
And your solution passed?
Well, no — I failed on a single test having n = 2. xD
However, quite a few of my friends passed, yet they get incorrect result on my test. All of these people stated that any feasible Move operation should be one of the following:
However, the test proves this approach wrong.
It's OK, shit happens :)
Just curious, which of mentioned Move operations has your solution used? Let me guess — triples of points?
He meant that some people tried all of those rules in their solutions. But it's still wrong.
Thanks, understand now.
This approach is not completely wrong, there is one more operation type to check:
This passed in the round and returns correct result for your test
------ UPD: Well, I challenged myself with a slightly modified test case
Got 5 instead of 6
You can only check for circle of infinite radius which is a half plane.
Take a look at this comment for proof.
Will FBHC ever start creating good testcases :|? FBHC's quality of tests is pretty pathetic. In previous round, I am sure a lot of people will fail cases mentioned in topic about quals in first problem. Here in B many people including me did some stupid things like "create a circle passing through every triple of points" which can be done right, but it is very easy to get them wrong. And I expect many of passing solutions to that problem to actually fail on some cases. Mine fails case mentioned by mnbvmar, but there are other families of testcases which can be troublesome to many solutions. Model solution is great and contains no weird geometry with circles, and I know it is impossible to create perfect tests, but it looks like FBHC organizers do not even try to come up with any wrong solutions or think about mistakes that competitors can do which is essential in order to create good tests.
I thought about solution for triples and proved, that it's incorrect. So I sent O(n^5) brute with 2 squares, because I coudn't disprove it. I didn't really prove it.
And your "stupid things" passed?)
Yeah, I did exactly what mnbvmar described and it fails on test provided by him, but it passes systests.
Wow. If so — congrats to you for bypassing it and shame on FBHC tests creators.
Can't agree more. Looks like the most part (if not all) of the tests is generated by a pure random.
By the way, if even with current weak test cases of FHC many strong coders fail problems, just imagine how cruel system testing would be with strong enough tests. If I could participate in such a competition, I would be sooo happy, it could be much more interesting and funny.
Hah, you think your solution is the worst that passes the full testset? Take a look at this.
Looks like they lack experienced problemsetters among round authors.
Well I didn't get the intended solution. But I just decided to check all possible sets of points which one could bound in a circle. So it's either empty subset, some vertex, or we should choose two of them and look over all circles passing through these two and some other vertex. You can just look over a perpendicular bisector and sort all centers of these circles (and using scan-line get n+-eps circles). That's where I was afraid of EPS problems, so I made everything in ratios of (__int128/long long) (but was pretty sure that authors would forget about it). After that I have O(n^3) sets, and I check them in O(nlogn) by events on scan-line.
Well I'm really sad that something like you're describing passed systests with such small effort. I hope there will not be such a problem in the next rounds.
You should've also checked circles of infinite radius.
I don't need to check them.
Last time I didn't have enough time to prove that having two potion of second type is the same as having one of each.
You should've also checked circles of infinite radius. Which turns out to be enough and there is no need to check for other types of circles.
A circle of infinite radius turns out to be a half plane.
It's obvious that having two potion of second type is as good or better than having one of each.
And it's possible to cover any pair of squares only by transforming using a half plane(potion of first type can do this) and then using a potion of second type. (If area of the intersection is 0 it's obvious. And if intersection has positive area then primers of squares are either intersecting in infinite number of points which is obvious that we can transform this or they intersect in two points. Draw a line through two points and transforming one side of the line.)
We've showed that having one potion of each type is the same as having two of second type.
I didn't understand what you called "potion". I just told you that I had different solution. I'm not checking halfplanes (yes, it's enough, and it's the intended solution). I check all circles (and halfplanes are also checked by themselves as case of center lying far away from two points). You can read how to do it more precisely in the answer to Swistakk lower. Or read my code.
Sorry it's my mistake. I used "potion" instead of "geometer".
Always wizards make potions but here in this problem they make geometers!
And yeah I see that now.
Nice trick! It can be useful in many problems.
Did you consider circles which almost contain some point? I mean, if we fix two points and consider event "in time T point P appears" then we need to create circles for times both T and T-eps (similarly with disappearing). You didn't mention it, but I guess you did it because I couldn't hack your solution.
I automatically checked it. So for example if you choose points (0,-1) and (0,1), centers are always on the line (c,0). Let's look at some other point (x,y). If x = 0 then it's doesn't matter what c you chose (you are always inside or outside). If x != 0 then let's denote the center of (0, 1), (0,-1) and (x,y) as (z, 0). if (x > 0) then you're inside the circle if c >= z (if x < 0 then you're inside if c <= z). So I start increasing c from -inf to inf, sometimes changing states of points (maximum once for one point). As always in scan-line algorithms you should fix the order in which you consider events with equal c (this will automatically at first check c and after that c + eps).
I also have the solution which tries circles passing through 2 or 3 points (or almost zero area circles containing just 1 point) — and, as mentioned, it passed the test cases I got (although there are counter examples to this approach). But what's worse is that it would have passed all the test cases even with trying just circles defined by any pair of points (I printed the results I got without considering triples of points and they were all the same for the official test cases I got). Of course, during local testing, I could easily find test cases where triples of points were producing better solutions than just pairs of points.
To those who don't understand that testcase (like me), here is a picture (source in Asymptote):
Red are points from the input, blue circle specifies the correct area for the "Move" spell, blue arrows are its direction, blue rectangle is the correct area for the "Destroy" spell. Note that only points 2 and 3 are moved and as a result they coincide with points 0 and 1, which could be covered by the rectangle.
However, if you assume that the circle is a circumcircle for some subset of points, you gonna have a bad time: magenta circle is a circumcircle for 2 and 3, but it also covers point 1. So, one should also consider circles of greater radius.
My thinking process was (as apparently there was no limit on radius of circle) that I can actually approximate any line segment of length R (or longer) with the circle. Which is true in the limit. So I dropped that idea about circles (who does circle geometry in second problem in Round 1 anyway??) and just thought whether I can separate points I need to move by line. And it immediately leads to the idea that you should just look for two squares.
i wish to add the contest to gym. i can download inputs and solutions? if i can't, please, share it to me! thank you!
RIP english, I assume you want the I/O files to make a gym contest, in that case you can find full I/O files here: https://www.dropbox.com/sh/bvnrwslazmr5ztc/AACZYKtzHq1mY4YrRQN-GFbDa?dl=0
thank you a lot! i know that my english is worst, because i was learn german in the school. ;(
Hey! Where can we find the editorial for this.
Editorial link
It made me laugh that the test cases for the problem D included only R_i <= 50 although "Ri <= 20000" was written in the statement.
Fail. My solution works in O(N·maxR) per test (or
per test).
I am reading editorial for the problem Manic Moving and I am thinking about the following sentence:
f(0, P, H) =the length of the shortest path fromPto theN-1th family’s destination, and then to theN-2th’s family’s destination ifH = 2.Did they make a mistake with the visiting order? Maybe we should first go to
N-2th family destination and only after that to theN-1family?Note that R = 0 here. So, there aren't any belongings left to deliver after this. Hence, to achieve this, we must have transported family N-1's belongings. If H=2, it means we also had family N-2's belongings loaded in the truck.
in problem "Manic Moving" ... if we have this "His truck is large enough to fit at most 2 families sets of belongings at a time" ==> "and fit at most "p" families ..." !
how can solve it? ... order?
Is it correct implementation?
I am particularly interested in the correctness of the following part:
It seems like this code doesn't handle the case when the optimal path for 3 families looks like that (s — starting vertex, f — finishing vertex):
s1 ⟶ s3 ⟶ f1 ⟶ s2 ⟶ f2 ⟶ f3.
But this code has passed all of the tests.
Quote from the statement:
The
part seems to violate this rule.
For some reason I skipped part of the last sentence and read it like this:
Thank you for pointing me at my mistake.