an idea about this problem!

I haven't coded this problem yet.

But I think if the test is :

10000

10000 9999 9998 ... 1

It needs 9999 steps to sort this sequence,each step needs to write 10000 elements to the output file.And at last,the output file would contain at least 100000000 elements.I think it's impossible and the problem must be solved with o(N^2) .That's right?

p/s:sorry for my poor english.

Re: an idea about this problem!

No, the number of steps for this test is far less...

Re: an idea about this problem!

Posted by

svr 16 Dec 2008 14:42

I didn't solve too but also have Idea.

Let seggment [a,b] is a maximal subsequence of type a...a+1..a+2...b in x[N].Let NN -number of such segment.

If NN==2 then k=1- number of sortings. I am sure that we can so organaze sort by the such way that on each step NN:=(NN+1)/2. From this we can take formula for k and quick solution.In other words on each permutation mumber of segments should decrease in 2 times.

Now I got Ac And confirmed my idea.

*Edited by author 16.12.2008 20:44*