|
|
| Show all threads Hide all threads Show all messages Hide all messages | | How to solve this problem? | Alexander Bidanets | 1568. Train Car Sorting | 1 Mar 2017 18:27 | 4 | Can I solve this problem by natural merge sort? I solved it via following approach, split array by incrementing sub sequencies (incrementing by 1) and join it back after sorting.
For example 5 1 3 2 4
Will be splited by (5) (1 2) (3 4).
After sort it by first element
(5) (1 2) (3 4) => (1 2) (3 4) (5)
After that all sequences on odd position gos to way #1 and all other to way #2
We will have (1 2 5) in way#1 and (3 4) in way#2 and trust order in array.
we will have (5 1 2) in way#1 and (3 4) in way#2.
And after join in will be (5 1 2 3 4).
Iterate such approach till not get (1 .. N)
Example of output for N=16 and decreasing array.
4
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
15 13 11 9 7 5 3 1 16 14 12 10 8 6 4 2
13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4
9 1 10 2 11 3 12 4 13 5 14 6 15 7 16 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | | an idea about this problem! | ConanKudo | 1568. Train Car Sorting | 16 Dec 2008 14:42 | 3 | 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. No, the number of steps for this test is far less... 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 | | Calculating k | test2008 | 1568. Train Car Sorting | 7 Nov 2008 04:36 | 1 | Is there any way to calculate k by any formula or the only way is to get it through the sorting sequence generation?
I can calculate the amount of steps (and the steps themselves) to sort any input with some fixed length, but obviuosly, there are some sequences of this length, that can be sorted by shorter sequence of steps and I cannot understand how to differ them in the input. | | Intresting problem, but very easy :) | pperm | 1568. Train Car Sorting | 22 Jul 2008 13:41 | 7 | Can you give me some ideas to solve this problem. I think about it very much.
Thanks Re: pperm 9 Oct 2007 22:12 n
p1 p2 ... pn
k
p1 p2 ... pn
...
c1 c2 ... cn-I find it in the first step of my algoritm))
1 2 ... n
My english is bad :)
(RUS)Решать надо с конца вот и все :)
2pperm maksay 4 Nov 2007 21:46 tip: Use translators if your English is bad
tip for others: in English it sounds:
It is neccesary to solve it from the end and thats all:) tip: Use translators if your English is bad
tip for others: in English it sounds:
It is neccesary to solve it from the end and thats all:) Wow, Maksay. You are so wise! Your tips are so brilliant! Everyone should idolize you! tip: google.com has rus->eng translator in their language tools
tip: idolize me too! :))) |
|
|
|
