Задача G ШАД 2025
Приветствую всех, на повестке дня разберем легчайшую первую задачку из алгоритмической части второго этапа отбора в ШАД. Математическая часть выдалась трудной, поэтому выигрышной стратегией было забирать бесплатные баллы за задачки G и H.
Условие задачи G
На вход дана число A (1 <= len(A) <= 10^6, где len(A) это количество цифр в числе). Пусть S(A) - сумма всех циклических сдвигов, числа A, от вас требуется посчитать сумму всех цифр A.
Разбор
Посмотрим, как работают циклический сдвиги и как изменяются позиции i-го элемента:
нулевой сдвиг: a[i]
первый сдвиг: a[i + 1]
k-й сдвиг: a[i + k] если i + k < n, иначе a[i + k - n]
Видно, что эту операцию удобно выразить, как (i + k) % n. Тогда мы можем расписать S(A) (P.S. ^ -пусть будет возведением в степень)
S(A) = sum(sum(a[(i + k) % n] * 10^(n - 1 - i) for i in range(n - 1)) for k in range(n - 1))
Заметим, что мы можем заменить порядок суммирования и вынести 10^(n - 1 - i) и тогда под вторым знаком суммы будет фиксированная величина (а именно суммы всех цифр, обозначим её за Sum_dec), а степени десяток можно свернуть по формуле арифметической прогрессии.
S(A) = sum(sum(a[(i + k) % n] for k in range(n - 1)) * 10^(n - 1 - i) for i in range(n - 1)) =
sum(Sum_dec * 10^(n - 1 - i) for i in range(n - 1)) =
Sum_dec * (10^0 + 10^1 + 10^2 + … + 10^(n - 1)) =
Sum_dec * (10^n - 1) / 9 =
Sum_dec * 111…111 (n единиц)
Важное уточнение, последнюю величину можно вычислить сразу только на питоне (так как n слишком велико ~10^6, а в питоне есть длинку) и далее просто проссумировать все цифры. Для решения на с++ же, требуется реализовать простое умножение в столбик суммируя цифры в каждом десятке.
@algoses
Приветствую всех, на повестке дня разберем легчайшую первую задачку из алгоритмической части второго этапа отбора в ШАД. Математическая часть выдалась трудной, поэтому выигрышной стратегией было забирать бесплатные баллы за задачки G и H.
Условие задачи G
На вход дана число A (1 <= len(A) <= 10^6, где len(A) это количество цифр в числе). Пусть S(A) - сумма всех циклических сдвигов, числа A, от вас требуется посчитать сумму всех цифр A.
Разбор
Посмотрим, как работают циклический сдвиги и как изменяются позиции i-го элемента:
нулевой сдвиг: a[i]
первый сдвиг: a[i + 1]
k-й сдвиг: a[i + k] если i + k < n, иначе a[i + k - n]
Видно, что эту операцию удобно выразить, как (i + k) % n. Тогда мы можем расписать S(A) (P.S. ^ -пусть будет возведением в степень)
S(A) = sum(sum(a[(i + k) % n] * 10^(n - 1 - i) for i in range(n - 1)) for k in range(n - 1))
Заметим, что мы можем заменить порядок суммирования и вынести 10^(n - 1 - i) и тогда под вторым знаком суммы будет фиксированная величина (а именно суммы всех цифр, обозначим её за Sum_dec), а степени десяток можно свернуть по формуле арифметической прогрессии.
S(A) = sum(sum(a[(i + k) % n] for k in range(n - 1)) * 10^(n - 1 - i) for i in range(n - 1)) =
sum(Sum_dec * 10^(n - 1 - i) for i in range(n - 1)) =
Sum_dec * (10^0 + 10^1 + 10^2 + … + 10^(n - 1)) =
Sum_dec * (10^n - 1) / 9 =
Sum_dec * 111…111 (n единиц)
Важное уточнение, последнюю величину можно вычислить сразу только на питоне (так как n слишком велико ~10^6, а в питоне есть длинку) и далее просто проссумировать все цифры. Для решения на с++ же, требуется реализовать простое умножение в столбик суммируя цифры в каждом десятке.
@algoses
🔥7❤2🙈1
Forwarded from Art of Code
Задача с собеса в Яндекс по C++
Напишите конструктор копирования для
Исходный код:
Решение: Класс
Foo(const Foo& other) :
a(other.a ? new A(*other.a) : nullptr),
b(other.b ? new B(*other.b) : nullptr) {} . Проверяем other.a и other.b на nullptr перед копированием.
Создаем новые объекты A и B через копирующие конструкторы (
Оператор присваивания: должен корректно обрабатывать самоприсваивание и освобождать старые ресурсы перед копированием новых.
Должен корректно обрабатывать самоприсваивание и освобождать старые ресурсы перед копированием новых.
Foo& operator=(const Foo& other) {
if (this != &other) { // Защита от самоприсваивания
delete a; // Освобождаем текущие ресурсы
delete b;
// Глубокое копирование
a = other.a ? new A(*other.a) : nullptr;
b = other.b ? new B(*other.b) : nullptr;
}
return *this;
}
Пояснение:
Проверка if (this != &other) исключает самоприсваивание (foo = foo).
Освобождаем текущие указатели a и b перед копированием новых значений.
Копируем объекты через new A(*other.a) (аналогично конструктору копирования).
class Foo {
public:
Foo(A* a, B* b): a(a), b(b) {}
~Foo() {
delete a;
delete b;
}
// Конструктор копирования
Foo(const Foo& other) :
a(other.a ? new A(*other.a) : nullptr),
b(other.b ? new B(*other.b) : nullptr) {}
// Оператор присваивания
Foo& operator=(const Foo& other) {
if (this != &other) {
delete a;
delete b;
a = other.a ? new A(*other.a) : nullptr;
b = other.b ? new B(*other.b) : nullptr;
}
return *this;
}
private:
A* a;
B* b;
};
@codeof_art
Напишите конструктор копирования для
Foo, учитывая, что класс Foo принимает a и b во владение. Для тех, кто справился с предыдущей задачей: напишите operator= для класса FooИсходный код:
class Foo {
public:
Foo(A* a, B* b): a(a), b(b) {}
~Foo() {
delete a;
delete b;
}
// TODO: copy_ctor
private:
A* a;
B* b;
};Решение:
Foo принимает владение сырыми указателями A* a и B* b. Необходимо выполнить глубокое копирование объектов A и B, чтобы избежать проблем с двойным удалением. Foo(const Foo& other) :
a(other.a ? new A(*other.a) : nullptr),
b(other.b ? new B(*other.b) : nullptr) {}
Создаем новые объекты A и B через копирующие конструкторы (
new A(*other.a)).Должен корректно обрабатывать самоприсваивание и освобождать старые ресурсы перед копированием новых.
Foo& operator=(const Foo& other) {
if (this != &other) { // Защита от самоприсваивания
delete a; // Освобождаем текущие ресурсы
delete b;
// Глубокое копирование
a = other.a ? new A(*other.a) : nullptr;
b = other.b ? new B(*other.b) : nullptr;
}
return *this;
}
Пояснение:
Проверка if (this != &other) исключает самоприсваивание (foo = foo).
Освобождаем текущие указатели a и b перед копированием новых значений.
Копируем объекты через new A(*other.a) (аналогично конструктору копирования).
public:
Foo(A* a, B* b): a(a), b(b) {}
~Foo() {
delete a;
delete b;
}
// Конструктор копирования
Foo(const Foo& other) :
a(other.a ? new A(*other.a) : nullptr),
b(other.b ? new B(*other.b) : nullptr) {}
// Оператор присваивания
Foo& operator=(const Foo& other) {
if (this != &other) {
delete a;
delete b;
a = other.a ? new A(*other.a) : nullptr;
b = other.b ? new B(*other.b) : nullptr;
}
return *this;
}
private:
A* a;
B* b;
};
@codeof_art
🔥5❤4
Задача с собеседования в ШАР Яндекса
Большинство кандидатов на собеседовании в Школу Аналитиков-Разработчиков просто ВАЛЯТСЯ на алгосах, которые яндекс принципиально ставит в начало собеседования, и уже после них шли теорвер и кейс по аналитике. Если кандидат не решает алгос, ему даже не давали шанса пройти дальше. Это очередной повод задуматься над тем, что алгосы все-таки надо заботать, а сделать это приятнее всего можно на наших курсах.
Даны два списка интервалов, когда пользователь A и пользователь B были онлайн. Нужно найти все интервалы, когда оба были онлайн одновременно.
Решение:
Легчайшая задача на два указателя
Поскольку интервалы уже отсортированы по началу, мы можем использовать два указателя и пройти списки одновременно, сравнивая текущие интервалы
def intersect_intervals(a, b):
i = j = 0
result = []
while i < len(a) and j < len(b):
a_start, a_end = a[i]
b_start, b_end = b[j]
start = max(a_start, b_start)
end = min(a_end, b_end)
if start < end:
result.append((start, end))
if a_end < b_end:
i += 1
else:
j += 1
return result
Асимптотика O(N)
@algoses
Большинство кандидатов на собеседовании в Школу Аналитиков-Разработчиков просто ВАЛЯТСЯ на алгосах, которые яндекс принципиально ставит в начало собеседования, и уже после них шли теорвер и кейс по аналитике. Если кандидат не решает алгос, ему даже не давали шанса пройти дальше. Это очередной повод задуматься над тем, что алгосы все-таки надо заботать, а сделать это приятнее всего можно на наших курсах.
Даны два списка интервалов, когда пользователь A и пользователь B были онлайн. Нужно найти все интервалы, когда оба были онлайн одновременно.
Решение:
Поскольку интервалы уже отсортированы по началу, мы можем использовать два указателя и пройти списки одновременно, сравнивая текущие интервалы
def intersect_intervals(a, b):
i = j = 0
result = []
while i < len(a) and j < len(b):
a_start, a_end = a[i]
b_start, b_end = b[j]
start = max(a_start, b_start)
end = min(a_end, b_end)
if start < end:
result.append((start, end))
if a_end < b_end:
i += 1
else:
j += 1
return result
@algoses
❤13😁4🤯1😢1🙈1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Поступашки открывают набор на курс по теории вероятностей и математической статистики для тех, кто поступает в Академию Аналитиков Авито!
Мечтаешь поступить в ААА? Или просто хочешь тащить собесы и стать крутым специалистом в DS, но не хватает фундамента? Тогда тебе к нам!
На курсе будет разобрана специфика задач, ВСЕ идеи и подходы, используемые составителями. А также тебя ждёт пробный экзамен и собеседование!
Как всегда лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор Владислав, который готовит десяток лет, все что может вам потребоваться для полной подготовки!
Цена самая доступная: 9000 р за курс.
Начинаем уже 7 июня! Первые материалы уже доступны!
После семинара доступна запись. Кураторы помогут заполнить анкету, помогут в абсолютно в любом вопросе, задаче. Вас ждет пробный экзамен, персональное собеседование! А также разведка по каждому экзамену, инсайды и персональные рекомендации. Все будет еще круче, чем на всех наших прошлых курсах (отзывы тут).
Программа и Подробности.
Для записи и вопросов: @menshe_treh
Мечтаешь поступить в ААА? Или просто хочешь тащить собесы и стать крутым специалистом в DS, но не хватает фундамента? Тогда тебе к нам!
На курсе будет разобрана специфика задач, ВСЕ идеи и подходы, используемые составителями. А также тебя ждёт пробный экзамен и собеседование!
Как всегда лекции со всей необходимой систематизированной теорией, семинары (на которых вы не просто сидите в чате, а имеете возможность отвечать, как на живом уроке), домашние задачи, разбор домашних задачек, куратор Владислав, который готовит десяток лет, все что может вам потребоваться для полной подготовки!
Цена самая доступная: 9000 р за курс.
Начинаем уже 7 июня! Первые материалы уже доступны!
После семинара доступна запись. Кураторы помогут заполнить анкету, помогут в абсолютно в любом вопросе, задаче. Вас ждет пробный экзамен, персональное собеседование! А также разведка по каждому экзамену, инсайды и персональные рекомендации. Все будет еще круче, чем на всех наших прошлых курсах (отзывы тут).
Программа и Подробности.
Для записи и вопросов: @menshe_treh
❤4😱1
Задача с собеседования на стажировку в Яндекс
Оригинальная задача, которая достаточно большое количество подходов к решению, тем не менее интервьювер ожидал чуть менее эффективное решение, по сравнению с самыми быстрми, но самое простое. Давайте разберем все способы.
Итак задача:
Дано n строк, сумма длин которых не превосходит 10^5, для каждой строки st[i] требуется найти позицию строки j, у которой длина наибольшего общего префикса максимальна возможной.
1 способ:
Наиболее лаконичный и даже подходящий под ограничения.
Отсортируем все строки (сохранив индексы изначальных позиций для каждой строки), получив просто лексикографический порядок, тогда для каждой строки одна из двух соседних будет соотвествовать нужной.
Итоговая асимптотика O(S log n), где S - сумма длин всех строк.
2 способ:
Воспользуемся структурой данных бор. Построим его и в каждой вершине будем сохранять два любых индекса строки (которые имеют такой же префикс, как путь от корня до данной вершины). Далее пройдемся по списку строк и для каждой строки будем спускаться по бору, тогда на каждой иттерации спуска в вершине будет храниться два индекса (один возможно совпадет с индексом текущей и на такой случай, второй будет как раз нужным). Если в какой-то момент на спуске будет вершина лишь с одним индексом, совпадающим с текущим, то остановимся.
Итоговая асимптотика O(S), где S - сумма длин всех строк
3 способ:
Пройдемся по каждой строке в наборе и параллельно будем поддерживать хеш каждого префикса и добавлять его в unordered_map (хеш мапу), и каждому хешу в мапе сопоставим два индекса (как в предыдщем решении). Затем пройдемся по каждой строке второй раз и поддержим хеш каждого префикса, соответственно найдем в мапе хеш префикса максимальной длины и получим ответ для каждой строки.
Итоговая асимптотика O(S), где S - сумма длин всех строк.
@algoses
Оригинальная задача, которая достаточно большое количество подходов к решению, тем не менее интервьювер ожидал чуть менее эффективное решение, по сравнению с самыми быстрми, но самое простое. Давайте разберем все способы.
Итак задача:
Дано n строк, сумма длин которых не превосходит 10^5, для каждой строки st[i] требуется найти позицию строки j, у которой длина наибольшего общего префикса максимальна возможной.
1 способ:
Наиболее лаконичный и даже подходящий под ограничения.
Отсортируем все строки (сохранив индексы изначальных позиций для каждой строки), получив просто лексикографический порядок, тогда для каждой строки одна из двух соседних будет соотвествовать нужной.
Итоговая асимптотика O(S log n), где S - сумма длин всех строк.
2 способ:
Воспользуемся структурой данных бор. Построим его и в каждой вершине будем сохранять два любых индекса строки (которые имеют такой же префикс, как путь от корня до данной вершины). Далее пройдемся по списку строк и для каждой строки будем спускаться по бору, тогда на каждой иттерации спуска в вершине будет храниться два индекса (один возможно совпадет с индексом текущей и на такой случай, второй будет как раз нужным). Если в какой-то момент на спуске будет вершина лишь с одним индексом, совпадающим с текущим, то остановимся.
Итоговая асимптотика O(S), где S - сумма длин всех строк
3 способ:
Пройдемся по каждой строке в наборе и параллельно будем поддерживать хеш каждого префикса и добавлять его в unordered_map (хеш мапу), и каждому хешу в мапе сопоставим два индекса (как в предыдщем решении). Затем пройдемся по каждой строке второй раз и поддержим хеш каждого префикса, соответственно найдем в мапе хеш префикса максимальной длины и получим ответ для каждой строки.
Итоговая асимптотика O(S), где S - сумма длин всех строк.
@algoses
❤7👍5
Задача с собеседования в ШАР Яндекса
Даны 2 вектора целых чисел одинаковой длины, заданные в сжатой форме списками пар вида (value, count)
Например, вектор [4, 4, 5] задается как [(4, 2), (5, 1)]
Необходимо посчитать скалярное произведение заданных векторов
Пример:
DotProduct([(1, 3)], [(1, 2), (10, 1)]) -> 12
Решение:
Пройдемся двумя указателями по обоим массивам за линию
Реализация может быть разной, но идея одна и та же - будем их "разворачивать" на лету, одновременно считая ответ
def DotProduct(vec1, vec2):
i = j = 0
count1 = count2 = 0
val1 = val2 = 0
result = 0
while i < len(vec1) and j < len(vec2):
if count1 == 0:
val1, count1 = vec1[i]
i += 1
if count2 == 0:
val2, count2 = vec2[j]
j += 1
k = min(count1, count2)
result += val1 * val2 * k
count1 -= k
count2 -= k
return result
Асимптотика O(N)
@algoses
Даны 2 вектора целых чисел одинаковой длины, заданные в сжатой форме списками пар вида (value, count)
Например, вектор [4, 4, 5] задается как [(4, 2), (5, 1)]
Необходимо посчитать скалярное произведение заданных векторов
Пример:
DotProduct([(1, 3)], [(1, 2), (10, 1)]) -> 12
Решение:
Реализация может быть разной, но идея одна и та же - будем их "разворачивать" на лету, одновременно считая ответ
def DotProduct(vec1, vec2):
i = j = 0
count1 = count2 = 0
val1 = val2 = 0
result = 0
while i < len(vec1) and j < len(vec2):
if count1 == 0:
val1, count1 = vec1[i]
i += 1
if count2 == 0:
val2, count2 = vec2[j]
j += 1
k = min(count1, count2)
result += val1 * val2 * k
count1 -= k
count2 -= k
return result
Асимптотика O(N)
@algoses
🤣6🔥5❤3❤🔥2
Forwarded from Art of Code
Задача с собеса в Ягуар
Задача: Напишите конструктор копирования для A. Для тех кто неуверенно (с подсказкой) справился с предыдущей задачей: напишите
Решение:
Конструктор копирования:A::A(const A& other)
: b(other.b ? other.b->clone() : nullptr),
c(other.c ? other.c->clone() : nullptr),
s(other.s ? new std::string(*other.s) : nullptr) {}
Оператор присваивания:A& A::operator=(const A& other) {
if (this != &other) { // Проверка на самоприсваивание
// Удаляем старые данные
delete b;
delete c;
delete s;
// Копируем новые данные
b = other.b ? other.b->clone() : nullptr;
c = other.c ? other.c->clone() : nullptr;
s = other.s ? new std::string(*other.s) : nullptr;
}
return *this;
}
Полный код:class A {
public:
A() : b(nullptr), c(nullptr), s(nullptr) {} // Конструктор по умолчанию
A(const A& other); // Конструктор копирования
A& operator=(const A& other); // Оператор присваивания
~A();
private:
Cloneable* b;
Cloneable* c;
std::string* s;
};
// Реализации
A::A(const A& other)
: b(other.b ? other.b->clone() : nullptr),
c(other.c ? other.c->clone() : nullptr),
s(other.s ? new std::string(*other.s) : nullptr) {}
A& A::operator=(const A& other) {
if (this != &other) {
delete b;
delete c;
delete s;
b = other.b ? other.b->clone() : nullptr;
c = other.c ? other.c->clone() : nullptr;
s = other.s ? new std::string(*other.s) : nullptr;
}
return *this;
}
A::~A() {
delete b;
delete c;
delete s;
}
@codeof_art
Задача: Напишите конструктор копирования для A. Для тех кто неуверенно (с подсказкой) справился с предыдущей задачей: напишите
operator= для класса A. чтобы проверить, что всё поняли.class Cloneable {
public:
virtual Cloneable* clone() const = 0; // Возвращает копию себя
virtual ~Cloneable() {}
};
class A {
public:
A(/* Какой должна быть сигнатура конструктора копирования? */);
~A();
// Добавить оператор присваивания
private:
Cloneable* b;
Cloneable* c;
std::string* s;
};
A::~A() {
delete b;
delete c;
delete s;
}Решение:
Конструктор копирования:
: b(other.b ? other.b->clone() : nullptr),
c(other.c ? other.c->clone() : nullptr),
s(other.s ? new std::string(*other.s) : nullptr) {}
Оператор присваивания:
if (this != &other) { // Проверка на самоприсваивание
// Удаляем старые данные
delete b;
delete c;
delete s;
// Копируем новые данные
b = other.b ? other.b->clone() : nullptr;
c = other.c ? other.c->clone() : nullptr;
s = other.s ? new std::string(*other.s) : nullptr;
}
return *this;
}
Полный код:
public:
A() : b(nullptr), c(nullptr), s(nullptr) {} // Конструктор по умолчанию
A(const A& other); // Конструктор копирования
A& operator=(const A& other); // Оператор присваивания
~A();
private:
Cloneable* b;
Cloneable* c;
std::string* s;
};
// Реализации
A::A(const A& other)
: b(other.b ? other.b->clone() : nullptr),
c(other.c ? other.c->clone() : nullptr),
s(other.s ? new std::string(*other.s) : nullptr) {}
A& A::operator=(const A& other) {
if (this != &other) {
delete b;
delete c;
delete s;
b = other.b ? other.b->clone() : nullptr;
c = other.c ? other.c->clone() : nullptr;
s = other.s ? new std::string(*other.s) : nullptr;
}
return *this;
}
A::~A() {
delete b;
delete c;
delete s;
}
@codeof_art
🥱14❤3🔥2😁1🤣1
Задача с собеседования в Яндекс
Дан массив чисел a₁, a₂, ..., aₙ.
Необходимо найти строго монотонный подотрезок (то есть строго убывающий или строго возрастающий) максимальной длины и вернуть пару индексов его начала и конца.
Решение:
Решение за линейное время и константную память (изменять входной массив нельзя).
В идеале: решить за один проход, отслеживая текущую монотонную последовательность, её направление и корректно сбрасывая при изменении направления и аккуратно обновляя максимум при переходе к следующему числу.
Также допустим подход в два прохода: отдельно ищем максимум среди возрастающих и убывающих отрезков. Но это менее оптимально, и большинство кандидатов ошибаются, пытаясь объединить оба направления в одном проходе.
def find_longest_monotonic_subarray(arr):
if not arr:
return (0, 0)
max_start = max_end = 0
cur_start = 0
direction = 0 # 1 — возрастаем, -1 — убываем, 0 — нет направления
for i in range(1, len(arr)):
if arr[i] > arr[i - 1]:
if direction == -1:
cur_start = i - 1
direction = 1
elif arr[i] < arr[i - 1]:
if direction == 1:
cur_start = i - 1
direction = -1
else:
direction = 0
cur_start = i
continue
if (i - cur_start) > (max_end - max_start):
max_start, max_end = cur_start, i
return (max_start, max_end)
@algoses
Дан массив чисел a₁, a₂, ..., aₙ.
Необходимо найти строго монотонный подотрезок (то есть строго убывающий или строго возрастающий) максимальной длины и вернуть пару индексов его начала и конца.
Решение:
В идеале: решить за один проход, отслеживая текущую монотонную последовательность, её направление и корректно сбрасывая при изменении направления и аккуратно обновляя максимум при переходе к следующему числу.
Также допустим подход в два прохода: отдельно ищем максимум среди возрастающих и убывающих отрезков. Но это менее оптимально, и большинство кандидатов ошибаются, пытаясь объединить оба направления в одном проходе.
def find_longest_monotonic_subarray(arr):
if not arr:
return (0, 0)
max_start = max_end = 0
cur_start = 0
direction = 0 # 1 — возрастаем, -1 — убываем, 0 — нет направления
for i in range(1, len(arr)):
if arr[i] > arr[i - 1]:
if direction == -1:
cur_start = i - 1
direction = 1
elif arr[i] < arr[i - 1]:
if direction == 1:
cur_start = i - 1
direction = -1
else:
direction = 0
cur_start = i
continue
if (i - cur_start) > (max_end - max_start):
max_start, max_end = cur_start, i
return (max_start, max_end)
@algoses
❤🔥6❤5🔥4🥱3💊3😁2🤣1
AAA.pdf
99.2 KB
Расписали для вас решения прогерской части отбора ААА, задачи специфичные на реализацию и тестирующей системы нет, так что проверяйте внимательно перед отправкой и не забывайте про систему антиплагиата. Всем удачного отбора!!!😎 А для подготовки к экзамену обязательно записывайтесь на наш курс.
@algoses
@algoses
🔥10🙈7💊5😁3❤🔥2❤1👏1
В нашем чате обсуждали один очень интересный алгоритм, который иногда может использоваться в проде.
Применение
Нахождение минимального пути от вершины s до вершины t в графе с неотрицательными рёбрами
Как это работает?
На самом деле это всё тот же алгоритм дейкстры, только теперь мы в куче сортируем вершины по следующему значению (g(v) + h(v), где g(v) - наилучшее расстояние до вершины v от s, h(v) - эвристика, некоторая функция, которая оценивает значение пути от вершины v до t).
Псевдокод
Как выбирать эвристику?
Сначала поговорим о корнер-кейсах алгоритма A*.
1) Eсли выбрать такую h, что ∀ v : h(v)=0, то у нас получится обычный алгоритм дейкстры и очевидно, что при такой эвристике алгоритм работает корректно.
2) Если как-то угадать идеальную эвристику (т. е. ∀ v : h(v) = dist(v, t)), то алгоритм будет работать корректно и более того, он пройдётся лишь по тем вершинам, что лежат на оптимальном пути (если их несколько, то алгоритм точно не будет перебирать заведомо худшие варианты).
Давайте попробуем определить критерий, по которому можно будет отбирать эвристики, назовём эвристику допустимой ∀ v : h(v) <= dist(v, t) (следствие h(t) = 0). (не стоит при выборе метрики отталкиваться исключительно от допустимых метрик, недопустимыми можно добиться большим процентном корректности и при этом ускорить работу алгоритма в разы). Добавим ещё более сильный критерий: эвристика является монотонной если∀(u, v) ∈ E (E - множество рёбер) : h(u) <= h(v) +dist(u, v). Далее можно доказать, что любая монотонная является допустимой. Теперь из этих двух критериев можно сформулировать теорему:
th. Если эвристика h является монотонной, то алгоритм A* найдёт точный оптимальный путь и при этом, каждая вершина будет посещена не более одного раза.
Эта теорема остаётся на упражнение читателю, ждём доказательства в комментариях!
Примеры
А теперь посмотрим примеры эвристик:
1) Нахождение гамильтоново пути, в этой задаче можно для некоторых случаев решать довольно быстро с помощью алгоритма A* (просто будем поддерживать посещённые вершины и последнюю в паре в куче) в качестве эвристики возьмём вес минимального остова на оставшихся вершинах, A* позволит в таком случае оптимизировать количество рассмотренных вариантов путей и соответственно сложность алгоритма.
2) Если граф представляет собой подмножество сетки (степень у каждой вершины <= 4) , то в качестве эвристики можно взять Манхэттенское расстояние: h(v) = |v.x−t.x|+|v.y −t.y| (положим граф на плоскость и возьмём координаты у каждой вершины при вычислении метрики).
3) Если в графе еще можно ходить по диагонали, то в качестве эвристики можно использовать h(v) = max{|v.x−t.x|,|v.y −t.y|}
4) Если у вас задача на плоскости и доступны любые направления, то подойдёт евклидово расстояние h(v) = sqrt((v.x - t.x)^2 + (v.y - t.y)^2)
Одну из задач на этот алгоритм вы можете сдать здесь. А так реализация этого алгоритма простая, всё заключается в правильном подборе эвристики.
@algoses
Применение
Нахождение минимального пути от вершины s до вершины t в графе с неотрицательными рёбрами
Как это работает?
На самом деле это всё тот же алгоритм дейкстры, только теперь мы в куче сортируем вершины по следующему значению (g(v) + h(v), где g(v) - наилучшее расстояние до вершины v от s, h(v) - эвристика, некоторая функция, которая оценивает значение пути от вершины v до t).
Псевдокод
q.push(start)
while (!q.empty()) {
v = q.top()
q.pop()
for u, cost : graph[v] {
func = dist[v] + cost + heuristic(u)
if (func < f[u]) {
if (u in q) {
// изменим значение функции у вершины u в куче
} else {
// добавим u в кучу
}
}
}
}
Как выбирать эвристику?
Сначала поговорим о корнер-кейсах алгоритма A*.
1) Eсли выбрать такую h, что ∀ v : h(v)=0, то у нас получится обычный алгоритм дейкстры и очевидно, что при такой эвристике алгоритм работает корректно.
2) Если как-то угадать идеальную эвристику (т. е. ∀ v : h(v) = dist(v, t)), то алгоритм будет работать корректно и более того, он пройдётся лишь по тем вершинам, что лежат на оптимальном пути (если их несколько, то алгоритм точно не будет перебирать заведомо худшие варианты).
Давайте попробуем определить критерий, по которому можно будет отбирать эвристики, назовём эвристику допустимой ∀ v : h(v) <= dist(v, t) (следствие h(t) = 0). (не стоит при выборе метрики отталкиваться исключительно от допустимых метрик, недопустимыми можно добиться большим процентном корректности и при этом ускорить работу алгоритма в разы). Добавим ещё более сильный критерий: эвристика является монотонной если∀(u, v) ∈ E (E - множество рёбер) : h(u) <= h(v) +dist(u, v). Далее можно доказать, что любая монотонная является допустимой. Теперь из этих двух критериев можно сформулировать теорему:
th. Если эвристика h является монотонной, то алгоритм A* найдёт точный оптимальный путь и при этом, каждая вершина будет посещена не более одного раза.
Эта теорема остаётся на упражнение читателю, ждём доказательства в комментариях!
Примеры
А теперь посмотрим примеры эвристик:
1) Нахождение гамильтоново пути, в этой задаче можно для некоторых случаев решать довольно быстро с помощью алгоритма A* (просто будем поддерживать посещённые вершины и последнюю в паре в куче) в качестве эвристики возьмём вес минимального остова на оставшихся вершинах, A* позволит в таком случае оптимизировать количество рассмотренных вариантов путей и соответственно сложность алгоритма.
2) Если граф представляет собой подмножество сетки (степень у каждой вершины <= 4) , то в качестве эвристики можно взять Манхэттенское расстояние: h(v) = |v.x−t.x|+|v.y −t.y| (положим граф на плоскость и возьмём координаты у каждой вершины при вычислении метрики).
3) Если в графе еще можно ходить по диагонали, то в качестве эвристики можно использовать h(v) = max{|v.x−t.x|,|v.y −t.y|}
4) Если у вас задача на плоскости и доступны любые направления, то подойдёт евклидово расстояние h(v) = sqrt((v.x - t.x)^2 + (v.y - t.y)^2)
Одну из задач на этот алгоритм вы можете сдать здесь. А так реализация этого алгоритма простая, всё заключается в правильном подборе эвристики.
@algoses
🔥7❤3🤣2👍1😁1🙉1
Forwarded from Art of Code
Задача с собеса в Yandex
Напишите код, который вернёт медиану из трёх чисел. Уточните определение медианы, если человек не знает.
Решение:
#include <algorithm>
int median3(int v1, int v2, int v3) {
int arr[] = {v1, v2, v3};
std::sort(arr, arr + 3);
return arr[1];
}
@codeof_art
Напишите код, который вернёт медиану из трёх чисел. Уточните определение медианы, если человек не знает.
//Интерфейс
int median3(int v1, int v2, int v3)
{
//реализация
}
assert(3 == median(2,5,3))
assert(2 == median3(2,2,1))
Решение:
int median3(int v1, int v2, int v3) {
int arr[] = {v1, v2, v3};
std::sort(arr, arr + 3);
return arr[1];
}
@codeof_art
🗿66🤣35👍2😁2🙉2❤1🔥1
Задача с собеседования в Яндекс
Дана строка, состоящая из букв 'X', 'Y' и 'O'.
Нужно найти кратчайшее расстояние между буквами 'X' и 'Y'.
Если хотя бы одна из букв отсутствует — вывести 0. Кстати задачу обсуждали ранее в нашем чате крутых алгоритмистов😎😎
Решение:
Решение за один проход по строке: запоминаем последние позиции X и Y, на каждой итерации обновляем ответ
def shortest_distance(s):
last_x = last_y = -1
min_dist = float('inf')
for i, ch in enumerate(s):
if ch == 'X':
last_x = i
if last_y != -1:
min_dist = min(min_dist, abs(last_x - last_y))
elif ch == 'Y':
last_y = i
if last_x != -1:
min_dist = min(min_dist, abs(last_x - last_y))
return min_dist if min_dist != float('inf') else 0
Асимптотика O(N)
@algoses
Дана строка, состоящая из букв 'X', 'Y' и 'O'.
Нужно найти кратчайшее расстояние между буквами 'X' и 'Y'.
Если хотя бы одна из букв отсутствует — вывести 0. Кстати задачу обсуждали ранее в нашем чате крутых алгоритмистов😎😎
Решение:
def shortest_distance(s):
last_x = last_y = -1
min_dist = float('inf')
for i, ch in enumerate(s):
if ch == 'X':
last_x = i
if last_y != -1:
min_dist = min(min_dist, abs(last_x - last_y))
elif ch == 'Y':
last_y = i
if last_x != -1:
min_dist = min(min_dist, abs(last_x - last_y))
return min_dist if min_dist != float('inf') else 0
Асимптотика O(N)
@algoses
👍13❤3🥱2😁1
Задача с собеседования в лабу СБЕРа
Даны два мультимножества, c одним из них вы можете проводить следующие операции:
1. Выбрать элемент и заменить его на x * 2.
2. Выбрать элемент и заменить его на x // 2 (округление вниз).
У вас есть неограниченное количество операций, ваша задача определить возможно ли приравнять второе мультимножество к первому.
Решение:
Обозначим мультимножества как A и B.
1. Для начала заметим выгодное разбиение A на классы эквивалентности x ~ y <=> \exist k >= 0: min(x, y) * 2^k = max(x, y) (иначе говоря если больший элемент может быть получен путём умножения меньшего на степень двойку (т е проводения некоторого количества операций первого типа), то мы будем эти два элемента считать за эквивалентные). То есть нам достаточно проверить множества на равенства меньших элементов из каждого класса (просто каждый элемент множества A будем делить до того момента, пока он делится). Таким образом мы свели задачу к использованию лишь второй операции.
2. Заметим что каждый элемент из множества b порождает с помощью операции 2 ряд различных классов эквивалентности (можно кстати оценить количество этих классов как O(log(x))), тогда нам остаётся лишь распределить выгодно эти классы по элементам из A. Воспользуемся жадным подходом отсортируем множество B, и будем идти от меньшего к большему по элементам и последовательно для каждого элемента перебирать эти классы (то есть просто делить на 2 с округлением и проверять наличие текущего элемента класса в множестве А), в случае если мы нашли элемент совпадающий с элементом из A просто удалим его и закончим перебор классов.
Пример кода (здесь даны множества уже в отсортированном порядке) уже в нашемчате .
Эту задачу нам скинул подписчик в нашем чатике и мы там же оперативно обсудили, присоединяйся в наше комьюнити алгоритмистов!
@algoses
Даны два мультимножества, c одним из них вы можете проводить следующие операции:
1. Выбрать элемент и заменить его на x * 2.
2. Выбрать элемент и заменить его на x // 2 (округление вниз).
У вас есть неограниченное количество операций, ваша задача определить возможно ли приравнять второе мультимножество к первому.
Решение:
Обозначим мультимножества как A и B.
1. Для начала заметим выгодное разбиение A на классы эквивалентности x ~ y <=> \exist k >= 0: min(x, y) * 2^k = max(x, y) (иначе говоря если больший элемент может быть получен путём умножения меньшего на степень двойку (т е проводения некоторого количества операций первого типа), то мы будем эти два элемента считать за эквивалентные). То есть нам достаточно проверить множества на равенства меньших элементов из каждого класса (просто каждый элемент множества A будем делить до того момента, пока он делится). Таким образом мы свели задачу к использованию лишь второй операции.
2. Заметим что каждый элемент из множества b порождает с помощью операции 2 ряд различных классов эквивалентности (можно кстати оценить количество этих классов как O(log(x))), тогда нам остаётся лишь распределить выгодно эти классы по элементам из A. Воспользуемся жадным подходом отсортируем множество B, и будем идти от меньшего к большему по элементам и последовательно для каждого элемента перебирать эти классы (то есть просто делить на 2 с округлением и проверять наличие текущего элемента класса в множестве А), в случае если мы нашли элемент совпадающий с элементом из A просто удалим его и закончим перебор классов.
Пример кода (здесь даны множества уже в отсортированном порядке) уже в нашем
Эту задачу нам скинул подписчик в нашем чатике и мы там же оперативно обсудили, присоединяйся в наше комьюнити алгоритмистов!
@algoses
❤6🤔2❤🔥1🔥1💋1
Задача с собеседования в Яндекс
Написать метод, который заменит все пробелы в строке на '%20'
На вход подается строка с зарезервированными под расширение символами (гарантируется, что resize() до разумных размеров не будет выделять память)
Ограничения: O(1) по памяти, O(N) по времени, менять исходную строку можно
Решение:
Два прохода по строке: на первом считаем количество пробелов, и таким образом итоговую длину, на втором идем с конца и копируем символы, кодируя в процессе пробелы
def url_encode(char_list, true_length):
space_count = 0
for i in range(true_length):
if char_list[i] == ' ':
space_count += 1
index = true_length + space_count * 2
i = true_length - 1
j = index - 1
if len(char_list) < index:
char_list.extend([''] * (index - len(char_list)))
while i >= 0:
if char_list[i] == ' ':
char_list[j] = '0'
char_list[j - 1] = '2'
char_list[j - 2] = '%'
j -= 3
else:
char_list[j] = char_list[i]
j -= 1
i -= 1
return ''.join(char_list[:index])
@algoses
Написать метод, который заменит все пробелы в строке на '%20'
На вход подается строка с зарезервированными под расширение символами (гарантируется, что resize() до разумных размеров не будет выделять память)
Ограничения: O(1) по памяти, O(N) по времени, менять исходную строку можно
Решение:
def url_encode(char_list, true_length):
space_count = 0
for i in range(true_length):
if char_list[i] == ' ':
space_count += 1
index = true_length + space_count * 2
i = true_length - 1
j = index - 1
if len(char_list) < index:
char_list.extend([''] * (index - len(char_list)))
while i >= 0:
if char_list[i] == ' ':
char_list[j] = '0'
char_list[j - 1] = '2'
char_list[j - 2] = '%'
j -= 3
else:
char_list[j] = char_list[i]
j -= 1
i -= 1
return ''.join(char_list[:index])
@algoses
❤8🔥3❤🔥1🤔1
Свершилось! Поступашки открывают набор на новую линейку карьерных курсов 🎉
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
➡️ алгоритмы старт
➡️ аналитика старт
➡️ машинное обучение старт
➡️ бэкенд разработка старт
Все курсы стартует 13.07. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
📊 Цена 15'000р ! Хочешь купить несколько курсов сразу? Дадим хорошую скидку!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):
Все курсы стартует 13.07. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.
Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!
А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!
Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1😁1🕊1🤨1🤓1🙈1💊1
Задача с собеседования в Яндекс
Дан список неотрицательных целых чисел, повторяющихся элементов в списке нет. Нужно преобразовать его в строку, сворачивая соседние по числовому ряду числа в диапазоны
Пример:
[1,4,5,2,3,9,8,11,0] => "0-5,8-9,11"
НАШ ЧАТ
Решение:
Сортировка плюс один проход. По времени за O(nlogn)
def compress_ranges(nums):
if not nums:
return ""
nums.sort()
result = []
start = end = nums[0]
for num in nums[1:]:
if num == end + 1:
end = num
else:
if start == end:
result.append(str(start))
else:
result.append(f"{start}-{end}")
start = end = num
if start == end:
result.append(str(start))
else:
result.append(f"{start}-{end}")
return ",".join(result)
@algoses
Дан список неотрицательных целых чисел, повторяющихся элементов в списке нет. Нужно преобразовать его в строку, сворачивая соседние по числовому ряду числа в диапазоны
Пример:
[1,4,5,2,3,9,8,11,0] => "0-5,8-9,11"
НАШ ЧАТ
Решение:
def compress_ranges(nums):
if not nums:
return ""
nums.sort()
result = []
start = end = nums[0]
for num in nums[1:]:
if num == end + 1:
end = num
else:
if start == end:
result.append(str(start))
else:
result.append(f"{start}-{end}")
start = end = num
if start == end:
result.append(str(start))
else:
result.append(f"{start}-{end}")
return ",".join(result)
@algoses
❤9
Разбор_ААА__программирование_.pdf
169.2 KB
Вот и разбор ААА алгосов! Для подготовки к собесам советую присмотреться к нашему курсу по алгоритмам.
@algoses
@algoses
🔥9❤1
Задача с собеседования в Яндекс
Реализовать функцию fuzzypussy search как в редакторе sublime text 3.
Для незнакомых с редактором - по факту требуется проверить, является ли первая строка подпоследовательностью второй
fuzzysearch('car', 'cartwheel') -> true
наш чат алгоритмистов
Решение:
Один проход по символам строки
def fuzzysearch(needle, haystack):
if not needle:
return True
if not haystack:
return False
i = 0 # индекс в needle
for char in haystack:
if char == needle[i]:
i += 1
if i == len(needle):
return True
return False
Асимптотика O(N)
@algoses
Реализовать функцию fuzzy
Для незнакомых с редактором - по факту требуется проверить, является ли первая строка подпоследовательностью второй
fuzzysearch('car', 'cartwheel') -> true
наш чат алгоритмистов
Решение:
def fuzzysearch(needle, haystack):
if not needle:
return True
if not haystack:
return False
i = 0 # индекс в needle
for char in haystack:
if char == needle[i]:
i += 1
if i == len(needle):
return True
return False
Асимптотика O(N)
@algoses
❤20🔥6😁5
Задача с собеседования в Яндекс
Дана строка из десятичных цифр (длинное число, младшие разряды расположены по младшему индексу). Написать код, который умножит это число на число 1 <= n <= 9.
Ограничения по памяти: О(1) доп памяти, т.е. надо использовать исходную строку (считаем, что возможное увеличение длины на 1 разряд не приведет к реаллокации)
наш чат алгоритмистов
Решение:
Пройдемся по строке с разрядами и столбиком умножим число на n. Поддерживаем остаток и считаем так до конца
def multiply_digit_inplace(num_str, n):
if not (1 <= n <= 9):
raise ValueError("n должен быть от 1 до 9")
num = list(num_str) # строка как список символов (можно считать, что это изменяемый массив)
carry = 0
for i in range(len(num)):
digit = int(num[i])
prod = digit * n + carry
num[i] = str(prod % 10)
carry = prod // 10
if carry:
num.append(str(carry))
return ''.join(num)
Асимптотика O(N)
@algoses
Дана строка из десятичных цифр (длинное число, младшие разряды расположены по младшему индексу). Написать код, который умножит это число на число 1 <= n <= 9.
Ограничения по памяти: О(1) доп памяти, т.е. надо использовать исходную строку (считаем, что возможное увеличение длины на 1 разряд не приведет к реаллокации)
наш чат алгоритмистов
Решение:
def multiply_digit_inplace(num_str, n):
if not (1 <= n <= 9):
raise ValueError("n должен быть от 1 до 9")
num = list(num_str) # строка как список символов (можно считать, что это изменяемый массив)
carry = 0
for i in range(len(num)):
digit = int(num[i])
prod = digit * n + carry
num[i] = str(prod % 10)
carry = prod // 10
if carry:
num.append(str(carry))
return ''.join(num)
Асимптотика O(N)
@algoses
❤5😁5
Задача с собеседования в Яндекс
На входе дана непустая строка. Требуется вяснить, можно ли удалить из нее ровно один символ так, чтобы получился палиндром.
Требуется решение за линейное время с константой дополнительной памяти.
наш чат алгоритмистов
Решение:
Несложно заметить следующее
Если строка уже является палиндромом, то ответ всегда положительный (достаточно удалить центральный или один из центральных символов)
В противном случае, если начать проверку строки на палиндромность с левого и правого концов - можно найти первое несовпадение abcX....Ycba. Можно заметить, что в случае положительного ответа на задачу один из символов X или Y в данном несовпадении должен быть удален и что после этого палиндромом должна быть строка .....Y или X.....
Таким образом, решение задачи сводится к поиску такого несовпадения и проверки двух случаев
def can_be_palindrome_by_removing_one_char(s):
def is_palindrome_range(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
left += 1
right -= 1
if left >= right:
return True # строка уже палиндром или можно удалить любой символ
# Проверяем два варианта: пропустить символ слева или справа
return (is_palindrome_range(left + 1, right) or
is_palindrome_range(left, right - 1))
@algoses
На входе дана непустая строка. Требуется вяснить, можно ли удалить из нее ровно один символ так, чтобы получился палиндром.
Требуется решение за линейное время с константой дополнительной памяти.
наш чат алгоритмистов
Решение:
Если строка уже является палиндромом, то ответ всегда положительный (достаточно удалить центральный или один из центральных символов)
В противном случае, если начать проверку строки на палиндромность с левого и правого концов - можно найти первое несовпадение abcX....Ycba. Можно заметить, что в случае положительного ответа на задачу один из символов X или Y в данном несовпадении должен быть удален и что после этого палиндромом должна быть строка .....Y или X.....
Таким образом, решение задачи сводится к поиску такого несовпадения и проверки двух случаев
def can_be_palindrome_by_removing_one_char(s):
def is_palindrome_range(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
left += 1
right -= 1
if left >= right:
return True # строка уже палиндром или можно удалить любой символ
# Проверяем два варианта: пропустить символ слева или справа
return (is_palindrome_range(left + 1, right) or
is_palindrome_range(left, right - 1))
@algoses
🔥15❤10
Задача с собеседования в Яндекс
Дан вектор, надо удалить из него нули, сохранив порядок остальных элементов. Интересует как с использованием стандартных средств, так и без них.
наш чат алгоритмистов
Решение:
Линейно пройдемся по элементам массива, поддерживая указатель на записываемый элемент. Затем удалим лишние индексы
def remove_zeros(arr):
write = 0
for read in range(len(arr)):
if arr[read] != 0:
arr[write] = arr[read]
write += 1
# обрезаем хвост (если надо)
del arr[write:]
Асимптотика O(N)
@algoses
Дан вектор, надо удалить из него нули, сохранив порядок остальных элементов. Интересует как с использованием стандартных средств, так и без них.
наш чат алгоритмистов
Решение:
def remove_zeros(arr):
write = 0
for read in range(len(arr)):
if arr[read] != 0:
arr[write] = arr[read]
write += 1
# обрезаем хвост (если надо)
del arr[write:]
Асимптотика O(N)
@algoses
😁21❤6