Обсуждение @ 1062. Триатлон @ Timus Online Judge

VC15 (Orel STU) One of the ways to solve [16] // Задача 1062. Триатлон 21 сен 2007 01:23

My solution is based on the next idea. When we check the current contestant we should know if there exists such vector x = (x0, x1, x2) that for every i = 1..n - 1 scalr product (v_i,x) > 0. I use simplex-method to solve this problem with such inequalities:
(v_0, x) >= EPS
(v_1, x) >= EPS
...
(v_n-1, x) >= EPS
x0 >= EPS
x1 >= EPS
x2 >= EPS
x0 + x1 + x2 <= 1500

BUT I HAVE TLE on test 21. I couldn't improve my simplex-method implementation.
Any who solved this problem using algebra, please, give me some hints. Thank you.

Razdolbay from SIS Re: One of the ways to solve [1] // Задача 1062. Триатлон 21 сен 2007 23:34

Try to suppose that x0=1

Edited by author 21.09.2007 23:35

VC15 (Orel STU) Re: One of the ways to solve // Задача 1062. Триатлон 22 сен 2007 21:59

Oh, yeah!!! I've got ACCEPTED. Thank you Razdolbay from SIS. You've really helped me.

svr Re: One of the ways to solve [3] // Задача 1062. Триатлон 9 окт 2007 16:09

Classic idea: 3d convex hull.
Points inside- No,on the boundary -Yes.
But implementation of effective 3d convex hull
is'n easy. Having it done we will have effective
voronoi diagrams and plenty of difficult timus problems
admissible.

Edited by author 09.10.2007 16:11

svr Re: One of the ways to solve [1] // Задача 1062. Триатлон 9 окт 2007 19:46

Additional!
Simplex method is O(exp(n)) for bad tests.
3d convex hull is O(n*log(n)) in wast case.

A got Ac 0.015 using convex hull but and it is
important, in D2 and when body defined as halpfspaces intersection. Simply we may consider a:=a/(a+b+c),
b:=b/(a+b+c),c:=c/(a+b+c) where a,b,c- length of
distances and after use c=1-a-b projecting by the
such way the problem from D3 to D2.

Edited by author 31.12.2008 15:14

Razdolbay from SIS Re: One of the ways to solve // Задача 1062. Триатлон 10 окт 2007 02:32

How to implement 3d convex hull in O(n*log(n))?
The best idea, which I know is O(n^2)...

molphys fti UFU question to svr // Задача 1062. Триатлон 15 июн 2014 16:04

svr писал(a) 9 октября 2007 16:09

Having it done we will have effective
voronoi diagrams and plenty of difficult timus problems
admissible.

I have an quick hull algorithm implementation for an arbitrary dimensional space. Can you provide a list of the problems, which is suitable for application of the convex hull algorithm?

svr Re: One of the ways to solve [9] // Задача 1062. Триатлон 31 дек 2008 15:22

In simple method errors are added and therefore
difficult to use comparing with EPS.
On this problem(I have Ac 0.015 using convex hull in D2)
I fistly understood that combinatorial methods(intersection line and polygone) have big advanteges before
simplex. I used simplex method above BigInteger/BigInteger
in java- righly but very slow,simplex above double- impossible to make choice of EPS and got Ac from the
first attempt using combinatorial approach.

dd (mp dpt USTU) Re: One of the ways to solve [8] // Задача 1062. Триатлон 24 окт 2009 02:30

Why, using transformation of coordinates specified in a post svr, and doing the projection specified in the same place, we receive an equivalent problem? Points pass to external surfaces D3 of set in points at external edges D2 of projective set - is it right?

Edited by author 24.10.2009 04:03

dd (mp dpt USTU) svr, reply to me, please [7] // Задача 1062. Триатлон 24 окт 2009 19:25

svr Re: svr, reply to me, please [6] // Задача 1062. Триатлон 24 окт 2009 19:59

Of course. I am on line all times. That I said is true
but much time is gone. I am Liability on my posts and soon you will have most detailed isue, wait some time,
please.

Edited by author 24.10.2009 19:59

dd (mp dpt USTU) Re: svr, reply to me, please [5] // Задача 1062. Триатлон 24 окт 2009 21:23

I hope, I trust and I wait.

dd (mp dpt USTU) still [4] // Задача 1062. Триатлон 25 окт 2009 16:14

dd (mp dpt USTU) so what? [3] // Задача 1062. Триатлон 26 окт 2009 09:01

svr Re: so what? [2] // Задача 1062. Триатлон 27 окт 2009 08:08

Answer.
This morning I have drinked cofee an remember.
1) h1/ai+h2/bi+h3/ci<h1/aj+h2/bj+h3/cj ~
h1*ai1+h2*bi1+h3*ci1<h1/aj1+h2/bj1+h3/cj1
where ai1=1/ai,bi1=1/bi,ci1=1/ci,aj1=1/aj,
bj1=1/bj,cj1=1/cj. So first convertion is a:=1/a,b:=1/b,c:=1/c
2) h1*ai+h2*bi+h3*ci<h1/aj+h2/bj+h3/cj for all j
is ~ to
(ai-aj)*h1+(bi-bj)*h2+(ci-cj)*h4<0 for all j
or Aj*h1+Bj*h1+Cj*h3<0.
3) Let Q=Aj+Bj+Cj(In my solution i accepted that Q!=0
if no then Cj=-Aj-Bj and so on.)
Let Aj=Aj/Q;Bj=Bj/Q;Cj=Cj/Q.
We have Aj*h1+Bj*h2+Cj*h3<0 or >0 and Aj+Bj+Cj=1.
4) ~ (Aj-Cj)*(h1-h3)+(Bj-Cj)*(h3-h3)< -Cj;
5) Let Qj=Aj-Cj;Sj=Bj-Cl;Rj=-Cj
h1-h3=x1;x2=h2-h3
We have that D2 point (x1,x2) belong to internity of
convex body satisfying system of inequalities
Qj*x1+Sj*x2<Rj or >Rj. This is simmple D2 theory.

Edited by author 27.10.2009 08:09

dd (mp dpt USTU) No subject [1] // Задача 1062. Триатлон 28 окт 2009 03:17

Edited by author 01.01.2010 15:46

dd (mp dpt USTU) No subject // Задача 1062. Триатлон 1 янв 2010 15:38

Whether probably to write qhull algorithm for space of arbitrary dimension? How much it is difficult?

Edited by author 05.01.2010 03:10

Обсуждение задачи 1062. Триатлон