Участвуй в КосмоХакатоне 4–6 сентября, решай реальные космические кейсы, поборись за 1,2 млн ₽ и шанс попасть в финал в Москве!

С 4 по 6 сентября в Ростове-на-Дону пройдёт КосмоХакатон Южного и Северо-Кавказского федеральных округов — масштабное соревнование для тех, кто готов превратить данные о нашей планете в реальные технологические решения.

Один хакатон — два формата: участвовать можно очно в Ростове-на-Дону или онлайн из любой точки России. Все команды работают над едиными кейсами, оцениваются по одинаковым критериям и участвуют в общем рейтинге.

В рамках хакатона также пройдёт открытая лекция «Применение космических технологий для решения экологических задач» от Игоря Кожелина, CEO SR Data.
Призовой фонд — 1 200 000₽

Даты проведения: 4–6 сентября
Формат: онлайн и офлайн
Очная площадка: Центр развития предпринимательства «Новый Ростов», ул. Максима Горького, 151, 4 этаж.
🔗 Зарегистрироваться: https://космохакатон.рф

Судоку

Алгоритм:

1. Создайте функцию, которая проверяет, действительна ли данная матрица судоку или нет. Сохраните Hashmap для строки, столбца и полей. Если какое-либо число имеет частоту больше 1 в hashMap, верните false, иначе верните true;

2. Создайте рекурсивную функцию, которая принимает сетку и текущий индекс строки и столбца.

3. Проверьте базовые случаи:
⁃ Если индекс находится в конце матрицы, т.е. i=N-1 и j=N, тогда проверьте, безопасна ли сетка или нет, если безопасно, распечатайте сетку и верните true, иначе верните false.
⁃ Другой базовый случай — когда значение столбца равно N, т. е. j = N, затем происходит переход к следующей строке, т. е. i++ и j = 0.

4. Если текущий индекс не присвоен, то заполняем элемент от 1 до 9 и повторяем для всех 9 случаев индекс следующего элемента, т.е. i, j+1. если рекурсивный вызов возвращает true, разорвите цикл и верните true.

5. Если присвоен текущий индекс, вызовите рекурсивную функцию с индексом следующего элемента, т. е. i, j+1.

Сложность: O(9^(n*n)

Вес последнего камня

Проблема: Дан массив целых чисел, где Stones[i] представляет вес i-го камня.
Представим, что мы играем в игру с камнями. На каждом ходу выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют вес x и y, причем x <= y.

Результат удара может быть:
- Если x == y, оба камня уничтожаются, и
- Если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x.

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

Пример: Input: stones = [2,3,6,2,4]
Output: 1

Найти минимум в повернутом отсортированном массиве

Проблема: Дан массив длины n, который изначально был отсортирован по возрастанию. Далее его поворачивали от 1 до n раз. Например, массив nums = [1,2,3,4,5,6] может выглядеть следующим образом:
[3,4,5,6,1,2], если его повернули 4 раза.
[1,2,3,4,5,6], если он был повернут 6 раз.

Обратим внимание, что поворот массива 4 раза перемещает последние четыре элемента массива в начало. Вращение массива 6 раз дает исходный массив.

Предполагая, что все элементы в повернутом отсортированном массиве уникальны, реализуемый алгоритм должен возвращать минимальный элемент этого массива. Решение, работающее за время O(n), тривиально, поэтому реализацию должна быть за время O(log n).

Пример 1: Input: nums = [3,4,5,6,1,2]
Output: 1

Пример 2: Input: nums = [4,5,0,1,2,3]
Output: 0

Поиск в повернутом отсортированном массиве

Проблема: Дан массив длины n, который изначально был отсортирован по возрастанию. Далее его поворачивали от 1 до n раз. Например, массив nums = [1,2,3,4,5,6] может выглядеть следующим образом:
[3,4,5,6,1,2], если его повернули 4 раза.
[1,2,3,4,5,6], если он был повернут 6 раз.

Учитывая повернутый отсортированный массив nums и число (target), которое надо найти, алгоритм должен возвращать индекс target в пределах nums или -1, если он отсутствует. Предполагается, что все элементы в отсортированном повернутом массиве уникальны.

Решение, работающее за время O(n), тривиально, поэтому реализацию должна быть за время O(log n).

Пример 1: Input: nums = [3,4,5,6,1,2], target = 1
Output: 4

Пример 2: Input: nums = [3,5,6,0,1,2], target = 4
Output: -1

Медиана двух отсортированных массивов

Проблема: Даны два целочисленных массива nums1 и nums2 размера m и n соответственно, каждый из которых отсортирован в порядке возрастания. Необходимо реализовать алгоритм, который возвращает медианное значение среди всех элементов двух массивов.

Медиана набора чисел — это значение, отделяющее верхнюю половину от нижней половины данных.

Решение работает за O(log(m+n)) времени.

Пример 1: Input: nums1 = [1,2], nums2 = [3]
Output: 2.0

Пример 2: Input: nums1 = [1,3], nums2 = [2,4]
Output: 2.5

Допустимая доска Sudoku

Проблема: Дана доска для судоку размером 9 x 9. Доска судоку действительна, если соблюдаются следующие правила:
- Каждая строка должна содержать цифры от 1 до 9 без дубликатов.
- Каждый столбец должен содержать цифры 1–9 без дубликатов.
- Каждый из девяти подполей сетки размером 3х3 должен содержать цифры от 1 до 9 без дубликатов.

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

Пример:
Input:

board = [["1","2",".",".","3",".",".",".","."],
["4",".",".","5",".",".",".",".","."],
[".","9","1",".",".",".",".",".","3"],
["5",".",".",".","6",".",".",".","4"],
[".",".",".","8",".","3",".",".","5"],
["7",".",".",".","2",".",".",".","6"],
[".",".",".",".",".",".","2",".","."],
[".",".",".","4","1","9",".",".","8"],
[".",".",".",".","8",".",".","7","9"]]

Output: false

Сумма трёх целых чисел

Проблема: Дан целочисленный массив nums. Необходимо реализовать алгоритм, который вернет все тройки [nums[i], nums[j], nums[k]], где nums[i] + nums[j] + nums[k] == 0, и индексы i, j и k различны.

Вывод не должен содержать повторяющихся троек. Можно вернуть результат и тройки в любом порядке.

Пример 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Объяснение:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

Пример 2:
Input: nums = [0,0,0]
Output: [[0,0,0]]

Покупка и продажа крипты

Проблема: Дан целочисленный массив цен, где prices[i] — цена AlgoCoin на i-й день. Можно выбрать один день для покупки одного AlgoCoin и выбрать другой день в будущем для его продажи.

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

Пример 1:
Input: prices = [10,1,5,6,7,1]
Output: 6
Пояснение: купить за prices[1] и продать по prices[4]. В итоге, прибыль = 7 – 1 = 6.

Пример 2:
Input: prices = [10,8,7,5,2]
Output: 0
Пояснение: Невозможно совершить прибыльные сделки, поэтому максимальная прибыль равна 0.

Проверка скобок

Проблема: Дана строка s, состоящая из следующих символов: '(', ')', '{', '}', '[' и ']'. Входная строка s действительна тогда и только тогда, когда:
- Каждая открытая скобка закрывается закрывающей скобкой одного и того же типа.
- Открытые скобки закрываются в правильном порядке.
- Каждой закрывающей скобке соответствует открытая скобка того же типа.

В результате надо вывести true, если s — допустимая строка, и false в противном случае.

Пример 1:
Input: s = "([{}])"
Output: true

Пример 2:
Input: s = "[(])"
Output: false

Обратная польская запись

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

Операнды могут быть целыми числами или результатами других операций. К операторам относятся «+», «-», «*» и «/». Предположим, что деление целых чисел всегда сокращается до нуля.

Пример:
Input: tokens = ["1","2","+","3","*","4","-"]
Output: 5
Объяснение: ((1 + 2) * 3) - 4 = 5