На самом деле я считаю, что сортировка подсчетом самая простая и самая нужная сортировка, которую нужно знать, например я находил решения довольно сложных для меня задач именно при помощи сортировки подсчетом, могу привести пример:

Задачу 1546C - AquaMoon and Strange Sort я например решил при помощи сортировки подсчетом, так как у неё были маленькие ограничения по числам на футболках (всего до 1e5), я решил создать два массива, где учитывал четные и нечетные индексы массива, а потом пробегался уже по отсортированному масиву и вычитал 1, если индекс стоит на четной позиции из массива с четными номерами (то есть even[a[i]] -= 1) и то же самое делала с нечетными индексами.

Итог:

#include <bits/stdc++.h>

#define ll long long
using namespace std;
inline string solve(vector<int> &odd, vector<int> &even, vector<int> a, int n){
    for (int i = 0; i < n; ++i) {
        if (even[a[i]] != 0){
            if (i % 2 == 0){
                even[a[i]]--;
            }
        }
        if (odd[a[i]] != 0){
            if (i % 2 != 0){
                odd[a[i]]--;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (even[a[i]] != 0 || odd[a[i]] != 0){
            return "NO";
        }
    }
    return "YES";
}
signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];
        vector<int> odd(1e5 + 1, 0), even(1e5 + 1, 0);
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0){
                even[a[i]] += 1;
            }else{
                odd[a[i]] += 1;
            }
        }
        sort(a.begin(), a.end());
        cout << solve(odd, even, a, n) << "\n";
    }
    return 0;
}

Мне бы очень хотелось узнать какие алгоритмы вы считаете незаменимыми и чаще всего используете ;)

Пора углубляться в сортировки и после сортировки пузырьком мы изучим сортировку вставками.

На самом деле, если вам кажется, что сортировка вставками намного быстрее, чем сортировка пузырьком, то вы заблуждаетесь) Потому что если у нас массив изначально отсортирован по убыванию, и мы, когда запустим сортировку вставками от такого массива (а наша сортировка сортирует по возрастанию), то асимптотика такого алгоритма будет O(N * N), потому что каждый новый неотсортированный элемент мы будет засовывать в начало массива => пробегаться по всему массиву заново.

Вот код:

int n = 5; // количество элементов в массиве
vector<int> x = {8, 1, 3, 4, 0}; // сам массив
for (int i = 1; i < n; i++) {
    for (int j = i; j > 0 && x[j - 1] > x[j]; j--) { // пока j > 0 и элемент j-1 > j
        swap(x[j - 1], x[j]); // меняем местами
    }
}
// Вывод массива
for (int i = 0; i < n; ++i) {
    cout << x[i] << " ";
}

Я решил еще решить задачку с помощью метода сортировки вставками:

Ссылка на задачу

Я бы порекомендовал бы вам самим попробовать решить эту задачку именно методом сортировки вставками, но кто вообще слушает рекомендации?)

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
    int n, max_s;
    cin >> n >> max_s;
    vector<int> x(n); // массив на n элементов
    for (int i = 0; i < n; ++i) {
        cin >> x[i]; // ввод элементов
    }
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0 && x[j - 1] > x[j]; j--) { // пока j > 0 и элемент j-1 > j
            swap(x[j - 1], x[j]); // меняем местами
        }
    }
    int sum = 0; // наша сумма 
    for (int i = n - 1; i >= n - max_s; --i) { // 
        if (sum + x[i] > sum){ // так как предметы могут быть отрицательными, то проверяем, что мы взяли положительный
            sum += x[i];
        }

    }
    cout << sum;
    return 0;
}

На этом все, надеюсь вам было интересно :)

Писал я такой спокойно статью про сортировку вставками и вдруг решил я проверить работает ли ссылка на задачу, которую я прикрепил. Перешел по ссылка, а назад уже не мог.

Статья была почти написана, но к сожалению она не сохранилась и для того, чтобы предостеречь тех, кто пишет статьи я хочу сказать, что всегда нажимайте на кнопку сохранить в черновиках или пишите в ворде, потому что остается неприятное ощущение того, что я просрал статью, которую делал на протяжении всего часа + находил для неё интересные задачки, чтобы рассмотреть алгоритм на практике.

В данном блоге я рассмотрю самою простую сортировку, которая поможет вам понять как работают сортировки.

- Почему метод называется методом пузырьком?

- Потому что легкие элементы (наименьшие) как-бы всплывают (прижимаются к левому краю списка), а тяжелые (самые большие) как-бы оседают на дно (прижимаются к правому краю списка). Таким способ массив и сортируется, так как самые элементы будут сортироваться в порядке возрастания: от самых легких, до самых тяжелых.

Что нам понадобиться для написания сортировки пузырьком:

• Умение писать циклы
• умение свопать (переставлять местами) элементы
• Массив

Код на C++:

#include <bits/stdc++.h>

#define int long long
#define forn(i, n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;
const int N = 6;
signed main() {
    int arr[N] = {5, 2, 8, 1, 9, 3};
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N - i - 1; ++j) {
            if (arr[j] > arr[j + 1]){ // сортируем массив по возрастанию
                swap(arr[j], arr[j + 1]); // переставляем элемент arr[j] и arr[j + 1]
            }
        }
    }
    // выводим элементы массива
    for(auto c: arr){
        cout << c << " ";
    }
    return 0;
}

Код на Python:

arr = [5, 2, 8, 1, 9, 3]
for i in range(len(arr)):
    for j in range(len(arr) - i - 1):
        if arr[j] > arr[j + 1]: # сортируем массив по возрастанию
            arr[j], arr[j + 1] = arr[j + 1], arr[j] # переставляем элемент arr[j] и arr[j + 1]
print(*arr) # выводим элементы массива

У вас может возникнуть логичный вопрос: А почему второй for идет от i до N — i — 1?

А потому что мы за каждую итерацию вложенного фора прижимаем наибольший элемент в массиве [0, N — i — 1], сейчас поясню: В первой итерации мы рассматриваем весь массив, от 0 до N — 1. До N — 1, потому что массив нумеруется с 0 и до N — 1.

Так вот:

• Первая итерация: прижимаем к правому краю max(arr[0, N — 1])
• Вторая итерация: прижимаем к правому краю max(arr[0, N — 2])
• Третья итерация: прижимаем к правому краю max(arr[0, N — 3])
• Четвертая итерация: прижимаем к правому краю max(arr[0, N — 4])
• и так далее...

В завершении блога хочу сказать, что этот алгоритм работает за квадрат O(n * n) — это медленно, так что в следующих блогах я рассмотрю более быстрые алгоритмы для сортировки

видео про пузырьковую сортировку: https://youtu.be/g6AAWruaSA8

Привет. Сегодня я буду разбирать задачки, которые помогут вам прокачать свои навыки при решении задач под буквой A. Задачи мы будем разбирать с acmp, так как на этом сайте находятся базовые задачи. Если интересно посмотреть, как дела с рейтингом у меня обстоят сейчас, то перейдите по ЭТОЙ ссылке.

На данный момент моя статистика такая:

---Давайте начнем с простого. Разберем сначала задачу Лифт. Задача на преобразования строк часто встречается в задачах A. Решение

Давайте разбираться. Предположим, что мы сейчас на нулевом этаже. Создадим три переменные: минимальный этаж, максимальный этаж, текущий этаж. Если мы поднялись на один этаж, то будем увеличивать текущую позицию и если она больше, чем максимальная, то будем увеличивать максимальную, а если текущая позиция меньше минимальной, то уменьшаем минимальную. Ответ мы получаем из суммы модулей максимального и минимального этажа и добавляем один этаж, так как если мальчик смог войти в лифт, то дом как минимум состоит из 1-го этажа.

Вот например для теста 21212 рисунок будет выглядеть так:

---Следующая задача будет на дп. Садовник-художник. Эта довольно жизненная задача (особенно для дачников). Решение. Очень просто догадаться о решении, если расписать N для 0, 1, 2, 3:

если у нас 0 деревьев, то количество способов = 0

если у нас 1 деревьев, то количество способов = 3

если у нас 2 деревьев, то количество способов = 6

если у нас 3 деревьев, то количество способов = 12

---Последняя задача будет про деда мороза. Подарки Деда Мороза. Решение.

Варианты решения:

1. написать алгоритм тупым перебором перебрать за O(x * y * z) // или за O(w/x * w/y * w/z), но это все равно будет долго.

2. немного подумать и написать алгоритм за O( w / x * w / y)

Допустим мы подобрали X и Y грамм конфет, тогда Z можно вычислить следующим образом:

z = (w — x * i — y * j), где i и j — количество конфет X и количество конфет Y соответственно!

Я серый и мне это не нравится. Любой, кто хоть раз был серым никогда не забудет этого неприятного ощущения... Если вы думаете, что я не решаю задачи, а просто гоняю BOLD, то вы ошибаетесь. Я каждый будний день решаю задачки и контесты, а на выходных пытаюсь разобраться в ошибках и недочетах, но этот алгоритм обучения похоже не работает, так как я не только не продвинулся в решении задач, а стал решать еще хуже. Я недавно ездил в весеннюю школу от МФТИ и изучил много новых алгоритмов, теперь буду сидеть и разбираться с ними, так как иного пути как развиваться в спортивном программировании я не вижу, как тупо заучивать алгоритмы, а потом, когда будет определенный багаж знаний, то пробовать решать задачки на контестах. Я уже в принципе знаю дп, бин поиск, всякие сортировки. Получается решать задачи на acmp, но там написано на какую тему задача, поэтому я быстро ориентируюсь и пытаюсь копать в одном направлении, но если допустим я вижу эту задачку на codeforces то часто начинаю искать слишком замудренное решение или же слишком простое. Если у вас есть какие-то лайфхаки, как вы обучались спортивному программированию, то буду очень рад выслушать вашу историю)

I create a repository with tasks solution. I am programming on python. If you want to see my own solutions and change them, you can do this