Obviously, do not discuss problems until after the contest is over. Good luck to everyone competing today, especially to my fellow UVA teams! :D
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 07:58:16 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by MagentaCobra (previous revision, new revision, compare).
What was the solution for the bitonic ordering? Min swaps to make first i elements increasing, and min swaps to make the latter elements decreasing wasn't working apparently.
That doesn't work for the case
4 5 6 7 9 1 10since you can just switch the 10 and the 1.The solution is for every number starting from the number with the lowest value, swap it all the way to the left or to the right. You will only swap with the numbers that are greater than it, so you will need store how many numbers are greater than it to the left and how many are greater to the right, which you can do with fenwick tree.
But making the first 5 elements increasing takes 0 swaps, and last 2 elements decreasing takes 1 swap, so my logic also gives 1 as the answer.
A better example is
2 3 4 1 5 6: it's optimal to move the 1 to the very right, but there's no reason to flip the 5/6 to decreasing.Does anyone know what's wrong with the following solution for bitonic ordering? Spent quite a bit trying to debug/identify the flaw b/c I kept getting the wrong answer. I also could not create a test-case that broke my code:
First, I compressed all values to be in the range [0,n-1], where n is the # of elements.
Now, suppose that index i contains the element with value n-1 (aka maximum in array). From here, it suffices to compute the minimum # of swaps needed to make the left part of the array (a[0] --> a[i-1]) monotonically increasing and the right part of the array (a[i+1] --> a[n-1]) monotonically decreasing.
Now, we traverse from left to right and compute the cost of creating the array such that the max is positioned each possible index i, using two Fenwick Trees to accomplish the task. The answer is the minimum of all such costs.
The complexity is O(NlogN).
we started with a similar idea, but came up with this case:
the answer for this case is 2, by swapping the 5 to the right twice. sorting a prefix and a suffix will cause you to move the 5 over but also swap 50 and 60, giving an answer of 3.
Jeez, if only I had come up with such a test case :( thanks a lot!