The input consists of natural number N and M (N <= 2*10^5 and M < N).
Then you are given a permutation of numbers [1, N]
You should sort the given array, but only the following operation is allowed:
Chose a number with index from [0, M-1] and choose a number from [M, N-1], then swap then.
What is the minimum number of operations to sort the array?
Example: Input:
5 3
1 2 3 5 4
**Steps:**
1. 1 2 5 | 3 4 (swap 3 and 5)
2. 1 2 4 | 3 5 (swap 4 and 5)
3. [1 2 3 | 4 5] (swap 3 and 4, now the array is sorted, total steps = 3)
Any idea on how to solve this problem?
Auto comment: topic has been updated by VMaksimoski008 (previous revision, new revision, compare).
Auto comment: topic has been updated by VMaksimoski008 (previous revision, new revision, compare).
Auto comment: topic has been updated by VMaksimoski008 (previous revision, new revision, compare).
Auto comment: topic has been updated by VMaksimoski008 (previous revision, new revision, compare).
Any problem source?
The problem is from Macedonia national olympiad, Task 2,Day 1. If you want to submit solution to the problem, you can go to this site. Click on the British flag and click on Register to create a new account. This is simple, but the submission is not if dont know my language. You should to competitions — > Macedonian olympiad day 1(2023) -> Click on PDF file — > Learn C++ — > National — > PROBLEM 365.
Disclaimer: I do not know how to prove that this is optimal(not even if it is optimal).
Let us draw an edge from each number placed at the wrong index to the number in the corresponding index. Now you get some directed cyclic graph. For each cycle, there are 2 possibilities: it is made out of both numbers $$$\le M$$$ and $$$>M$$$, or it is made of a single type of number. Let the length of the cycle be $$$L$$$. You can solve the first type of cycle in $$$L-1$$$ operations, by keeping it type 1 until you get to 2. The type 2 cycle has to be changed to a type 1 cycle first, so the length becomes $$$L+1$$$, but it is solved in $$$L+1-1=L$$$ operations. In total for a type 2 you use $$$L+1$$$ operations. Then the answer is the number of numbers not well placed — number of type 1 cycles + number of type 2 cycles.
Thanks for the answer. In the meantime I wwas working on a subtask where M=1, and saw a direced cycle, but couldn't realise how to solve when M > 1. Thanks again
Ok, I have been thinking about the problem overnight and realised there is a way to get better cost. If you have 2 cycles of type 2, one made out of numbers$\le M$ and one made of numbers $$$>M$$$, then you can apply one operation and join these 2 cycles together, forming a cycle of type 1. Then it is solveable in $$$L_1+L_2-1$$$. Adding it up, 2 cycles of type 2 containing diferent types of nodes can be solved in $$$L_1+L_2$$$. To recap, first join cycles of type 2 made of different types of nodes, then the answer is the sum of lengths of cycles of type 1 — the count of cycles of type 1 + the sum of lengths of cycles of type 2 + the count of cycles of type 2.
The formula is the same as the previous one.
Sum of lengths cycles type1 + type2 = Numbers on wrong positionYes, but now the number of type 2 cycles is reduced(since we merged an even number of them together).
Cycles are independent, I think you can’t merge two cycles but only change whether they are solely on one side or on both (in regards to m).
I am also unsure but I think it will be like this. Draw edge (one-way) between $$$(i,a[i])$$$ for $$$ 0\le i \le n - 1$$$. We will not take into consideration cycles of length 1, i.e the element is pointing to itself (it is in the correct position).First, let's prove the following lemma. $$$\newline$$$ Lemma: If the array is not sorted, we will have at least one cycle with length $$$\ge 2$$$ $$$\newline$$$ Proof: $$$\newline$$$ Since the array contains numbers $$$[0,N-1]$$$ and we draw edges $$$(i,a[i])$$$, there must be an edge starting from index $$$i$$$ and an edge ending at index $$$i$$$. Let's say that there are exactly $$$k$$$ elements which are misplaced (in the wrong position). Then if we have an edge $$$(i,j \neq i) \implies$$$ both $$$i$$$ and $$$j$$$ are misplaced. This means that if we start traversing from some misplaced point $$$s$$$, there exist $$$k - 1$$$ possibilities where will go next s.t we don't form a cycle. Notice how this number decreases as we continue to traverse the directed graph $$$(k-1,k-2,...,0)$$$. Eventually we will visit exactly $$$k$$$ nodes but still have one edge to go through $$$\implies$$$ the end of this edge will be an index already visited, hence there is a cycle. $$$\newline \newline$$$ Now let's call a cycle good if it contains a pair of indexes $$$(i,j)$$$, such that $$$(m-i) \cdot (m - j) < 0$$$ (they are on a different side in regards to $$$m$$$). On the other hand, we will call bad any cycle where this pair does not exist. (Notice how we are unable to make a move on any cycle that we defined as bad because all elements will be on one side.) This means that we can only rearrange elements between themselves in a good cycle. $$$\newline$$$ Lemma: The minimum number of operations needed to arrange a good cycle is $$$sizeof(cycle) - 1$$$ $$$\newline$$$ Proof: $$$\newline$$$ First, let's show that this is actually possible in every case. Assume there are exactly $$$k$$$ elements in this good cycle. Since there are at least 2 edges that crossed the border $$$m$$$, we can pick a start of the cycle to be an edge that crossed the boarder. More formally, we begin the cycle at a point $$$p$$$ s.t $$$\exists$$$ an edge $$$(p,u)$$$ and $$$(m - p) \cdot (m - u) < 0$$$ AND $$$\nexists$$$ an edge $$$(o,p)$$$ and $$$(m - p) \cdot (m - o) < 0$$$, because in this way will split the cycle into two bad parts (if this is the only such point). If this $$$p$$$ doesn't exist, than we must have more than 1 point that both points at and is pointed by another points on the opposite side (in this case we are allowed to use one of them as $$$p$$$ since it will not break the cycle). If $$$k=2$$$ point $$$p$$$ does not exist and we arrange the cycle in one operation. Otherwise we have to pick this point $$$p$$$ and swap $$$(p,a[p])$$$. $$$\implies$$$ in 1 operation we can place any element on it's correct place if it needs to cross the boarder, and we can arrange a cycle of two elements in 1 operation. If we swap $$$(p,a[p])$$$, what we will have left is a cycle of length $$$k-1$$$. Eventually, if we repeat this proces $$$k - 2$$$ times, the cycle will have only 2 elements, hence $$$T = (k - 2) + 1 = k - 1$$$. Lastly, if there exists a lower cost algorithm, it would require $$$< k - 1$$$ operations and we know that it is not possible since there are $$$k$$$ edges and we cannot place two elements in 1 operation on their correct position unless the cycle has length 2, i.e (both are pointing at each other). In other words, we can use the operation to swap two misplaced elements to their correct positions only once.
Now we have an optimal strategy to solve good cycles and we cannot make an operation to a bad cycle. What is left is to intentionally swap an element from this bad cycle with an element from the other side of $$$m$$$, hence we now have a good cycle of $$$k + 1$$$, if $$$k = sizeof(cycle)$$$. Since we can solve this newly formed good cycle in $$$k$$$ moves, the answer is $$$k+1$$$ because we performed a switch in the beginning. Now let's count the number of bad cycles on one side of $$$m$$$ and on the other side, label them as $$$k_1$$$ and $$$k_2$$$. Then we just subtract $$$2 \cdot min(k_1,k_2)$$$ from our original answer because we can merge a pair of bad cycles on opposite sides and save 1 operation.
In order to solve two bad cycles, one with elements less than $$$m$$$ and one with elements greater than $$$m$$$ you can choose an element from each and do a swap on them. Now you have a good cycle with length equal to the sum of the two lengths of the bad cycles. So instead of doing $$$L_1+1+L_2+1=L_1+L_2+2$$$ you do $$$1+L_1+L_2-1=L_1+L_2$$$.
Oh, nice. So it's more complicated than what I thought. In this case we need to see how many bad cycles on each side. If we have $$$k_1$$$ and $$$k_2$$$ bad cycles smaller and larger than m respectively, can we just subtract $$$2 \cdot min(k_1, k_2)$$$ of my original answer?
Looks good to me.
Thanks for the long answer. But I already solved it two days ago.
Try this, Counter Test:
4 2
2 1 4 3
Ans = 4 Does your solution give 4?
No. My code gives 6 as the answer. But as I said before, my code suprisingly works for 100% test cases. Do you know who made them?
Haha mine did too, I fixed it. Idk who made them, but I have no idea how they didn't put a single test case where this happens, it's impossible it should happen frequently.
I heard that O(n^2) solution worked for day 1 problem 1.