ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1568. Train Car Sorting

an idea about this problem!
Posted by ConanKudo 25 Jun 2008 15:12
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!
Posted by Vedernikoff Sergey 26 Jun 2008 19:28
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