Problem 1369 "Cockroach Race". Time limit decreased
The new time limit for the problem id 4 seconds. With old time limit 5 seconds bruteforce solutions could pass all tests.
Re: Problem 1369 "Cockroach Race". Time limit decreased
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
Orient 7 Jun 2016 22:10
I think time limit should be decreased down to 1 second. It is not hardest problem otherwise.
My AVX solution w/o custom input/output can pass all the tests too.
http://acm.timus.ru/getsubmit.aspx/6871223.cppAnother way to make this problem interesting is to change N from 10000 to 100000.
Re: Problem 1369 "Cockroach Race". Time limit decreased
AVX? :) if solution requires manual vectorization to avoid TL - it is still hard problem,
but trivial (double precision) arithmetic is enough here for now.
Edited by author 08.06.2016 04:43
Re: Problem 1369 "Cockroach Race". Time limit decreased
IMO time limit should be 2 (or 3) seconds - it breaks brute force, at least for now,
but still allow(?) good java solutions (best - 1.7 seconds).
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
Orient 9 Jun 2016 00:18
Simple arithmetic gives TLE 9. BTW Fortune's algorithm also implies just only trivial arithmetic (i.e. +-*/), do you mean this?
Re: Problem 1369 "Cockroach Race". Time limit decreased
No, I mean absolutely straightforward O(N*M) algorithm, 20 lines of c/++
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
rip&pvs 10 Jun 2016 03:24
So, I reached 1.7 seconds It is not brute force now (since there are several non-trivial optimizations), but it is still O(N*M) algorithm... It should be 1.5-2X faster when AVX512 is available.
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
Orient 10 Jun 2016 06:54
AVX (256 bit, 4 dobule) is not faster then SSE (128 bit, 2 double) on the judging system, though. Because of bus width, I think.
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
rip&pvs 10 Jun 2016 11:50
gcc msvc
1xD: TL9 3.260
2xD: 1.981 2.308
4xD: 1.575 1.482
Edited by author 10.06.2016 12:55
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
Orient 10 Jun 2016 18:36
I really want to see your solution! Can we trade it for top3?
Edited by author 10.06.2016 22:27
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
rip&pvs 11 Jun 2016 00:37
Just understand what is "top3" - thank you - no, I like problem solving :)
Edited by author 11.06.2016 06:44
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
Orient 11 Jun 2016 10:05
That means problem 1548.
Anyways I will to solve this problem using Voronoi. But now I just especially interested in manual vectorization technique. And SSE/AVX/AVX512 solution is just a "reference point" for "right" solution via Fortune's algorithm.
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
rip&pvs 11 Jun 2016 11:34
Yep, I understood.
Please share your email. I don't think that my solution will help you, it is based on very specific optimizations.
Re: Problem 1369 "Cockroach Race". Time limit decreased
See profile...
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
Orient 11 Jun 2016 18:28
How to improve SSE solution in such a way, that it became 2.5x faster? Very interesting optimizations should be here.
Edited by author 13.06.2016 01:39
Re: Problem 1369 "Cockroach Race". Time limit decreased
New time limit is set to 2 sec. Thanks for reporting a problem.
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by
Orient 15 Jun 2016 07:37
It seems that solutions of other problems may have benefit from new hardware too. Maybe it make sense to rejudge a couple of tens of hardest problems (at least 100-200 top solutions).