Hello everybody. Today, i hope you can help me to solve this problem. I have many ways to solve it if the array has distinct integers. But if the array has repeated elements, i think it is very hard. Can anyone give me some advice ?
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 11:39:32 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Haven't put much thought on this, but my guess would be n - k, where n is the size of the array and k is the value of longest not decreasing subsequence.
for test
2 3 4 ... n 1
you would return 1 instead of n — 1
Sure! Got it wrong. I think the problem it solves is when you are able to change the position of a element instead of swapping two. Any counter examples for this problem?
If you have several equal elements you will never make a swap between them, so you can replace each element with the tuple (ai, i). Notice that now all elements are distinct (and solving this problem is equivalent to solve the previous) and you can do whatever algo you know to solve this.
Would it work for the sequence 1 3 2 2?
Of course. You need to sort the array: [(1, 1);(3, 2);(2, 3);(2, 4)]
The sorted version will be: [(1, 1);(2, 3);(2, 4);(3, 2)]
Notice when comparing tuple we first compare first element, and in case they differ we compare the second element.
In this case you only need two swaps. Actually, after you replace each element by a tuple, you can replace each element by a different integer in the range [1, n], assigning each element its final position in the array, and now you need to solve the problem in a permutation. (Notice you need to sort the array first, to find it's final position).
In this case
(1,1) -> 1 (2,3) -> 2 (2,4) -> 3 (3,2) -> 4so the array you need to sort is:
(1, 4, 2, 3)
But you may use one swap only: between the 3 and the last 2.
My bad, I was thinking in the problem:
Performing swaps between adjacents elementsWill this work if we allow to swap not only adjacent elements?
Friend of mine was asked the same question in Zalando interview round. Could not solve this too. Swapping any two elements is allowed. Anyone with a solution?
I think you or your friend lied. Because there is currently a problem like this in USACO bronze
I have an idea based on the idea of finding "cycles" (kind of like in IOI 1996 "Sorting a Three-Valued Sequence"):
We sort the array, and make notes of where the original array and the sorted array are different. Then, we go from left to right, and whenever we find an index such that the two arrays differ, we do this process:
-in the original array, swap the element at the current index with the element that is at an index where it could be if the array were sorted (for example, if the max element is not where it should be, we would possibly swap it with the element located at the last index). Make sure that while making this swap the two elements have different values (so that it's not a useless swap).
-keep on continuing this process until an element that actually belongs at the current index is swapped in.