The problem is what's the minimum amount of reverse so the array become sorted. I observed in the worst case answer is N-1. But how can I solve the problem?
The problem is what's the minimum amount of reverse so the array become sorted. I observed in the worst case answer is N-1. But how can I solve the problem?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
How did you come to the conclusion that the worst case is N?
I think it's based on that the worst case would be you having to make a reverse in order to put every single element in it's place. For example: 2 3 1
First, you see the number 1 is in the wrong position so you use a reverse to make it 1 3 2
Second, you see the number 2 is in the wrong position so you use a reverse to make it 1 2 3
So, at most you will need N — 1 operations on the worst case, following this strategy: For each element which is not in it's right place, reverse a segment starting with the index where you want to put the number, and ending with the index the number is currently at.
Find i, such that ai is the smallest element of array a among index 1 to n. Then if you reverse a1 to ai, you have the smallest element of a at a1. Again, find the smallest among a2 to an and reverse a2 to ai to bring the 2nd smallest to the 2nd position... and so on...
UPD: This will sort the array using exactly n reverses. Minimum number of needed reverses may be less. So this does not help you finding minimum number of reverse operations. It's only useful if you are allowed to do up to n reverse operations.
This can be done efficiently using treap in O(NlogN) time.
I posted this solution based on the observation of the author of the blog, which says he may do up to N reverse operations. I didn't know there exists better solutions, thank you for mentioning.
Counter-example: 5 1 2 3 4
Answer is 2 (reverse [2, 5] and reverse [1, 5])
Let's run this algorithm another time, but sorting in decreasing order (:
What can you reverse?
Second is my problem. So I understand we can't solve the problem in exponential time complexity. Am I wrong?
We can't solve the problem in polynomial time complexity. We can pretty much always solve problems in exponential time complexity.
Thanks
Actually we can't, most problems are undecidable.
What do you mean by "most"? It's very rare that I see an undecidable problem and most of them are very abstract. For the majority of the problems with finite constraints you can just apply the dumbest bruteforce and get a terribly slow but correct solution (perhaps with exponential memory, too).
nope
P.S. Codeforces downvoters are like a flock of sheep.
Yes, there are more real non-integer numbers than integers. Though, there are almost only decidable problems in the competitive programming.
PS. Don't expect upvotes after writing that downvoters are bad/stupid/etc. It doesn't work this way.
I'm only expecting votes :D
This problem asks what you want. Sort the array with maximum n swaps.
I solved this problem using method similar to selection sort.
Start from first index, find minimum element in the array then swap it with first index. Do same for other indexes. Maximum n swaps.
Code
As linked by cgy4ever your problem is the pancake flipping problem which is NP-Hard, sadly. Anyone who proposes some solution that is polynomial here is most likely wrong.