Блог пользователя master_flomaster

Автор master_flomaster, история, 3 года назад, По-русски

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

Задачу 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;
}

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор master_flomaster, история, 3 года назад, По-русски

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

Как работает эта сортировка?

На самом деле, если вам кажется, что сортировка вставками намного быстрее, чем сортировка пузырьком, то вы заблуждаетесь) Потому что если у нас массив изначально отсортирован по убыванию, и мы, когда запустим сортировку вставками от такого массива (а наша сортировка сортирует по возрастанию), то асимптотика такого алгоритма будет 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] << " ";
}

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

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

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

Решение

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

Автор master_flomaster, история, 3 года назад, По-русски

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

Автор master_flomaster, история, 3 года назад, По-русски

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

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

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

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

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

Код на 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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор master_flomaster, история, 3 года назад, По-русски

Привет. Сегодня я буду разбирать задачки, которые помогут вам прокачать свои навыки при решении задач под буквой 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 соответственно!

Полный текст и комментарии »

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

Автор master_flomaster, история, 4 года назад, По-русски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

Автор master_flomaster, история, 4 года назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится