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.

# | User | Rating |
---|---|---|

1 | tourist | 3629 |

2 | maroonrk | 3447 |

3 | Um_nik | 3441 |

4 | Benq | 3406 |

5 | ksun48 | 3395 |

6 | ecnerwala | 3380 |

7 | boboniu | 3300 |

8 | Petr | 3268 |

9 | ainta | 3246 |

10 | Radewoosh | 3245 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 197 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 186 |

6 | vovuh | 185 |

7 | Um_nik | 183 |

8 | Ashishgup | 182 |

9 | Radewoosh | 169 |

10 | pashka | 168 |

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.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/02/2020 02:39:08 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

iwe can calculate how manyjare there such thatj<ianda[j] >a[i]. Maximum of this value equals how many steps we need. Maximum value can beN- 1(actuallyN- 2 because of first step). So afterNsteps, 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>ianda[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..

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

Well, there is:

O(n^{2})And omega(N * N) ?!

We want to prove O(N) !!

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