главная новое лучшее написать
2

Задача 8-го дня Advent of Code — Resonant Collinearity.

🧩 Часть I. Условие задачи

В городе расставлены антенны, каждая из которых настроена на определённую частоту, обозначенную символом (az,AZ,09). Если две антенны одной частоты расположены на прямой, и одна из них находится ровно в два раза дальше от точки, чем другая, то в этой точке возникает антинод.

Нужно найти количество уникальных позиций на карте, в которых возникает антинод. Позиции должны лежать в пределах карты. Антенны с разными частотами не создают антиноду.

💡 Идея

Для каждой частоты рассматриваем все пары антенн, стоящих на одной частоте. Каждая пара порождает ровно два симметричных антинода, расположенных по формуле:

(2*r0 - r1, 2*c0 - c1) и (2*r1 - r0, 2*c1 - c0)

Затем добавляем эти позиции в хеш-сет, если они находятся в пределах границ карты.

🧩 Часть II. Условие задачи

Читать дальше →

ответить
3

Ссылка на задачу с LeetCode — 2338. Count the Number of Ideal Arrays.

📋 Описание задачи

Дан массив длины n, состоящий из целых чисел от 1 до maxValue. Массив называется «идеальным», если:

Нужно посчитать количество различных идеальных массивов длины n.
Ответ вернуть по модулю 10⁹ + 7.

💬 Пример

💡 Идея

Читать дальше →

ответить
3

Задача 7-го дня Advent of Code — Bridge Repair.

📘 Часть I. Условие задачи

У инженеров почти готова калибровка оборудования, но из формул пропали все операторы!
Остались только числа. В каждой строке входных данных указано:

Задача: вставить между числами операторы + и *, чтобы получить целевое значение.
Важно: выражения вычисляются строго слева направо, без учёта приоритетов операций.
Например:

190: 10 19
3267: 81 40 27

Требуется определить, какие строки могут быть истинными, и посчитать сумму их целевых значений.

💡 Идея

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

Читать дальше →

ответить
3

Задача 6-го дня Advent of Code — Guard Gallivant.

📘 Часть I. Описание задачи

Нам требуется смоделировать движение охранника по лаборатории, представленной в виде сетки.

Задача — определить количество уникальных клеток, которые охранник посетит, прежде чем покинет карту.​

💡 Идея

Необходимо симулировать движение охранника, учитывая его текущую позицию и направление. Для отслеживания посещённых клеток используется двумерный массив, где каждая клетка хранит информацию о направлениях, с которых она была посещена. Если охранник возвращается в ту же клетку с тем же направлением, это означает начало цикла.

📘 Часть II. Описание задачи

Во второй части задачи требуется определить количество позиций, где добавление одного нового препятствия приведёт к тому, что охранник зациклится и никогда не покинет карту. Очевидно, что нельзя размещать препятствие в начальной позиции охранника.​

💡 Идея

Читать дальше →

ответить
3

Задача пятого дня Advent of Code - Print Queue.

📘 Часть I. Условие задачи

💡 Идея

Для проверки корректности можно обходить последовательность и накапливать множество страниц, которые должны были уже встретиться раньше.
Если мы наткнемся на одну из них позже зависимой страницы, это нарушение!

📘 Часть II. Условие задачи

Теперь рассмотрим некорректные последовательности страниц.
Их нужно перестроить согласно правилам и взять сумму центральных страниц из корректных порядков.

💡 Идея

Это задача на топологическую сортировку.

Читать дальше →

ответить
3

Задача 4-го дня Advent of Code — Ceres Search.

📌 Часть I. Условие задачи

Нам дано поле из символов. Нужно найти все вхождения слова "XMAS".
Слово может быть записано:

💡 Идея

Для поиска всех таких слов:

📌 Часть II. Условие задачи

Теперь требуется найти не само слово XMAS, а X-образное расположение двух слов "MAS" вокруг символа "A".
Пример расположения:

  M . S

Читать дальше →

ответить
3

Ссылка на задачу с LeetCode — 2179. Count Good Triplets in an Array.

📘 Условие задачи

Даны два массива nums1 и nums2, являющиеся перестановками чисел от 0 до n-1.
Нужно найти количество хороших троек (x, y, z), таких что:

📌 Пример

💡 Идея

Рассматриваем каждое число как средний элемент потенциальной хорошей тройки.
Если знать, сколько подходящих чисел было до него и после него, можно посчитать количество троек с этим числом посередине.

Читать дальше →

ответить
3

Задача третьего дня Advent of Code — Mull It Over.

📘 Часть I. Описание задачи

Необходимо выделить все корректные mul(X,Y) и подсчитать сумму произведений.

💡 Идея

Парсим только строки, точно соответствующие регулярному выражению "mul(\d{1,3},\d{1,3})", остальные пропускаем. После чего результат каждого умножения суммируем.

📘 Часть II. Описание задачи

Кроме mul, в дампе встречаются do() и don't():

По умолчанию mul разрешён. Надо подсчитать только те mul, которые активны в момент встречи.

💡 Идея

Читать дальше →

ответить
3

Задача второго дня Advent of Code — Red-Nosed Reports.

📘 Часть I. Описание задачи

Имеется множество отчётов, каждый из которых представляет собой последовательность целых чисел — уровней. Отчёт считается безопасным, если:

Пример безопасных отчётов:

Пример небезопасных отчётов:

💡 Идея

Необходимо пройтись по каждой последовательности и проверить, являются ли все пары элементов:

Если хотя бы одна из этих проверок не выполняется — отчёт считается небезопасным.

Читать дальше →

ответить
3

100 задач с LeetCode мы уже обозрели. Пора переходить к более тяжёлым наркотикам.
Дальше будем смотреть на задачи из последнего Advent of Code.
Задача первого дня — Historian Hysteria несложная и затравочная 😻.

📘 Условие части I

Даны два списка целых чисел одинаковой длины. Необходимо оценить, насколько они различаются.
Для этого:

Пример:

После сопоставления по возрастанию:

Читать дальше →

ответить
4

Проблема: локальные virtualenv'ы для ML-проектов жрут до хрена места, но при этом часто имеют очень много дублирующегося контента.
В моём случае 4 простеньких проекта сходу съедают 21 GB.

$ du -hs ~/.pyenv/versions/*/envs/*
7.6G    /home/rutsh/.pyenv/versions/3.11.11/envs/ASpanFormer
6.0G    /home/rutsh/.pyenv/versions/3.11.11/envs/LightGlue
502M    /home/rutsh/.pyenv/versions/3.11.11/envs/Navigation
5.8G    /home/rutsh/.pyenv/versions/3.11.11/envs/yolo

Хочется как-то более-менее просто дубликаты найти и хардлинками связать друг с другом.

Решение: утилита rdfind уже умеет всё автоматически разрешать - https://github.com/pauldreik/rdfind
В моём случае запуск "rdfind -makehardlinks true /data/pyenv_versions/" превратил 21 GB в 8.7 GB!

Пользуйтесь!!!

Tags: #tools

ответить
4

Ссылка на задачу — 2551. Put Marbles in Bags.

📌 Описание задачи

💡 Идея

При разбиении на k подряд идущих мешков мы делаем k - 1 разрез между кусками.
Каждый разрез влияет на итоговую сумму добавлением пары вида weights[i] + weights[i+1],
где i — индекс последнего элемента в предыдущем мешке.

explanation.png

Следовательно, вся задача сводится к выбору k - 1 пар соседних кусков, которые:

Читать дальше →

ответить
3

Условие задачи — 2874. Maximum Value of an Ordered Triplet II.

📄 Описание задачи

Дан массив целых чисел nums (индексация с нуля).
Нужно найти максимум выражения (nums[i]-nums[j])·nums[k] среди всех троек индексов i < j < k.
Если все такие значения отрицательны, вернуть 0.

💡 Идея

Выражение (nums[i]-nums[j])·nums[k] будет наибольшим, при фиксированном k, если:

Значит, на каждом шаге мы можем поддерживать максимальное значение разности (nums[i]-nums[j]) до текущего индекса и умножать его на nums[k], обновляя лучший результат.

🔍 Детали подхода

  1. Идем по массиву слева направо. На каждом шаге:
    • max_val хранит максимум из всех предыдущих чисел (nums[..i]);
    • max_diff — максимум nums[i]-nums[j] на текущий момент;
    • умножаем max_diff на текущий nums[k] и обновляем best.
  2. Всё делается за один проход, без дополнительных структур данных.

⏱️ Асимптотика

🧾 Исходный код

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        nums.into_iter().fold((0i64, 0, 0), |(best, max_diff, max_val), x| (
            best.max(x as i64 * max_diff as i64),
            max_diff.max(max_val - x),
            max_val.max(x),
        )).0
    }
}

Tags: #rust #algorithms #greedy

ответить
4

Ссылка на задачу — 2780. Minimum Index of a Valid Split.

📘 Описание задачи

💡 Идея

Для эффективного поиска доминирующего элемента хорошо подходит алгоритм большинства голосов Бойера — Мура.
Зная доминирующий элемент, можно пройти по массиву и в каждой возможной точке разделения отслеживать:

🔍 Детали подхода

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

Читать дальше →

ответить
3

Ссылка на задачу — 2140. Solving Questions With Brainpower.

📋 Описание задачи

📌 Пример:

💡 Идея

Читать дальше →

ответить
3

Ссылка на задачу — 763. Partition Labels.

📄 Описание задачи

💡 Идея

Каждая буква должна присутствовать в одной части.
Значит, можно рассматривать все буквы как интервалы [первая позиция, последняя позиция].
Теперь задача сводится к жадному объединению перекрывающихся интервалов: как только текущий интервал завершился, мы фиксируем подстроку.

🔍 Детали подхода

  1. Проходим по строке один раз, чтобы:
    • определить первую и последнюю позицию каждой буквы;
    • зафиксировать порядок появления символов.
  2. Затем проходим по символам алфавита в порядке первого появления:

Читать дальше →

ответить
4

Ссылка на задачу — 3169. Count Days Without Meetings.

📌 Описание задачи

Нужно посчитать количество дней, когда сотрудник свободен от встреч и может работать.

💡 Идея

Мы сортируем встречи по дню начала, чтобы затем обходить их в порядке возрастания.
Это позволяет использовать метод заметания линии как эффективный способ вычислить количество свободных дней между встречами.

🚀 Детали подхода

1️⃣ Сортируем встречи по начальной дате.
2️⃣ Проходим по списку встреч, отслеживая next_free (следующий свободный день).
3️⃣ Подсчитываем разрывы между next_free и началом следующей встречи.
4️⃣ Обновляем next_free после каждой встречи, сдвигая его на день после её окончания.
5️⃣ Добавляем свободные дни после последней встречи.

⏳ Асимптотика

💻 Исходный код

impl Solution {
    pub fn count_days(days: i32, mut meetings: Vec<Vec<i32>>) -> i32 {
        meetings.sort_unstable_by_key(|meet| meet[0]);

        let (next_free, free_count) = meetings.into_iter()
            .fold((1, 0), |(next_free, free_count), meet| {
                let [start, end] = meet[..2] else { unreachable!("bad meet format") };
                let gap = (start - next_free).max(0);
                let next_free = next_free.max(end + 1);
                (next_free, free_count + gap)
        });

        free_count + (days - next_free + 1).max(0)
    }
}

Tags: #rust #algorithms #counting

ответить
2

Следственное бюро Братьев Пилотов сообщает:

Во время загрузки страницы на сервере произошло нечто неладное.

Подозреваются:

error-500.png

🕵️ Что произошло?

Сервер сломался, испугался или просто ушёл пить чай.
К счастью, Братья Пилоты уже ведут расследование!

🧩 Что делать?

"Это вам не простая ошибка. Это — ошибка с усами!"
Шеф (3 минуты назад, после падения сервера).

ответить
3

Условие задачи — 2503. Maximum Number of Points From Grid Queries.

📘 Условие задачи

💡 Идея

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

Такой метод за 1 проход отвечает сразу на все запросы.

🛠️ Детали реализации

  1. Сохраняем исходные индексы запросов и сортируем их по значениям.

Читать дальше →

ответить
4

Ссылка на задачу — 3191. Minimum Operations to Make Binary Array Elements Equal to One I.

📌 Описание задачи

Пример:

💡 Идея

Читать дальше →

ответить
3

Ссылка на задачу — 2033. Minimum Operations to Make a Uni-Value Grid.

📌 Описание задачи

Дан двумерный массив grid размером m x n, а также число x.
За одну операцию можно прибавить или

Читать дальше →

ответить
3

Ссылка на задачу — 3394. Check if Grid can be Cut into Sections.

📌 Описание задачи

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

Если такие разрезки возможны, вернуть true, иначе — false.

Пример

💡 Идея

Поскольку прямоугольники не пересекаются, возможные разрезки должны полностью разделять их на независимые группы.
Мы спроектируем прямоугольники на каждую ось. Если полученные отрезки отсортировать по координатам и просканировать их, можно определить количество неперекрывающихся сегментов, это позволит понять, возможно ли корректное разбиение.

Читать дальше →

ответить
4

Ссылка на задачу — 2594. Minimum Time to Repair Cars.

❓ Описание задачи

Дано:

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

💡 Идея

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

Однако это распределение не покрывает все машины. Для распределения оставшихся машин мы посчитаем для каждого механика оценку времени его работы, если взять несколько дополнительных машин (тем больше, чем больше вес механика). После остаётся лишь выбрать k-ое минимальное значение среди посчитанных времён с помощью алгоритма «QuickSelect» (любезно реализованного в стандартной библиотеке Rust).

🔍 Детали подхода

1️⃣ Быстрое распределение — вычисляем вес каждого механика и распределяем машины пропорционально.

Читать дальше →

ответить
3

Ссылка на задачу — 2115. Find All Possible Recipes from Given Supplies.
В этой задаче для эффективного решения важно не только выбрать эффективный алгоритм, но и аккуратно разложить строки по необходимым структурам данных, избежать лишних копирований и обеспечить ясную картину ownership'a за объектами.

📌 Описание задачи

💡 Идея

Используем рекурсивный DFS для проверки доступности рецептов.
Чтобы избежать повторных вычислений, применяем мемоизацию (кеширование уже проверенных результатов).

Вместо хранения графа явным образом, мы используем индексирование рецептов и проходим по их списку ингредиентов.

🔍 Детали подхода

  1. Предобработка входных данных:
    • Создаём хеш-таблицу для быстрого доступа к индексу каждого рецепта.
    • Добавляем начальные запасы в кеш доступных ингредиентов.

Читать дальше →

ответить
4

Сегодня у нас еще одна задача на аккуратное манипулирование индексами 2337. Move Pieces to Obtain a String.

Описание задачи

Даны две строки start и target длины n, содержащие символы 'L', 'R' и '_'.

Идея 🧠

Задача сводится к тому, чтобы проверить, совпадают ли позиции и направления символов 'L' и 'R' в двух строках с учётом их ограничений на движение. Мы используем итерацию по строкам одновременно, отслеживая доступные символы 'L' и 'R' через счётчики.

Подход 🛠️

  1. Используем метод as_bytes(), чтобы быстро перебрать символы в виде байтов.
  2. Одновременно проходим по обеим строкам:
    • Если видим 'L' в target, увеличиваем счётчик доступных 'L'.
    • Если видим 'L' в start, проверяем, есть ли доступный 'L', и уменьшаем счётчик.

Читать дальше →

1 ответ

Страница 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19