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 1062. Triathlon

One of the ways to solve
Posted by VC15 (Orel STU) 21 Sep 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.
Re: One of the ways to solve
Posted by Razdolbay from SIS 21 Sep 2007 23:34
Try to suppose that x0=1

Edited by author 21.09.2007 23:35
Re: One of the ways to solve
Posted by VC15 (Orel STU) 22 Sep 2007 21:59
Oh, yeah!!! I've got ACCEPTED. Thank you Razdolbay from SIS. You've really helped me.
Re: One of the ways to solve
Posted by svr 9 Oct 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
Re: One of the ways to solve
Posted by svr 9 Oct 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
Re: One of the ways to solve
Posted by Razdolbay from SIS 10 Oct 2007 02:32
How to implement 3d convex hull in O(n*log(n))?
The best idea, which I know is O(n^2)...
Re: One of the ways to solve
Posted by svr 31 Dec 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.
Re: One of the ways to solve
Posted by dd (mp dpt USTU) 24 Oct 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
svr, reply to me, please
Posted by dd (mp dpt USTU) 24 Oct 2009 19:25
Re: svr, reply to me, please
Posted by svr 24 Oct 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
Re: svr, reply to me, please
Posted by dd (mp dpt USTU) 24 Oct 2009 21:23
I hope, I trust and I wait.
still
Posted by dd (mp dpt USTU) 25 Oct 2009 16:14
so what?
Posted by dd (mp dpt USTU) 26 Oct 2009 09:01
Re: so what?
Posted by svr 27 Oct 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
No subject
Posted by dd (mp dpt USTU) 28 Oct 2009 03:17


Edited by author 01.01.2010 15:46
No subject
Posted by dd (mp dpt USTU) 1 Jan 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
question to svr
Posted by molphys fti UFU 15 Jun 2014 16:04
svr wrote 9 October 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?