Div.2 – A. Football

В этой задаче достаточно просто найти самую длинную подстроку из одинаковых цифр и проверить или ее длина является не менее 7.

Div.2 – B. Lucky Numbers - 2

Если длина входного числа является нечетным, то, очевидно, искомое число имеет длину на 1 большую и выглядит так: 4444 ... 7777, то есть сначала L / 2 четверок, затем L / 2 семерок, где L - длина входного числа + 1. Если число имеет четное количество цифр, то, возможно, число-результат будет иметь такое же количество цифр, или на 2 больше. То есть, длина результата будет не более чем на 2 длиннее, чем число N. Это означает, что мы можем легко рекурсивно сгенерировать все счастливые числа длиной до 10, выбрать из них очень счастливые числа, среди них найти наименьшее, не меньше N.

Div.1 – A, Div. 2 – C. Hockey

Заведем массив B. Для каждого слова из словаря найдем все вхождения в строке S, для кожного из них B [i] обозначим true, где i лежит в [Li, Ri], где Li - номер самого левого символа следующего вхождения, Ri - самого правого . Теперь для каждого i, для rоторого B[i] = true, сделаем следующее:

•          Если S[i] = letter і letter = ‘a’, тогда S[i] = ‘b’
  
•          Если S[i] = letter і letter != ‘a’, тогда S[i] = ‘a’
  
•          Если S[i] != letter, тогда S[i] = letter.
  

Очевидно, что это удовлетворяет условию и гарантирует максимальное количество letter и ее лексикографическая минимальность. Также нужно аккуратно различать большие и маленькие латинские буквы.

Div.1  - B. Lucky Number

Сначала смотри Div.2 – B

Заметим, что ответ будет примерно таким: к какой-то позиции результат будет совпадать с N (эта часть будет счастливым число), следующая цифра увеличится, а затем будет идти как угодно. Переберем все такие возможные позиции. Чем больше номер такой позиции, тем меньше будет число. Возможные позиции будут в промежутке [0, lucky_prefix], где lucky_prefix - размер наибольшего префикса строки (числа N), который является счастливым. Пусть мы рассматриваем позицию i. Если цифра в ней меньше 4, мы можем установить ее 4, при этом можем как угодно менять все цифры правее. Так же, если цифра меньше 7 (только в случае если она больше или равна 4) - установим ее 7. При этом некоторые позиции могут нам не подойти. Для того чтобы позиция подошла, нужно чтобы абсолютная разница между количеством четверок и семерок к позиции i (включая i, включая замену) была меньше или равна размера части справа от i. Теперь пусть позиция i подошла нам (и она является самой правой возможной), тогда нужно заполнить правую часть. Ее следует заполнять следующим образом слева направо: если на какую позицию мы поставим 4 и дальше сможем заполнить число так, чтобы количество четверок и семерок была равной (т.е. abs (c4 + 1- c7) <= n-j-1, j - текущая позиция которую рассматриваем, c4, c7 - количество 4-ок и 7-ок в позиции j, включая заменены цифры), то поставим 4, иначе 7. Если позиции i не существует, то ответ - число в форме 4444 ... 7777, здесь количество четверок = количеству семерок = (n +2) / 2.

Div.1 - C, Div.2 - D. Volleyball

Сначала в этой задаче нужно найти минимальный путь между всеми парами вершин. Так как их количество до 1000, то обычные кубические алгоритмы по времени вкладываться не будут. Для этого нужно было написать алгоритм Дейкстры за O (N * (N + M) * logN), подробнее об этом можно прочитать здесь: http://e-maxx.ru/algo/dijkstra_sparse. Следующей частью решения задачи является составление новой матрицы, для которой G[i][j] = C[i], если D[i][j] <= T[i], иначе G[i][j] = INF. Здесь D[i][j] - минимальный путь между вершинами i и j, G[i][j] - стоимость такого пути. Теперь нужно просто найти минимальный путь между вершинами X и Y используя G, что можно выполнить используя простой алгоритм Дейкстры за O (N * N + M).

Div.1 – D, Div.2 – E. Horse Races

Традиционно напомню, что ответ будет Результат (0 .. R) - Результат (0 .. L-1).

Пусть у нас есть заполненный массив DP[x][y][z] - количество чисел длины x если последняя счастливая цифра в нем была на позиции y и boolean z (0 or 1) - была уже пара счастливых цифр на расстоянии не больше K. Ответ теперь будем строить так. Пусть s - строка, которая является числом N, F (x, y, z) - результат для префикса к позиции x, y - последняя счастливая цифра, z (0,1) - была пера счастливых цифр на расстоянии не более K. Очевидно, что если мы в какой позиции поставим меньшую цифру чем в строке, то все цифры справа мы можем выставлять как угодно (если только все цифры слева от этой позиции совпадают с лентой). Переберем возможные цифры, которые поставим в текущей позиции. Если эта цифра меньше чем s [x], тогда к результату для F (x, y, z) добавим DP [n-x-1] [yy] [zz]. Здесь y и z возможно изменится и перейдут в yy и zz, если цифра которую мы устанавливаем является счастливой. Если эта цифра равна s[x], тогда к результату прибавим F (x+1, yy, zz) - опять, y и z изменится, если s [x] является счастливой цифрой. DP заполняется тривиально. Пусть из состояния (x, y, z) мы ставим на позицию x какую цифру d. Из состояния (x, y, z) мы можем перейти в состояние (x+1, yy, zz). y перейдет в yy и z в zz при тех же условиях что и выше.

Сложность - O (T * |N|).

Div.1 – E. Lucky Country.

Пусть все A[i] - посортированы размеры различных компонент связанности, C[i] - количество компонент размером A[i]. Сумма по всем C[i]*A[i] равна N. Размер массива A будет O (sqrt (N)).

Пусть все C [i] = (2^k) -1. Разложим его следующим образом 1 + 2 + 4 + 8 + ... + 2^(k-1). Очевидно, что если выбирать из такого множества какое-то подмножество (его стоимость будет равна ее размера), можно представить любое число от 0 до C[i]. То есть мы свели задачу к следующей. Для каждого A[i]  есть log (C [i]) вещей, каждая из которых имеет стоимость и может быть использована или не использована. Это уже стандартная задача о рюкзаке (почитай http://ru.wikipedia.org/wiki/Задача_о_рюкзаке). Сложность такого решения O (N * S), где S - сумма по всем log (C [i]). Если же C[i] не является степенью двойки, то нужно найти наибольшее k для которого (2 ^ k) -1 <= C[i] и добавить в множество C[i]-((2^k)-1).