I tried looking at id for patterns, but couldn’t find any.
Compressing the coordinates (A[id[i]] = i) preserves the relative order of the original A and doesn’t help either.
I looked at a bubble sort simulation, and in the i-th iteration, we seek to put the i-th largest element in its correct place (unless it’s already there). So I thought about how many elements would be accidentally be put into place on each iteration.
For instance, take this example: 6 5 3 1 8 7 2 4.
(The first row is the element we seek to put in place and the second row is what we accidentally put into place).
8 7 6 5 3
_ _ 1 4 2.
So we have 8-3 = 5 loops until is_sorted = true. Then we loop once again just to “verify” that the array is sorted, so we need 8-3+1 = 6 loops.
It seemed that 2 was accidentally put into place because 2 was after 3 in A. Similarly in 8 7 6 5 4 3 2 1, 1 is put into place at the end because 1 is after 2. I thought of counting how many of the statements “1 is after 2”, “2 is after 3”, …, “n-1 is after n” are true. However, this idea definitely fails.
Can you please give me a hint on this problem? Thank you!
I kinda cheesed this problem lol. You should try proof by AC tbh (that’s what I did at least). Just try as many things as possible. Hopefully you’ll be able to solve it .
Please be more specific. I already tried a lot of ideas. As mentioned in post #1, I tried
Compressing the coordinates / sorting the id’s,
Simulating bubble sort and noticing how many elements were “accidentally put into place”,
Counting how many pairs of consecutive numbers are inverted.
And several more ideas from which I couldn’t make much progress.
Can you [or anyone else reading this thread] please provide a hint into the key idea? Please explain what suggests looking at that particular idea and an example to prove why it works.
For all of the “Out of Sorts” tasks, it helps to start thinking about the case where A_i\in \{0,1\} for all i. In fact, if you can solve this special case in T time, then you can solve the problem in NT time. (Can you figure out why?)
Oftentimes for these sorting/arranging problems it’s more helpful to focus on one individual element and see how it moves. Make some cases and trace the paths of a small or large element. Also think about why bubble sort works.
The number of iterations of the bubble sort is the maximum number of times it takes for an arbitrary number (you should figure out what this arbitrary number is in O(n\log n) time - to sort the array. After sorting, find this arbitrary number in linear time) to be in its proper “sorted” position.
.