На эту неделю подготовили тренировочный контест по сортировкам, поиску и жадным идеям.

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

В контест вошли задачи:

• Сортировка по возрастанию — https://judje.olprog.ru/problem/sortasc
• Сортировка по убыванию — https://judje.olprog.ru/problem/sortdesc
• Минимальная разность — https://judje.olprog.ru/problem/mindifference
• Размах массива — https://judje.olprog.ru/problem/range
• k-й наименьший элемент — https://judje.olprog.ru/problem/kthsmallest
• Медиана массива — https://judje.olprog.ru/problem/median
• Индексы двух чисел с заданной суммой — https://judje.olprog.ru/problem/twosumindices
• Количество различных элементов — https://judje.olprog.ru/problem/distinctcount
• Мода массива — https://judje.olprog.ru/problem/mode
• Ближайшая пара — https://judje.olprog.ru/problem/closestpair
• Позиция элемента — https://judje.olprog.ru/problem/findposition
• Максимальный разрыв — https://judje.olprog.ru/problem/maxgap
• Минимальная сумма пар — https://judje.olprog.ru/problem/minpairsum
• Жадный выбор предметов — https://judje.olprog.ru/problem/greedyitems
• Минимальное скалярное произведение — https://judje.olprog.ru/problem/minscalarproduct
• Минимальное отсутствующее положительное число — https://judje.olprog.ru/problem/mexpositive

Этот контест подойдёт тем, кто хочет:

• закрепить сортировку массивов;
• научиться использовать порядок элементов для упрощения задачи;
• потренировать поиск, подсчёт и работу с частотами;
• разобраться с медианой, модой и k-м элементом;
• увидеть, как сортировка помогает в жадных задачах;
• подготовиться к более сложным темам: двум указателям, бинарному поиску и структурам данных.

Во время решения полезно обращать внимание на несколько вещей:

• нужно ли сохранять исходные индексы после сортировки;
• можно ли решить задачу быстрее после упорядочивания массива;
• как правильно обработать повторяющиеся элементы;
• что делать при нескольких одинаково хороших ответах;
• нужен ли словарь/множество для подсчёта;
• не появляется ли переполнение при суммах и произведениях.

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

Удачи в решении!

Ждём ваши результаты, вопросы и впечатления от задач.