M_H_M's blog

An other Good Problem
By M_H_M, history, 9 years ago, In English

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.

  • Vote: I like it
  • +73
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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"

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

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

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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..

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    It is subsequence on that problem ! And there is no bound for the answer :(

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Well, there is: O(n2)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        And omega(N * N) ?!
        We want to prove O(N) !!

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -26 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like 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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply