This is the case of a particularly small competition!

https://technology.cpm.org/general/3dgraph/
Just in case someone (like me) needs a handy tool for 3D points visualization

https://github.com/tomilov/quickhull

Edited by author 28.04.2016 19:03

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.

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?

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;
}

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

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

#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

My solution runs only 0.015 (http://acm.timus.ru/status.aspx?space=1&num=1062&author=34678) and is based on simple algebra only.
Maybe 3d convex hull is faster, but it is much more complex to implement.
So i think Huang Yizheng is right. My solution isn't greedy at all and i think it's right.

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

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.