Алгоритмы - Собеседования, Олимпиады, ШАД – Telegram
Алгоритмы - Собеседования, Олимпиады, ШАД
11.4K subscribers
35 photos
7 videos
10 files
154 links
Номер заявления регистрацию в РКН: № 5731053751

Чат: @algoses_chat

По всем вопросам: @vice22821
Download Telegram
Задача с собеседования в Яндекс

Дан массив prices, где prices[i] — цена акции в день i. Нужно выбрать один день для покупки и позже другой день для продажи так, чтобы прибыль была максимальна. Если прибыли получить нельзя — вернуть 0.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение:

Проходим массив один раз, поддерживая:
min_price — минимальную цену, встреченную слева (лучшая покупка до текущего дня);
best — максимальную прибыль на данный момент.
На каждом шаге обновляем best = max(best, prices[i] - min_price) и затем min_price = min(min_price, prices[i]).
Это даёт O(n) по времени и O(1) по памяти.


Код:

#include <bits/stdc++.h>
using namespace std;

int maxProfit(const vector<int>& prices) {
int min_price = INT_MAX;
int best = 0;
for (int p : prices) {
if (p > min_price) {
best = max(best, p - min_price);
}
min_price = min(min_price, p);
}
return best;
}


@algoses
😁182💊2
Задача с собеседования в Amazon

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

Пример:
Input: s = "aab"
Output: [["a","a","b"], ["aa","b"]]

|s| <= 16

Наш чат алгоритмистов

Решение:

Самое простое решение
Используем рекурсивный возврат с откатом:
1. На каждом шаге пробуем все возможные подстроки, начиная с текущей позиции
2. Если подстрока является палиндромом — добавляем её в текущий путь и рекурсивно продолжаем с оставшейся частью строки
3. Когда достигаем конца строки — сохраняем текущее разбиение
4. Откатываемся и пробуем другие варианты

Это даёт O(n × 2^n) по времени (2^(n-1) возможных разбиений, для каждого O(n) на проверку) и O(n) по памяти для стека рекурсии.

def partition(s: str) -> List[List[str]]:
def is_palindrome(string: str) -> bool:
return string == string[::-1]

def backtrack(start: int, path: List[str]) -> None:
if start == len(s):
result.append(path[:])
return

for end in range(start + 1, len(s) + 1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop()

result = []
backtrack(0, [])
return result

Оптимизация:
Можно предварительно вычислить все палиндромы с помощью DP за O(n²), чтобы потом проверять их за O(1). Но для |s| <= 16 рекурсии достаточно


@algoses
🔥62🤔1
Задача с собеседования в Amazon

Реализовать структуру данных MapSum, которая поддерживает две операции:
- insert(key, val) — вставить пару ключ-значение (или обновить значение, если ключ существует), key - строка, val - целое число
- sum(prefix) — вернуть сумму всех значений, ключи которых начинаются с заданного префикса

Пример:
mapSum.insert("apple", 3)
mapSum.sum("ap") // return 3
mapSum.insert("app", 2)
mapSum.sum("ap") // return 5 (apple + app = 3 + 2)


Работать должно линейно по времени

Наш чат алгоритмистов

Решение:

Будем использовать бор - префиксное дерево, где каждый узел хранит сумму всех значений с данным префиксом:
1. При вставке ключа вычисляем дельту (разницу между новым и старым значением)
2. Проходим по дереву вдоль символов ключа, создавая узлы при необходимости
3. В каждом узле увеличиваем значение на дельту
4. При запросе суммы просто идём по дереву до конца префикса и возвращаем значение узла

Дельта нужна для корректной обработки обновлений: если
apple было 3, а стало 7, то во все узлы пути добавляем +4.

Это даёт O(k) по времени для обеих операций (где k — длина ключа/префикса) и O(n × k) по памяти (где n — количество ключей).

class TrieNode:
def init(self):
self.children = {}
self.value = 0

class MapSum:
def init(self):
self.root = TrieNode()
self.map = {} # Храним текущие значения для обработки обновлений

def insert(self, key: str, val: int) -> None:
delta = val - self.map.get(key, 0)
self.map[key] = val

node = self.root
for char in key:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.value += delta

def sum(self, prefix: str) -> int:
node = self.root
for char in prefix:
if char not in node.children:
return 0
node = node.children[char]
return node.value

Можно использовать просто словарь и при каждом sum() перебирать все ключи с помощью startswith(). Это даст O(1) для insert и O(n) для sum, что проще в реализации, но менее эффективно при частых запросах сумм.

@algoses
9🗿7
Стартовал «Технокубок» 2025/26

VK, МФТИ и МГТУ им. Н. Э. Баумана открыли регистрацию на олимпиаду по программированию для школьников 8–11 классов. Победители могут поступить в вузы без экзаменов или получить 100 баллов за ЕГЭ по информатике — для этого участникам предстоит пройти три этапа:

➡️ Два независимых отборочных онлайн-раунда — они 16 ноября и 7 декабря на платформе All Cups. Будет засчитан лучший результат из двух.
➡️ Очный отбор 8 февраля на площадках вузов-партнеров. 
➡️ Финал пройдет 13-15 марта в Москве.

Участникам предстоит решать задачи по программированию от партнеров олимпиады и сервисов VK на различных языках — C++, Python, Java, C#, Kotlin и других.

Формат остался прежним, код писать придется самому 😎. На платформе VK Education есть бесплатная программа для подготовки к таким соревнованиям — обучение и тренировки в решении задач на курсе «Старт в олимпиадном программировании» бесплатные.

@algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
5
Задача с собеседования в МТС

Условие задачи
Вы начинаете в точке (0, 0). Доступны 4 типа перемещений:
U (x, y) -> (x, y+1)
R (x, y) -> (x+1, y)
D (x, y) -> (x, y-1)
L (x, y) -> (x-1, y)
Нельзя использовать все 4 типа перемещений. Можно задействовать не более 3 различных способов (каждый — сколько угодно раз).
Даны n точек с целочисленными координатами. Определите, можно ли посетить все точки (в любом порядке), соблюдая ограничение на типы перемещения.

Чат алгоритмистов

Банк собесов по алгоритмам

Решение
Чтобы обойти ограничение, необходимо полностью исключить один из типов. Это означает, что все точки должны лежать в одной из полуплоскостей:
1. Без D (вниз): все точки с y ≥ 0 (верхняя полуплоскость)
2. Без U (вверх): все точки с y ≤ 0` (нижняя полуплоскость)
3. Без L (влево): все точки с x ≥ 0 (правая полуплоскость)
4. Без R (вправо): все точки с x ≤ 0 (левая полуплоскость)
Если выполняется хотя бы одно условие, ответ yes. Иначе - no.

n = int(input())
no_D = True
no_U = True
no_L = True
no_R = True
for _ in range(n):
x, y = map(int, input().split())
if y < 0:
no_D = False
if y > 0:
no_U = False
if x < 0:
no_L = False
if x > 0:
no_R = False
if no_D or no_U or no_L or no_R:
print("yes")
else:
print("no")


@algoses
🗿357😁4
Задача с собеседования Яндекс

Задача 
Дана последовательность a и последовательность a'. Вам требуется найти такие l, r, что отсортировав подмассив a[l:r+1], можно получить массив a'. Если ответов несколько, выберите отрезок наибольшей длины. По условию такая операция всегда существует.

Чат алгоритмистов

Решение 
Найдем первое отличающееся вхождение, позицию i: a[i]!= a'[i](то есть самое левое) и найдем последнее (самое правое). Далее расширим эти границы: до тех пор, пока левее от левой границы в приведенном массиве a стоит меньше или равный a'[l-1]<= a'[l], будем двигать его влево. Аналогично и с правым указателем, расширим его вправо.

Код
l,r=-1,-1
for i in range(n):
  if a[i]!=aa[i]:
   r=i
   if l==-1:
    l=i
while l>0 and aa[l-1]<=aa[l]:
  l-=1
while r<n-1 and aa[r+1]>=aa[r]:
  r+=1
print(l+1,r+1)


@algoses
14🔥1
Магистратура — это 2 года жизни и серьезные вложения. Как не ошибиться с выбором?

Приходите на день открытых дверей ИТ-магистратуры Центрального университета — разберем все важные вопросы, которые помогут принять правильное решение.

О чем будем говорить:
→ Как создаются программы магистратуры в ЦУ, что такое продуктовый подход в высшем образовании и как это делает выпускников реально востребованными на рынке
→ Как университет помогает студентам строить карьеру: от менторства до трудоустройства в топовые компании
→ Какие направления есть в ЦУ и как выбрать то, что приведет к вашим карьерным целям
→ Реальные истории студентов: как они поступали, учились и куда пошли работать

Спикеры — практики с опытом в Google, Яндексе, Т-Банке и Visa, которые сейчас отвечают за образовательный опыт студентов ЦУ.

Когда:
Онлайн 13 ноября с 19:30 до 21:00 (трансляции в VK и YouTube).
Очно 18 ноября с 19:30 до 21:00 (в Москве с экскурсией по кампусу ЦУ).

Регистрируйся по ссылке!

Реклама. АНО ВО "Центральный университет", ИНН 7743418023, erid: 2Ranynxo6A5
💊72
🔥Прими участие в Хакатоне от ИТ-холдинга Т1 в Москве и поборись за призовой фонд 1 200 000 рублей!

Когда: 25–28 ноября
Формат: онлайн + финал на площадке

Участвуй, если ты:
🔹обучаешься на технической или ИТ-специальности
🔹развиваешься в направлении разработки, системной администрации, AI/ML или DevOps
🔹сможешь быть в Москве 28 ноября.

Выбери свой кейс:

✴️VibeCode Jam: собеседование будущего. Создай ИИ-платформу для прохождения технических собеседований с виртуальным интервьюером.

✴️Self-Deploy: CI/CD без DevOps. Автоматизируй генерацию CI/CD пайплайнов по анализу структуры Git-репозитория.


Почему стоит участвовать:
🔘Кейс в портфолио и полезная обратная связь от менторов Т1
🔘Шанс проявить себя, чтобы начать карьеру в одной из крупнейших ИТ-компаний
🔘Реальный опыт командной работы
🔘Мерч и атмосфера сильного комьюнити — в Т1 более 5 000 джунов из 580+ вузов России и Беларуси.

Регистрация открыта!
➡️ Успей до 23 ноября по ссылке.

Реклама.
О рекламодателе.
Please open Telegram to view this post
VIEW IN TELEGRAM
3
Задача с собеса в Авито

Условие задачи
Дано бинарное поисковое дерево (BST) и число k. Нужно вернуть значение k-го по величине элемента в этом дереве (нумерация с 1).
для любой вершины: все значения в левом поддереве меньше её значения; все значения в правом поддереве больше её значения.

Решение
Очень важное свойство BST: если обойти дерево в порядке
лево -> корень -> право (симметричный / inorder обход),
то значения вершин будут посещаться в отсортированном по возрастанию порядке.

Значит, k-й посещённый элемент при таком обходе — это и есть k-й по величине.
Делаем итеративный inorder-обход через стек:
1. Идём по указателю node максимально влево, по пути кладём все вершины в стек.
2. Когда упёрлись в None, достаём вершину из стека — это следующий по возрастанию элемент.
3. Уменьшаем k. Если k стало 0 — возвращаем значение этой вершины.
4. Переходим в правого ребёнка и повторяем.
Так мы не храним все элементы, а только путь в стеке.


Сложность:
по времени: O(h + k), где h — высота дерева (в худшем O(n), для сбалансированного O(log n)), по памяти: O(h) на стек

Код:

class Solution:
def kthSmallest(self, root: Optional['TreeNode'], k: int) -> int:
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right


@algoses
🔥113🗿1
Поступашки продолжают набор на новую линейку карьерных курсов 🎉

Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК? Узнал себя? Тогда записывайся у администратора на любой из курсов (если андроид - смотрим через яндекс браузер):

➡️ SQL и базы данных
➡️ анализ временных рядов
➡️ обучение с подкреплением

Все курсы стартуют 29.11. Курсы заточены на практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. Ничего нудного и скучного! Изучаем только то, что тебе реально понадобится и залетаем на первую работу! Хочешь подробностей? На нашем сайте можно найти программу и отзывы на каждый курс.

Помимо этого на курсах тебя ждут:
- пет проекты и мини проекты, которые пойдут в портфолио;
- разбор реальных тестовых заданий бигтехов;
- разбор актуального контеста на стажировку в Яндекс и Тинькофф;
- банк реальных технических вопрос с собесов;
- разбор всех задач с алгособесов Яндекса!

А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании!

📊 Цена 10'000р 6'990р! Хочешь купить несколько курсов сразу? Дадим хорошую скидку!

Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено
Please open Telegram to view this post
VIEW IN TELEGRAM
😁41
Разбор на стажировку Яндекса

Финальные 6 часов скидок на наши курсы подходят к концу. В честь этого выкладываем разбор актуального контеста в Яндекс:
Бэкенд
Аналитика
ML & DS

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

@postypashki_old
😁32🔥1🙉1
Задача с собеседования в Яндекс

Дан отсортированный в порядке возрастания массив nums, состоящий из уникальных целых чисел.
Известно, что диапазон [a, b] представляет собой множество всех целых чисел от a до b включительно.

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

Пример:
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]

Чат алгоритмистов

Решение
Проходим внешним циклом по всем элементам массива.
start - начало текущего диапазона. С помощью внутреннего цикла ищем окончание диапазона (проверяем наличие следующего эл-та и то, что числа идут подряд, если оба условия верны: обновляем i).
Если начало диапазона не равняется текущему значению nums[i]: выводим (строковый) диапазон, состоящий из более чем одного числа. Иначе: диапазон состоит из одного числа. Переходим к следующему эл-ту (за пределами выведенного диапазона).

Сложность
O(n) - по времени
O(n) - по памяти


Код

def summaryRanges(self, nums: List[int]) -> List[str]:
result = []
i = 0

while i < len(nums):
start = nums[i]
while i < len(nums) - 1 and nums[i] + 1 == nums[i + 1]:
i+= 1

if start != nums[i]:
result.append(str(start) + "->" + str(nums[i]))
else:
result.append(str(nums[i]))

i += 1

return result


@algoses
🔥4🥱42
Состоялся первый студенческий хакатон для мессенджера МАХ — участники привезли на очный финал в Москву больше 50 сервисов, и жюри выбрало девять лучших. В треке «Цифровизация» выиграла команда SUPERVIBECODING с сервисом «Цифровой кампус», в социальном треке — Smolensk Dynamics, разработавшая бота для анализа состава продуктов питания, а в «Эффективности» сильнейшими стали ребята из Explain с AI-календарём.

Хакатон получился масштабным: заявки отправили более 2,7 тысяч студентов, до финала дошли 56 команд, из которых были выбраны победители. В VK Education отмечают, что участники продемонстрировали отличное понимание реальных потребностей пользователей и вузов и создали актуальные и востребованные мини-приложения и чат-боты для мессенджера МАХ.

@algoses
🤣87💊7🤨63🤯2
Задача с собеседования в Яндекс

Дан массив строк strs. Найдите анаграммы и сгруппируйте их вместе.
Группы анаграмм можно вывести в любом порядке.

Пример:
Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Чат алгоритмистов

Решение
Идея: хэш-таблица, где ключ - кортеж из 26 эл-ов (каждое число - количество вхождений определённой буквы в слово), а значение - список слов, имеющих одинаковую частоту букв (анаграммы).
Проходим по каждому слову в массиве strs и создаём массив из 26 нулей (кол-во букв алфавита). Для каждого символа в слове вычисляем его индекс (соответствует позиции буквы в алфавите) и увеличиваем счётчик.
Далее преобразовываем список в кортеж, чтобы сделать его ключом словаря.
Проверяем, есть ли ключ в словаре. Если да: добавляем слово в существующий список анаграмм по этому ключу, если нет: создаём новую группу анаграмм.
Выводим двумерный список, состоящий из сгруппированных значений нашего словаря с анаграммами.

Сложность
O(n × k) - по времени
O(n × k) - по памяти


Код

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagrams = {}

for word in strs:
letter_counts = [0] * 26

for char in word:
letter_counts[ord(char) - ord("a")] += 1

key = tuple(letter_counts)

if key not in anagrams:
anagrams[key] = [word]
else:
anagrams[key].append(word)

return list(anagrams.values())


@algoses
🔥86
Гранты на обучение в Центральном университете

Получи грант на 4 года до 3 480 000 ₽ на учебу в бакалавриате Центрального университета.

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

Конкурс состоит из двух этапов: тестирование и бизнес-игра. Фаст-трек: поступи по ускоренному пути, если у тебя уже есть достижения.
Грант открывает доступ к мероприятиям университета: стипендиальная программа, пробные ЕГЭ и другие.
Для выпускников 10–11-х классов и СПО.

Участвуй в конкурсе уже сейчас!
4💊2
Задача с собеседования в Zalando

В лимонадном киоске один стакан лимонада стоит 5 долларов. Покупатели стоят в очереди и приобретают лимонад в порядке, указанном в массиве bills. Каждый клиент покупает только один лимонад и платит одной из следующих купюр: 5, 10 или 20 долларов.
Вам необходимо дать правильную сдачу каждому клиенту, чтобы итоговая сумма, которую он заплатил, составила ровно 5 долларов. Имейте в виду, что вначале у вас нет денег для сдачи.

Задан целочисленный массив bills, где bills[i] - это купюра, которой расплачивается i-й любитель лимонада.
Верните true, если можете дать правильную сдачу каждому клиенту, или false в противном случае.

Пример 1:
Input: bills = [5,5,5,10,20]
Output: true

Пример 2:
Input: bills = [5,5,10,10,20]
Output: false

Чат алгоритмистов

Решение
Создаём переменные для хранения купюр, переменная twenty нам не нужна, потому что не будет использоваться в качестве сдачи.
Проходим по каждому элементу в массиве и обрабатываем платежи, увеличивая (принимая купюру) и/или уменьшая (при необходимости сдачи) счётчик переменной.
Проверяем возможность дать клиенту сдачу при каждом платеже, применяя жадный алгоритм. Ищем наиболее оптимальное решение на каждом шаге:
При оплате 10$ - выбора нет, отдаём купюру номиналом 5, и это наиболее оптимально в данном случае. Но если клиент платит 20$, предпочитаем дать сдачу с использованием купюры наибольшего номинала (10+5, а не 5+5+5), так как 5$ более универсальны и чаще могут понадобиться для размена.

Сложность
O(n) - по времени
O(1) - по памяти


Код

class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = 0
ten = 0

for b in bills:
if b == 5:
five += 1
elif b == 10:
if five < 1:
return False
else:
five -= 1
ten += 1
else:
if five >= 1 and ten >= 1:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True


@algoses
6🔥4
Задача с собеседования в Zalando

Дан массив интервалов, где intervals[i] = [starti, endi]. Необходимо объединить все пересекающиеся интервалы, а затем вернуть массив, состоящий из непересекающихся интервалов, которые покрывают все интервалы из входных данных.

Пример 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Пример 2:
Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]

Чат алгоритмистов

Решение
1. Сортируем интервалы по началу, это гарантирует: если текущий интервал не пересекается с последним, то он не может пересекаться с каким-либо более ранним, т.к. все предыдущие интервалы имеют начало не больше, чем у последнего, и если последний заканчивается до начала текущего, то все предыдущие тем более закончились раньше. Это позволяет решить задачу за один проход.

2. Проходим по каждому отсортированному интервалу в массиве:

- добавляем новый интервал в список, если это первый интервал в списке ИЛИ если конец последнего интервала меньше начала текущего
(в merged лежит [1,6], а текущий интервал [8,10], 6 < 8 => интервалы не пересекаются => добавляем [8,10] как новый интервал).

- иначе объединяем его с последним интервалом и обновляем конец
(в merged лежит [1,3], текущий интервал = [2,6], они пересекающиеся, так как 3 ≥ 2. Обновляем конец объединённого интервала: max(3, 6) = 6, то есть [1,6]).


Сложность
O(n log n) - по времени
O(n) - по памяти


Код

class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda interval: interval[0])
merged = []

for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])

return merged


@algoses
6🔥2
Media is too big
VIEW IN TELEGRAM
2 недели, 2 бигтеха, 95 сильнейших студентов AI360

С 17 по 28 ноября второкурсники из МФТИ, НИУ ВШЭ, ИТМО и Университета Иннополиса работали в офисах Сбера и Яндекса под менторством тех, кто создаёт ИИ-продукты прямо сейчас.

Разбирали научные статьи по AI вместе с экспертами, работали над проектами в командах и защищали результаты на постерной сессии перед топ-менеджерами. Успели даже попасть на AI Journey 2025 и пообщаться с Германом Грефом 💚
Лучший способ прокачаться в ИИ — учиться там, где его создают 😎

AI360 — это про то, как компании растят новое поколение AI-специалистов вместе с лучшими вузами страны 🔝

Хочешь не пропустить следующий отбор на AI360? Подписывайся на нас — там будут все анонсы, лайфхаки по подготовке и истории студентов 🚀
7🔥3😎2
Т-Образование запускает курс по алгоритмам и структурам данных

Он поможет подготовиться к техническим интервью и уверенно решать алгоритмические задачи — один из ключевых этапов отбора в ИТ-компании.

В программе:

— еженедельные лекции с разбором новых тем и практикой;
— языки курса — C++, Perl, Java, C#, Python, Go, Scala, Kotlin и Swift;
— общий чат студентов и преподавателей по решению задач.

Курс ведет инженер мобильного приложения Т-Банка, преподаватель Т-Поколения и интервьюер алгоритмической секции.

Занятия проходят онлайн, а в конце у участников будет сертификат в портфолио.

Успейте подать заявку до 23 января
🔥4❤‍🔥21
Задача с собеседования в Zalando

Даны три целых числа: x, y и z.
У вас есть x строк, равных "AA", y строк, равных "BB", и z строк, равных "AB". Вы хотите выбрать некоторое (возможно, все или ни одной) количество из этих строк и объединить их в некотором порядке, чтобы сформировать новую строку. Эта новая строка не должна содержать подстрок "AAA" или "BBB".
Известно, что подстрока - это непрерывная непустая последовательность символов внутри строки.
Верните максимально возможную длину новой строки.

Пример 1:
Input: x = 2, y = 5, z = 1
Output: 12
Объяснение: мы можем объединить строки "BB", "AA", "BB", "AA", "BB" и "AB" в таком порядке. Тогда наша новая строка будет "BBAABBAABBAB".
Длина этой строки равна 12, и мы можем показать, что невозможно сформировать строку большей длины.

Пример 2:
Input: x = 3, y = 2, z = 2
Output: 14
Объяснение: мы можем объединить строки "AB", "AB", "AA", "BB", "AA", "BB" и "AA" в таком порядке. Тогда наша новая строка будет "ABABAABBAABBAA".
Длина этой строки равна 14, и мы можем показать, что невозможно сформировать строку большей длины.

Ограничения:
1 <= x, y, z <= 50

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задачу можно решить с помощью жадного алгоритма или более элегантно - с помощью выведения математической формулы, считающей длину строки. Используем второй способ:

Последовательности, которые мы можем соединять:
"AB" + "AA" = "ABAA"
"BB" + "AB" = "BBAB"
"AA" + "BB" = "AABB"

И те, которые НЕ можем:
"AA" + "AA" = "AAAA"
"BB" + "BB" = "BBBB"
"AA" + "AB" = "AAAB"

Строка "AB" самая безопасная и может использоваться для разбиения других последовательностей.
Если у нас равное количество строк "AA" и "BB" (x == y), то, чтобы высчитать максимальную длину строки нужно: сложить количество строк "AA", "BB" и "AB" и умножить сумму на 2 (по 2 символа в каждой строке).

Если же количество строк "AA" и "BB" различно, то: чередуем "AA" и "BB" столько раз, сколько можно. Далее, когда один из типов строк заканчивается, добавляем ещё одну строку противоположного типа. Так мы максимально продляем строку и не допускаем образования запрещённой подстроки.
Для наглядности:
Если x < y: ...AA + BB + AB - и дальше можем продолжать строку только типом "AB".
Если x > y: ...BB + AA или ...BB + AB + AA - и далее строку продолжать невозможно.

Определим, строк какого типа у нас меньше ("AA" или "BB"). Сформулируем формулу: мы используем все строки безопасного типа "AB" (по 2 символа в каждой: z * 2), также все строки того типа, которого у нас меньше (m * 2 символа), и строки противоположного типа в количестве, равном количеству строк менее частого типа + 1 ((m + 1)* 2 символа).


Сложность
O(1) - по времени
O(1) - по памяти


Код
class Solution:
def longestString(self, x: int, y: int, z: int) -> int:
m = min(x, y)
if x == y:
return 2 * (x + y + z)
else:
return 2 * m + (m + 1) * 2 + 2 * z


@algoses
🔥41
Новогодние скидки на нашу линейку математических курсов 🎓

Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:

➡️ алгоритмы
➡️ теория вероятностей
➡️ линейная алгебра
➡️ математический анализ

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

Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты! А если вы выполните все рекомендации, но не достигнете поставленной цели, то вам вернут все потраченные деньги!

Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
3