|
|
вернуться в форумПоказать все сообщения Спрятать все сообщения
My solution is 462 bytes long and works 0.12 sec!
Who smaller? :-)
>
> My solution is 462 bytes long and works 0.12 sec!
> Who smaller? :-)
>
>
xe...xe... ;-)
O( N * sqrt(N) ) ? ;)) > xe...xe... ;-)
> O( N * sqrt(N) ) ? ;))
No. O(15*N) > > xe...xe... ;-)
> > O( N * sqrt(N) ) ? ;))
>
> No. O(15*N)
> > O(15*N)==O(N), that's the basics of the mathematic
analysis.
> did you mean O(N*lnN) ?
I know it. But if I write O(N) nobody believe me.
And I didn't write O(N*lnN) because when N = 2, my solution
does 30 iterations.
My solution isn't very small but it's fast, written on
PASCAL (!!!), time=0.06s (see problem statistics)... Who
can write FASTER??? > > O(15*N)==O(N), that's the basics of the mathematic
> analysis.
> > did you mean O(N*lnN) ?
>
> I know it. But if I write O(N) nobody believe me.
> And I didn't write O(N*lnN) because when N = 2, my
solution
> does 30 iterations.
>
>
Do you understand O notation?
It says that for large enough N, the behavior of the
function that describes the running time of your program
tends to the function given. It does not assert that the
running time of your program is always equal to a constant
value of the function given. > Do you understand O notation?
> It says that for large enough N, the behavior of the
> function that describes the running time of your program
> tends to the function given. It does not assert that the
> running time of your program is always equal to a constant
> value of the function given.
Yes, yes, yes.
It's O(N). But I gave some hint, when wrote O(15*N) > > Do you understand O notation?
> > It says that for large enough N, the behavior of the
> > function that describes the running time of your program
> > tends to the function given. It does not assert that the
> > running time of your program is always equal to a constant
> > value of the function given.
>
> Yes, yes, yes.
> It's O(N). But I gave some hint, when wrote O(15*N)
>
I think you're mistaken, 'cause if you can solve the problem with the
time O(n), then you can sort arbitrary array with the same time, wich
is impossible. This is not an arbitrary array. The positions are integers smaller
than 32000. Sorting this kind of arrays is linear with countsort.
> > > Do you understand O notation?
> > > It says that for large enough N, the behavior of the
> > > function that describes the running time of your program
> > > tends to the function given. It does not assert that the
> > > running time of your program is always equal to a constant
> > > value of the function given.
> >
> > Yes, yes, yes.
> > It's O(N). But I gave some hint, when wrote O(15*N)
> >
> I think you're mistaken, 'cause if you can solve the problem with
the
> time O(n), then you can sort arbitrary array with the same time,
wich
> is impossible. >
> My solution is 462 bytes long and works 0.12 sec!
> Who smaller? :-)
>
My smaller! My program is 197 bytes, runs in O(N*N)
time and is the obvious thing everybody writes. It can
become even smaller if i delete the spaces but that won;t
be fair :) and even now the code is quite unpretty.
BTW i think the judge here can report different execution
times for different submissions so 0.12 may become 0.10
or 0.15 if you submit it now. > My smaller! My program is 197 bytes, runs in O(N*N)
> time and is the obvious thing everybody writes. It can
> become even smaller if i delete the spaces but that won;t
> be fair :) and even now the code is quite unpretty.
>
> BTW i think the judge here can report different execution
> times for different submissions so 0.12 may become 0.10
> or 0.15 if you submit it now.
And does it pass new timelimit?
Timelimit for this problem is 1 second now. > And does it pass new timelimit?
> Timelimit for this problem is 1 second now.
my new solution works in 0.22 and is 351 bytes.
Well its complexity is not O(NlogN) but it's obviously
fast enough My runs in 0.08 seconds (but it's 753 bytes :) > My runs in 0.08 seconds (but it's 753 bytes :)
My runs 0.06 & olny 635 bytes! |
|
|
