Ссылка на задачу — 1980. Find Unique Binary String.
Кайфовая задачка для тех, кто не прогуливал лекции по мат. анализу ☺
📌 Описание задачи
Дан массив nums, содержащий n различных бинарных строк длины n.
Необходимо найти любую бинарную строку длины n, которая не содержится в nums.
💡 Идея
Используем диагонализацию Кантора:
- Если пройти по диагонали массива строк и инвертировать каждый символ (
'0' → '1', '1' → '0'), то полученная строка гарантированно отличается от каждой строки в nums хотя бы в одном символе.
- Это означает, что такая строка не может присутствовать в
nums.
🔍 Подробности подхода
- Итерируемся по индексам
0..n.
- Берем
i-й символ i-й строки.
- Инвертируем его (
'0' → '1', '1' → '0').
- Собираем новые символы в строку и возвращаем её.
📊 Асимптотика
- Временная сложность:
O(n) — один проход по n элементам.
- Дополнительная память:
O(n) — единственное, что создаётся, это строка длины n.
Визуальный пример
🦀 Исходный код
impl Solution {
pub fn find_different_binary_string(nums: Vec<String>) -> String {
let n = nums.len();
// Generate a new binary string by flipping the diagonal elements.
(0..n)
.map(|i| Self::inverse_char(nums[i].as_bytes()[i] as char))
.collect()
}
fn inverse_char(c: char) -> char {
match c {
'0' => '1',
'1' => '0',
_ => unreachable!("Unexpected character: {}", c),
}
}
}
Tags: #rust #algorithms #math
ответить
Ссылка на задачу – 2364. Count Number of Bad Pairs.
📌 Описание задачи
Дан массив nums, где пара индексов (i, j) называется плохой, если выполняется:
Требуется найти общее количество таких плохих пар.
💡 Идея
- Запишем условие хорошей пары:
j−i = nums[j]−nums[i]
- Переставляя слагаемые, получаем:
nums[j]−j = nums[i]−i
То есть если два индекса имеют одинаковое значение позиционной разности (nums[k] - k), – они образуют хорошую пару!
🛠️ Детали метода
- Создаём массив позиционных разностей:
pos_diff[i]=nums[i]−i
- Сортируем массив
pos_diff, группируя одинаковые значения.
- Используем метод
chunk_by для подсчёта частот одинаковых значений.
- Для каждой такой частоты
count, вычисляем количество хороших пар:
count×(count−1)/2
- Всего существует
n × (n - 1) / 2 пар, из них вычитаем хорошие пары и получаем ответ.
⏳ Асимптотика
- Время:
O(n·log n), так как сортировка доминирует над остальными операциями.
- Память:
O(n), так как храним pos_diff.
🔥 Хотя сортировка для подсчёта частот медленнее хеш-таблиц в асимптотике, на практике она быстрее из-за низкой константы!
📝 Исходный код
impl Solution {
pub fn count_bad_pairs(nums: Vec<i32>) -> i64 {
let n = nums.len() as i64;
// Compute adjusted values (nums[i] - i) and sort
let mut pos_diff: Vec<_> = nums.into_iter()
.enumerate()
.map(|(idx, num)| num - idx as i32)
.collect();
pos_diff.sort_unstable();
// Count good pairs using `chunk_by`
let good_pairs: i64 = pos_diff
.chunk_by(|a, b| a == b)
.map(|chunk| (chunk.len() as i64 * (chunk.len() as i64 - 1)) / 2)
.sum();
// Total pairs - good pairs = bad pairs
let total_pairs = n * (n - 1) / 2;
total_pairs - good_pairs
}
}
Tags: #rust #algorithms #math
ответить
Был у меня был период увлечения математической логикой в тщетной попытке понять доказательство независимости континуум-гипотезы от ZFC. Хочу рассказать оттуда об одном занимательном факте и предложить не очень сложную, но красивую, на мой взгляд, задачку.
Сначала немного определений. Назовём структурой произвольное множество M, на котором заданы какие-то отношения. Например, (N, <) - множество натуральных чисел с отношением "меньше", или (R, +) - множество действительных чисел с отношением сложения. "Отношение сложения" - это множество всех троек (x, y, z), для которых x + y = z.
Имея структуру, можно задаться вопросом, какие множества в ней определяемы с помощью стандартных логических формул (и, или, отрицание, существует, для любого). Разрешён знак =, который означает совпадение элементов.
Чтобы определить множество, нужно написать формулу с одной свободной переменной, которая будет верна только на этом множестве. Например, множество чётных чисел в структуре (Z, +) определяется формулой "существует y такое, что x = y + y". Свободная переменная здесь - x, и утверждение верно тогда и только тогда, когда x чётное.
Ещё несколько примеров.
-
Ноль в структуре ( Z, +) определяется формулой "x + x = x".
-
Отношение порядка в структуре ( N, +) определяется формулой "существует z такое, что x + z = y". Эта формула верна, когда x < y.
-
Множество неотрицательных чисел в структуре ( Z, +, *) можно определить с помощью теоремы Лагранжа: "cуществуют такие k, l, m, n, что x = k*k + l*l + m*m + n*n".
Читать дальше →
6 ответов
Наверняка у вас были книжки о математике/программированию, которыми вы зачитывались в подростковом возрасте?
Из тех, которые запомнились мне:
"Математические новеллы", Гарднера и "Алиса в стране смекалки" Рэймонда Смаллиана - обе могу порекомендовать как взрослым, так и детям. #books #math
4 ответа
Все, кто занимается анализом данных, статистикой, машинным обучением или похожими дисциплинами, слышали поговорку "correlation doesn't imply causation" ("наличие корреляции не означает наличия причинно-следственной связи"). Сама по себе эта поговорка абсолютно верна, но её легко понять слишком расширительно и сильно навредить тем самым самому себе. А именно, можно решить, что данные в принципе не могут быть основой ни для каких суждений о причинно-следственных связях, и что любой вывод, сделанный на основе той или иной статистики, сам по себе не может быть поводом для каких-либо действий, за исключением "посмотреть сюда внимательнее".
Это, конечно, не так. Если завоняло серой, это не значит, что рядом бродит чёрт, но если завоняло серой, рядом бродит чёрт, а ваш собеседник продолжает отрицать причинно-следственную связь, то, скорее всего, у него просто KPI привязан к тому, чтобы связи не было.
В дискуссии упоминание "correlation doesn't imply causation", соответственно, часто означает "мне не нравятся ваши выводы, поэтому я хочу вас заткнуть". Поинтересуйтесь у такого оппонента, что он думает про двойное слепое рандомизированное тестирование лекарств, обычно восторг от этой практики как-то необъяснимо уживается в одной голове с этой поговоркой.
in#math
5 ответов
Вот, например, международные математические олимпиады : https://www.youtube.com/playlist?list=PL22w63XsKjqycsMoTIRjPhWXTD6F3LslO
Зовут Майкл Пенн, контента много, снято хорошо, очень аддиктивно.
В процессе просмотра его видео перед сном я наконец-то всей душой поверил в несколько вещей, которые головой в принципе знал и до этого:
- математические олимпиады - это такой спорт, типа бега или CodeForces; золото на межнаре это очень крутое достижение, но кроме таланта для этого обязательно нужно быть "в системе" и посвящать подготовке много времени (ну если вы не Терри Тао), а польза от такой гонки довольно сомнительная
- в любой стране есть выдающиеся умы. Опять же, одно дело знать это умом, другое решать вполне содержательные задачки из национальной олимпиады Таджикистана или Нигерии, мало чем отличающиеся от аналогичных из Австрии или Японии, буквально
- при этом ММО (последний уровень) радикально круче национальных олимпиад, мало того, что гробы, но еще и очень неожиданные, ни на что не похожие. Откуда они их берут в таких количествах?
in #youtube, #math
ответить
TLDR: бруски (примерно как в учебнике физики за 7 класс) выдают последовательные знаки числа Пи (естественно, в теории, то есть без трения, в вакууме и все такое). У этого есть красивое объяснение через фазовое пространство.
in#youtube,#math
1 ответ
Серия естественно выглядящих интегралов, каждый из которых равен пи, пока в какой-то момент вдруг не оказывается чем-то типа 0.9999965 пи. При этом не просто рандомный курьёз, а имеет довольно глубокое объяснение через вейвлеты и преобразование Фурье. У меня только в этот момент окончательно кликнуло, зачем эти вейвлеты вообще нужны.
Если есть фантомные боли по поводу того, что вы не стали математиком, рекомендую подписаться на автора, видео он выкладывает нечасто, но общий уровень очень высокий
in#youtube,#math
ответить
