Блог пользователя M_H_M

Автор M_H_M, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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"

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    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 :))

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    N, 1, 2, 3, ,,, , N — 1
    maximum value = 1 but the answer is N — 1

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится

      I think we can fix it with calculate j > i and a[j] < a[i]. Is it true now?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        N / 2 + 1, ..., N, 1, ..., N / 2
        Answer is N — 1 but max value both from left or right = N / 2

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Why "Maximum of this value equals how many steps we need"?

»
8 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -26 Проголосовать: не нравится

Yes. Short proof: number 1 moves to the left. EDIT: missed the "after N steps" part, I'll think about it.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    You can't prove by example :( but it is good think that you found a decreasing function.