This is the case of a particularly small competition! 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. Try to suppose that x0=1 Edited by author 21.09.2007 23:35 Oh, yeah!!! I've got ACCEPTED. Thank you Razdolbay from SIS. You've really helped me. 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 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 How to implement 3d convex hull in O(n*log(n))? The best idea, which I know is O(n^2)... 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? 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. 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 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 I hope, I trust and I wait. 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 Edited by author 01.01.2010 15:46 Whether probably to write qhull algorithm for space of arbitrary dimension? How much it is difficult? Edited by author 05.01.2010 03:10 I think I found counter example for this, ie. set of points of which one is inside the 3D convex hull, but it's appropriate contenstant can win. If we are given for contestant with following speeds: 1 1 2 1 1 4 100 1 3 1 100 3 20 20 3 If we choose paths of length 100, 100, 3, than last contestant (20, 20, 3) can win with time 100/20 + 100/20 + 3/3 = 11. But, for this points 3D convex hull consists of (1, 1, 2), (1, 1, 4), (100, 1, 3) and (1, 100, 3). Does anyone know if I'm wrong and why? Consider that the sum of swim,bike and run is a const number,so we can let the total s=1,then we can solve it for 2D convex hull alogrithm rather than 3D. You should use reciprocals of speeds (preferably multiplied by some constant) as coordinates, but not just the speeds. After applying such an "inversion" to the points in your example, the last one jumps out of the convex hull formed by others. Does anybody know what #8 test looks like? I'm sure my solution is right, but I can't pass this test. Here it is: #include <iostream> int n; int m[100][3]; int main() { std::cin >> n; for (int i = 0; i < n; ++i) { std::cin >> m[i][0] >> m[i][1] >> m[i][2]; }
for (int i = 0; i < n; ++i) { bool found = false; for (int j = 0; j < n; ++j) { if (j == i) continue; if (m[i][0] <= m[j][0] && m[i][1] <= m[j][1] && m[i][2] <= m[j][2]) { found = true; break; } } std::cout << (found? "No" : "Yes") << std::endl; } return 0; } This test could be like 4 501 501 501 500 10000 10000 10000 500 10000 10000 10000 500 Seems the correct answer is No Yes Yes Yes This test could be like 4 501 501 501 500 10000 10000 10000 500 10000 10000 10000 500 Seems the correct answer is No Yes Yes Yes Thank you, great test! I could not even imagine such a case. Can someone who has had problems on this test put a tes the used to figure the problem? Thank you very much Later Edit: This tests helped me: 4 1 1 1 3 1 2 4 1 2 5 2 1 and 3 1 1 1 2 2 2 3 2 2 Edited by author 15.04.2011 02:21 My solution (as well as solutions of some other authors) got AC, but gives incorrect answer for such test case: 3 9999 9999 1 10000 9998 10000 9998 10000 10000 The correct answer is: Yes Yes Yes Please add it to system tests. Edited by author 04.05.2009 00:44 Really, i've got AC with incorrect answer for this test. I used too small infinity (1e10). My solution (as well as solutions of some other authors) got AC, but gives incorrect answer for such test case: 3 9999 9999 1 10000 9998 10000 9998 10000 10000 The correct answer is: Yes Yes Yes Please add it to system tests. Edited by author 04.05.2009 00:44 this test is incorrect ! 9999a + 9999b + 1c > 10000a + 9998b + 10000c 9999a + 9999b + 1c > 9998a + 10000b + 10000c => 19998a+19998b+2c > 19998a+19998b+ 20000c => 2c > 20000c !!!! that why the answer is: No Yes Yes a/9999 + b/9999 + c/1 < a/10000 + b/9998 + c/10000 a/9999 + b/9999 + c/1 < a/9998 + b/10000 + c/10000 a = 9999^4 b = 9999^4 c = 1e-100 I agree with Valentin. We may also choose such a, b and c: a = 9999 b = 9999 c = 1e-9 We get: a/9999 + b/9999 + c/1 = 2 + 1e-9 a/10000 + b/9998 + c/10000 = a/10000 + b/9998 + c/10000 = = 2 * 9999 * 9999 / (9999 * 9999 - 1) + 1e-15 > > 2 + 2 / 9999 * 9999 > 2 + 2e-8 > 2 + 1e-9 So the first contestant can win. 2 1 2 3 1 2 3 Edited by author 23.01.2010 12:58 Question deleted. Edited by author 12.08.2009 21:34 - question deleted. Edited by author 12.08.2009 21:34 #include<iostream.h> struct Triathlon{ int V1; int V2; int V3; }; main() { bool t; int i,j,n; cin>>n; Triathlon*a; a=new Triathlon [n]; for(i=0;i<n;i++) {cin>>a[i].V1>>a[i].V2>>a[i].V3;} for(i=0;i<n;i++) {t=true; for(j=0;j<n;j++) { if(i==j)continue; if(a[j].V1>=a[i].V1) if(a[j].V2>=a[i].V2) if(a[j].V3>=a[i].V3) {cout<<"NO"<<endl; t=false; break;}
} if(t) cout<<"YES"<<endl;} return 0; }
//Thanks Edited by author 11.12.2005 15:21 64 9998 10000 9999 9999 9999 9998 10000 9997 9997 9997 9998 9999 9998 9997 9997 9998 10000 10000 9997 9997 9998 9998 9999 9999 10000 9999 9999 9998 10000 9998 9997 9998 9998 9998 9998 9999 9997 10000 9999 10000 9999 9997 10000 9998 9998 9998 9999 9998 9999 10000 9997 10000 10000 10000 9999 9997 9997 9997 9999 9997 9997 9999 10000 9999 9998 10000 10000 9998 9997 9999 9998 9998 9997 10000 9997 9997 9997 9997 9999 9999 9999 9998 9997 9999 10000 9997 9999 9999 9997 10000 9997 9999 9998 10000 9998 10000 9999 9998 9997 9997 9997 9999 9997 9998 9997 9997 10000 9998 9999 9997 9999 9997 9998 10000 9998 9997 9998 9998 9998 10000 10000 9999 9998 9997 9997 10000 9998 9998 9997 9998 9999 10000 9999 9997 9998 9997 10000 10000 9998 10000 9997 9999 10000 9999 9998 9997 10000 10000 9997 9998 10000 10000 9998 9998 9998 9998 10000 10000 9997 9999 9998 9999 10000 9999 10000 9999 9999 9997 9999 9999 10000 10000 9998 9999 9999 10000 9998 9998 9999 9997 9999 10000 10000 10000 9997 10000 9997 9999 9999 10000 10000 9999 Answer is: No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Thx I've got AC. It's not precision although it looks like so. Nevertheless I still would like to remind programmers of this program to watch out for precision. I recommend 9e9 for infinity and 1e-12 for epsilon. Excuse me how did you get that test, I mean where did you get it. There is so many test that i'd wish to know, so please if there is a way please be so kind tell me. Here is my email aleksamarkoni@gmial.com You would be my friend for life if you do so. :) Thanks in advance. But 3-d convex hull realization may be taken somewhere acide and it is good practice. For me it was taken 5 min to understand that 3-d convex hool could be applied and it is well to context. But difficult to find accurate with hight precision effective realisation but after having it 3-d convex hool more better. Edited by author 07.04.2008 22:34 Could you give me good link? You see, i haven't implemented it because everything i found seemed very time-consuming to write. I'm preparing to olympiad, so i look for algos which i can implement fast without mistakes. As for this problem O(N^3) is ok. One of easy ways is to pick every pair of points and rotate a plane around them through others to get all of them on one side. I think the correct output for the example should be: YES YES YES NO NO NO NO //not YES NO YES if I am wrong plz tell me why this is the way i thought of solving the problem STEP 1: --sort the contestants in descending order: after v | after W | after u 10 2 6 | 1 8 7 | 5 6 7 10 7 3 | 10 7 3 | 3 2 7 10 4 2 | 5 6 7 | 3 5 7 8 4 6 | 3 5 7 | 1 8 7 6 2 6 | 8 4 6 | 10 2 6 5 6 7 | 10 4 2 | 6 2 6 3 2 7 | 10 2 6 | 8 4 6 3 5 7 | 3 2 7 | 10 7 3 1 8 7 | 6 2 6 | 10 4 2 STEP 2: --only the first of each sort might be winners => after v | after w | after u 10 2 6 | 1 8 7 | 5 6 7 10 7 3 | | 3 2 7 10 4 2 | | 3 5 7 | | 1 8 7 STEP 3: --I sort the three columns after the other 2 speeds column 1 --after w and than u --after u and than w column 2 ... STEP 4: -- the first of every sort is surely a winner in conclusion i sort the competitors after: vwu vuw wvu wuv uvw uwv and the first of every sort is a winner hope you cold understand me :) PS: -if you have a nother idea post it plz -if the example is ok than plz tell me why Edited by author 20.02.2005 18:51 STEP 2 is wrong. Try this: 4 100 100 1 100 1 100 1 100 100 50 50 50 The answer should be: YES YES YES YES!!! A my idea. We should find answer for the first contestant. a[i] b[i] c[i] - is the speeds. x y z - the lengths. Write inequation describing that first contestant will win over i-th: (1/a[1] - 1/a[i])x + (1/b[1] - 1/b[i])y + (1/c[1] - 1/c[i])z < 0 Then, we should answer: are exist such x, y and z, that satisfy this inequations for each i > 1? Edited by author 30.03.2005 19:31 Ok, and which algo can answer on this question? A my idea. We should find answer for the first contestant. a[i] b[i] c[i] - is the speeds. x y z - the lengths. Write inequation describing that first contestant will win over i-th: (1/a[1] - 1/a[i])x + (1/b[1] - 1/b[i])y + (1/c[1] - 1/c[i])z < 0 Then, we should answer: are exist such x, y and z, that satisfy this inequations for each i > 1? Edited by author 19.08.2008 12:50 I write a program of only 50 lines that solves this problem, but i get WA at test nr.8. Can someone tell me what is in test 8? i have no idea. thanks. 3 10 10 10 6 100 17 100 6 17 uses windows; var canwin:array[1..100] of boolean; a,b,c:array[1..100] of extended; t1,t2,mi,mc,i,j,k,m,n:integer; l,ml,d,x,y,z,m1,m2,m3,m4,m5,m6:extended; label next; begin randomize; t1:=gettickcount; readln(n); for i:=1 to n do begin readln(x,y,z); a[i]:=1/x; b[i]:=1/y; c[i]:=1/z; end; for i:=1 to n do canwin[i]:=false; t2:=t1; while t2<t1+1500 do begin x:=random(1000000)+1; y:=random(1000000)+1; z:=random(1000000)+1; ml:=a[1]*x+b[1]*y+c[1]*z; mc:=1; mi:=1; for m:=2 to n do begin l:=a[m]*x+b[m]*y+c[m]*z; if l<ml then begin ml:=l; mi:=m; mc:=0; end; if l=ml then mc:=mc+1; end; if mc=1 then canwin[mi]:=true; t2:=gettickcount; end; x:=1; for i:=1 to n do if not(canwin[i]) then begin for j:=1 to n-1 do if j<>i then begin for k:=j+1 to n do if k<>i then begin m1:=b[i]-b[j]; m2:=c[i]-c[j]; m3:=a[j]-a[i]-0.000000000001; m4:=b[i]-b[k]; m5:=c[i]-c[k]; m6:=a[k]-a[i]-0.000000000001; d:=m1*m5-m2*m4; if d<>0 then begin y:=(m3*m5-m6*m2)/d; z:=(m1*m6-m4*m3)/d; if (y>=0)and(z>=0) then begin ml:=a[1]*x+b[1]*y+c[1]*z; mc:=1; mi:=1; for m:=2 to n do begin l:=a[m]*x+b[m]*y+c[m]*z; if l<ml then begin ml:=l; mi:=m; mc:=0; end; if l=ml then mc:=mc+1; end; if mc=1 then canwin[mi]:=true; if canwin[i] then goto next; end; end; end; end; next:; end; for i:=1 to n do if canwin[i] then writeln('Yes') else writeln('No'); end. |
|