Обсуждение @ 1052. Охота на зайцев @ Timus Online Judge

Any tricks in this problem?

Послано zhangmuyang 2 янв 2002 14:00

It seems that everything in my program is OK, but I still got
the "Wrong Answer". I wonder if someone can tell me if there is some
tricks in the program that I had neglected.

Re: Any tricks in this problem?

Послано Miguel Angel 3 янв 2002 11:50

I think there's no trick on this problem. The solution as you may
know is taking 2 points, do the lineal equation and try for all the
points if match in the line. Well, for this problem i saw the fact
that you can use integers without trying with floating point values
(how in city blocks) maybe a fact of rounding cause that you are not
taking some points. Hope this help you:
dy = y[j]-y[i];
dx = x[j]-x[i];
mx = 0;
for (k=0; k<N; k++)
if (y[k]*dx==dy*(x[k]-x[i])+dx*y[i]) ++mx;

I don't think your solution is efficient enough.Yours are O(n^3),but I have a O(n^2) one.You see that my program is the fastest of all.hehe..

Послано Huang Yizheng 3 янв 2002 12:55

Re: Any tricks in this problem?

Послано zhangmuyang 4 янв 2002 12:10

I used 'Extended' in Pascal(equals to 'long doulbe' in C++);
Can it be OK?

Re: Any tricks in this problem?

Послано zhangmuyang 4 янв 2002 12:10

I used 'Extended' in Pascal(equals to 'long double' in C++);
Can it be OK?

Well, not always we can have the best solution, but in the problem "Trash" I do(check time and memory), later i send to you :)

Послано Miguel Angel 5 янв 2002 11:20

Re: Any tricks in this problem?

Послано Molochiy Ivan[ Lviv NU ] 9 мар 2007 20:15

Can rabbits be sutuated on diagonal?

//Sorry for me English

Re: I don't think your solution is efficient enough.Yours are O(n^3),but I have a O(n^2) one.You see that my program is the fastest of all.hehe..

Послано svr 9 мар 2007 20:32

Value N=200 allow use O(N^3) algo.
Therefore better more simple and verified algorithm.
But there is 1422("svetlatcki") with N=2000 and n=3
which the same but need O(n^2lg(n)).
After 1052 try 1422 and question will be understood
at hole.

Edited by author 09.03.2007 20:39

Edited by author 09.03.2007 20:42

Re: I don't think your solution is efficient enough.Yours are O(n^3),but I have a O(n^2) one.You see that my program is the fastest of all.hehe..

Послано LADO ( TBILISI SU ) 16 мар 2007 13:14

Huang Yizheng писал(a) 3 января 2002 12:55

Re: I don't think your solution is efficient enough.Yours are O(n^3),but I have a O(n^2) one.You see that my program is the fastest of all.hehe..

Послано Alias (Alexander Prudaev) 16 мар 2007 22:18

1422 can be done with O(n^2)

Обсуждение задачи 1052. Охота на зайцев