Разбор
V (Vadim) K (Krutoi)Тасочка А (Бшка Див2)
Ну тут все легко
Бежишь фором со второй вершины и до последней. A[i] = k - A[i-1]; Вот и все.
Сложность: O(n)
Решение: https://pastebin.com/Xi7M3MtV
Тасочка Б (Цшка Див2)
Тут-то ты и вспоминаешь о памяти, о которой не помнил все эти годы.
Кол-во островов 30000, длина прыжка от 1 до 30000, но создать двумерное ДП на 30000*30000 элементов не получится. Поэтому быстро додумываем, что даже если изначальная длина прыжка равна 1, то макс длина будет ~246. Из этого выходит, что достаточно будет сделать ДП 30000*500 элементов, где 250 - изначальная длина прыжка.
Сложность: O(30000*500) = O(15000000)
Решение: https://pastebin.com/Q4DWCVrK
Тасочка Ц (Цшка Див1)
Нерешаемае геома. Я решил прочитать разбор, но лучше бы не делал этого. Что-то говорят про формулу Эйлера (https://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84#%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%B0)
Лучше это говно и не решать, я думал там все проще. Извините, что добавил.
Сложность: O(chen' slojno)
Ладно, на самом деле старик Эйлер говорит, что f = e - v + c + 1, где f - кол-во регионов, v - кол-во аершин, e - кол-во граней, c - количество частей. Находим v уникальных точек с помощью функции нахождения точек пересечения двух кругов, e для каждого круга = v этого круга, c можно найти через СНМ.
Но всем же лень это писать, так???
Решение: (из офф разбора)
Тасочка Д (Ешка Див2)
Вещей немного, только 100, времени тоже, всего 2000 секунд. Опять ДП, 100*2000 элементов.
Для начала посортируем все вещи в порядке убывания их времени сгорания. Сделано это для того, чтобы при спасении вещи мы не беспокоились о том, что перед этой вещью нужно было бы спасти еще какую-то.
Клетка D[i][j] значит, что мы рассмотрели первых i вещей, затратили j времени. D[i][j] хранит ценность спасенных вещей и их номера. D[i][j] = max(D[i-1][j], D[i-1][j-t[i]]);
Хотя хватило бы и ДП 2*200 элементов.
Сложность: O(n*max(d))
Решение: https://pastebin.com/eaYK9wzp
Тасочка Е (Джишка финала говноконтеста[эту таску решило больше ссего человек])
Очень легкая таска.
Я решал через хеши. Сначала каждую строку, что даны изначально, хэшируем, пихаем в мапу (значение - количество таких строк). Затем подставляем в каждый знак воросика в новых строках 'a','b','c','d','e' или ' '. Если такие строки есть, то добавляем к ответу количество таких строк.
Там в тестах есть защита от хэшей с некоторыми модулями, поэтому либо используем свой интересный модуль, либо пишем двойное хэширование(что сделал я)
Сложность: O(n*len(s)*log(n) + m*6^3*len(s)*log(n)) ~= O(1024000000)
Решение: https://pastebin.com/9j5Pz4Hj