ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1369. Cockroach Race

Problem 1369 "Cockroach Race". Time limit decreased
Posted by Vladimir Yakovlev (USU) 28 Sep 2012 14:32
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
Posted by rip nsk 7 Jun 2016 03:40
Please decrease time limit again. Trivial brute force can pass all tests:
http://acm.timus.ru/getsubmit.aspx/6872297.cpp
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.cpp
Another way to make this problem interesting is to change N from 10000 to 100000.
Re: Problem 1369 "Cockroach Race". Time limit decreased
Posted by rip&pvs 8 Jun 2016 04:36
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
Posted by rip&pvs 8 Jun 2016 04:43
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
Posted by rip&pvs 9 Jun 2016 02:32
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
Posted by Jane Soboleva (SumNU) 11 Jun 2016 15:24
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
Posted by Vladimir Yakovlev (USU) 15 Jun 2016 04:00
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).