### M_H_M's blog

By M_H_M, history, 4 years ago, Hello :)

Consider permutation p from 1 to N
Every permutation has a decomposition to decreasing substrings.
Step : Reverse all decreasing substrings.
Prove or disprove that p will be sorted after N steps.  Comments (14)
 » 4 years ago, # | ← Rev. 2 →   In 1 step, all decreasing substrings are reversed or only one?If I have 5 6 3 4 1 2 (only 5,6 or any other such combo is reversed or all decreasing substrings are reversed in first step)Got it. I didn't read that you mentioned "every permutation has a decomposition of decreasing substrings"
•  » » All of them ! 5 6 3 4 1 2 => 5 3 6 1 4 2 => 3 5 1 6 2 4 => 3 1 5 2 6 4 => 1 3 2 5 4 6 => 1 2 3 4 5 6 In five steps :))
 » Reverse all decreasing substrings for once. After that, maximum length of decreasing substring will be 2. For all indices i we can calculate how many j are there such that j < i and a[j] > a[i]. Maximum of this value equals how many steps we need. Maximum value can be N - 1(actually N - 2 because of first step). So after N steps, permutation will be sorted.
•  » » N, 1, 2, 3, ,,, , N — 1 maximum value = 1 but the answer is N — 1
•  » » » I think we can fix it with calculate j > i and a[j] < a[i]. Is it true now?
•  » » » » N / 2 + 1, ..., N, 1, ..., N / 2 Answer is N — 1 but max value both from left or right = N / 2
•  » » Why "Maximum of this value equals how many steps we need"?
 » The problem is here: http://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf and the solution here: http://hsin.hr/coci/archive/2011_2012/contest1_solutions.zip, I hope it helps you..
•  » » 4 years ago, # ^ | ← Rev. 3 →   It is subsequence on that problem ! And there is no bound for the answer :(
•  » » » Well, there is: O(n2)
•  » » » » And omega(N * N) ?! We want to prove O(N) !!
 » 4 years ago, # | ← Rev. 2 →   Yes. Short proof: number 1 moves to the left. EDIT: missed the "after N steps" part, I'll think about it.
 » It seems the problem is correct even for N - 1 steps. I have an idea how to solve it, but I haven't managed to turn it into the solution. Let us call a potential of a number: 0, if the number is already at its destination point; (distance from its destination)+(the length of maximal increasing sequence from number to its destination) otherwise. As an example, evolution of a sequence is below (potentials are under the numbers). The potential of '7' in the first row of example below is 6, because it is a distance from the place of 7 to 7-th place, and "71" is not an increasing sequence. The potential of '2' is 1, as distance from destination is 1, and "12" is increasing, so '1' gives additional potential. The potential of '8' is 3, because dist=2, and '9' gives additional point, as "89" is increasing, however, "895" is not increasing, so there is only 1 additional point. The potential of '6' is 2, because dist=1, and "68" increases, which gives additional 1. "689" also increases, but '9' is already beyond the destination of 6, and it doesn't counts. Another example: the potentials of "56781234" are "76544567". 712468953 612023236 --------- 172468359 051022440 --------- 127463859 004013130 --------- 124736589 002320200 --------- 124375689 001121200 --------- 123457689 000001100 --------- 123456789 000000000 It is easy to see that the potential cannot be greater than N - 1. My conjecture is that the maximal potential decreases every turn, and the problem follows from it. But it is not so easy to prove or disprove:/ I suppose I could give a rather technical proof, if it is actually true, after thinking a bit more.
•  » » You can't prove by example :( but it is good think that you found a decreasing function.