| ENG RUS | Timus Online Judge |
Discussion of Problem 1568. Train Car SortingAlexander Bidanets How to solve this problem? [3] // Problem 1568. Train Car Sorting 18 Aug 2014 18:56 Alexander Bidanets Re: How to solve this problem? [1] // Problem 1568. Train Car Sorting 18 Aug 2014 19:50 Can I solve this problem by natural merge sort? Alexander Bidanets Re: How to solve this problem? // Problem 1568. Train Car Sorting 18 Aug 2014 19:51 I have WA #1 Tolstobrov Anatoliy[Ivanovo SPU] Re: How to solve this problem? // Problem 1568. Train Car Sorting 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 ConanKudo an idea about this problem! [2] // Problem 1568. Train Car Sorting 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. Vedernikoff Sergey Re: an idea about this problem! // Problem 1568. Train Car Sorting 26 Jun 2008 19:28 No, the number of steps for this test is far less... svr Re: an idea about this problem! // Problem 1568. Train Car Sorting 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 test2008 Calculating k // Problem 1568. Train Car Sorting 7 Nov 2008 04:36 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. pperm Intresting problem, but very easy :) [6] // Problem 1568. Train Car Sorting 8 Oct 2007 15:09 Only 50 lines :) Pascal or C++ Re: Intresting problem, but very easy :) [4] // Problem 1568. Train Car Sorting 8 Oct 2007 18:05 Can you give me some ideas to solve this problem. I think about it very much. Thanks pperm Re: [3] // Problem 1568. Train Car Sorting 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)Решать надо с конца вот и все :) maksay 2pperm [2] // Problem 1568. Train Car Sorting 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:) LX&R Bacherikov [KNU] Re: 2pperm [1] // Problem 1568. Train Car Sorting 3 Dec 2007 20:35 maksay wrote 4 November 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:) Wow, Maksay. You are so wise! Your tips are so brilliant! Everyone should idolize you! Denis Koshman Re: 2pperm // Problem 1568. Train Car Sorting 22 Jul 2008 13:41 tip: google.com has rus->eng translator in their language tools tip: idolize me too! :))) papayawing Re: Intresting problem, but very easy :) // Problem 1568. Train Car Sorting 28 Oct 2007 05:56 How to do it please?
|