Show all threads Hide all threads Show all messages Hide all messages | WA 2 | Otrebus | 1062. Triathlon | 7 Aug 2021 23:03 | 1 | WA 2 Otrebus 7 Aug 2021 23:03 This is the case of a particularly small competition! | Online tool for 3D plotting | Sirko | 1062. Triathlon | 29 Jun 2017 20:09 | 1 | | Convex hull implementation | Orient | 1062. Triathlon | 29 Jun 2014 02:15 | 1 | | One of the ways to solve | VC15 (Orel STU) | 1062. Triathlon | 15 Jun 2014 16:04 | 17 | 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. still dd (mp dpt USTU) 25 Oct 2009 16:14 so what? dd (mp dpt USTU) 26 Oct 2009 09:01 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 | Counter example for 3D convex hull algorithm | [MF] Radomir Djokovic | 1062. Triathlon | 4 Sep 2013 04:34 | 3 | 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. | WA #8 | Ezrah | 1062. Triathlon | 24 Aug 2011 16:36 | 3 | WA #8 Ezrah 23 Aug 2011 01:53 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; } Re: WA #8 daftcoder [Yaroslavl SU] 23 Aug 2011 11:56 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. | WA #12 | Budau Adrian | 1062. Triathlon | 15 Apr 2011 01:15 | 1 | WA #12 Budau Adrian 15 Apr 2011 01:15 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 | To admins: please could you add such test case | Slusarenko Alexey | 1062. Triathlon | 12 Sep 2010 21:47 | 5 | 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. | What is the answer for this Test ? can anyone give me a help? | Nguyễn Cảnh Toàn | 1062. Triathlon | 23 Jan 2010 12:58 | 1 | 2 1 2 3 1 2 3 Edited by author 23.01.2010 12:58 | I know why I was wrong. | ACcreator | 1062. Triathlon | 12 Aug 2009 15:22 | 2 | Question deleted. Edited by author 12.08.2009 21:34 - question deleted. Edited by author 12.08.2009 21:34 | Please give test 8 | Evolution | 1062. Triathlon | 4 Dec 2008 21:50 | 1 | | Please say why i have WA#8 | Evolution | 1062. Triathlon | 2 Dec 2008 22:32 | 1 | #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 | WA on test #24. I hope it's not because of precision. Could anyone give me the test? Either here or by mail, thx | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1062. Triathlon | 17 Nov 2008 05:34 | 5 | 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. | Use algebra, neither simplex method nor 3d convex hull | hedrok | 1062. Triathlon | 21 Aug 2008 04:33 | 4 | 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 EXAMPLE IS WRONG !!! plz take a look | Manastireanu | 1062. Triathlon | 24 Nov 2007 18:00 | 3 | 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? | No subject | Meni Packeou | 1062. Triathlon | 24 Aug 2007 17:08 | 1 | Edited by author 19.08.2008 12:50 | Anybody could tell me what the tricks are in this problem? | Li Ang | 1062. Triathlon | 24 Aug 2007 16:57 | 2 | | WA#8 | Grosu Andrei | 1062. Triathlon | 8 Aug 2007 21:36 | 1 | WA#8 Grosu Andrei 8 Aug 2007 21:36 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. | Can you tell my the answer for this test and why? | Alexandru Tandrau | 1062. Triathlon | 13 Dec 2006 17:11 | 1 | 3 10 10 10 6 100 17 100 6 17 | Where is my mistake? WA #14 | DWED | 1062. Triathlon | 16 Dec 2005 14:24 | 1 | 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. |
|
|