ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1568. Train Car Sorting

How to solve this problem?
Posted by Alexander Bidanets 18 Aug 2014 18:56
Re: How to solve this problem?
Posted by Alexander Bidanets 18 Aug 2014 19:50
Can I solve this problem by natural merge sort?
Re: How to solve this problem?
Posted by Alexander Bidanets 18 Aug 2014 19:51
I have WA #1
Re: How to solve this problem?
Posted by Tolstobrov Anatoliy[Ivanovo SPU] 1 Mar 2017 18:27
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