Discussion @ 1369. Cockroach Race @ Timus Online Judge

Vladimir Yakovlev (USU) Problem 1369 "Cockroach Race". Time limit decreased [17] // Problem 1369. Cockroach Race 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.

rip nsk Re: Problem 1369 "Cockroach Race". Time limit decreased [16] // Problem 1369. Cockroach Race 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

Anatoliy V Tomilov Re: Problem 1369 "Cockroach Race". Time limit decreased [13] // Problem 1369. Cockroach Race 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.

rip&pvs Re: Problem 1369 "Cockroach Race". Time limit decreased [12] // Problem 1369. Cockroach Race 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

rip&pvs Re: Problem 1369 "Cockroach Race". Time limit decreased // Problem 1369. Cockroach Race 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).

Anatoliy V Tomilov Re: Problem 1369 "Cockroach Race". Time limit decreased [10] // Problem 1369. Cockroach Race 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?

rip&pvs Re: Problem 1369 "Cockroach Race". Time limit decreased [9] // Problem 1369. Cockroach Race 9 Jun 2016 02:32

No, I mean absolutely straightforward O(N*M) algorithm, 20 lines of c/++

rip&pvs Re: Problem 1369 "Cockroach Race". Time limit decreased [8] // Problem 1369. Cockroach Race 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.

Anatoliy V Tomilov Re: Problem 1369 "Cockroach Race". Time limit decreased [7] // Problem 1369. Cockroach Race 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.

rip&pvs Re: Problem 1369 "Cockroach Race". Time limit decreased [6] // Problem 1369. Cockroach Race 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

Anatoliy V Tomilov Re: Problem 1369 "Cockroach Race". Time limit decreased [5] // Problem 1369. Cockroach Race 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

rip&pvs Re: Problem 1369 "Cockroach Race". Time limit decreased [4] // Problem 1369. Cockroach Race 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

Anatoliy V Tomilov Re: Problem 1369 "Cockroach Race". Time limit decreased [3] // Problem 1369. Cockroach Race 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.

rip&pvs Re: Problem 1369 "Cockroach Race". Time limit decreased [2] // Problem 1369. Cockroach Race 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.

Jane Soboleva (SumNU) Re: Problem 1369 "Cockroach Race". Time limit decreased // Problem 1369. Cockroach Race 11 Jun 2016 15:24

See profile...

Anatoliy V Tomilov Re: Problem 1369 "Cockroach Race". Time limit decreased // Problem 1369. Cockroach Race 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

Vladimir Yakovlev (USU) Re: Problem 1369 "Cockroach Race". Time limit decreased [1] // Problem 1369. Cockroach Race 15 Jun 2016 04:00

New time limit is set to 2 sec. Thanks for reporting a problem.

Anatoliy V Tomilov Re: Problem 1369 "Cockroach Race". Time limit decreased // Problem 1369. Cockroach Race 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).

Discussion of Problem 1369. Cockroach Race