When I'm looking at Status page an press F5 for big amount of times, sometimes I see such a page:

No colors, no nice font at "Verdict" column

My reaction:

I look at it and I have oggression and teeth creak

Киньте плз годного рэпчика послушать

Дорешиваю задачу 573C - Bear and Drawing.

Мое решение 12772765 получило wa12.

Но я не расстроился, и рандомно пошаффлил вершины. Теперь мое решение стало получать АС.

12772768

Я конечно рад, что я сдал задачу, но по-моему это не нормально.

Отличие там в одной строке random_shuffle(q.begin(), q.end());

UPD

Сдал честно. 12773232. Но все же тесты немного weak.

Смотрите, какой заголовок б^ло^г_а прикольный!

А у тебя спина белая

Есть вот такая вот функция.

def test(k):
	i = 0
	j = randint(0, k - 1) # randint(0, k - 1) - случайное целое число из [0, k - 1]
	while i < j:
		i += 1
		j = randint(0, k - 1)
	return i

Какое математическое ожидание величины test(k)? Требуется посчитать быстрее, чем за O(k).

460A - Вася и носки

В этой задаче нужно было промоделировать то, что написано в условии. Также можно показать, что ответом является формула , где под ⌊ x⌋ понимается целая часть числа x.

7536107

460B - Димка и уравнение

Заметим, что S(x) может принимать только целые значения и 1 ≤ S(x) ≤ 81. Переберем S(x) от 1 до 81, и посчитаем значение выражения B * S(x)^A + C. Затем, если сумма цифр полученного числа совпадает с S(x), число положительное и оно меньше 10⁹, то оно является решением. В этой задаче могли возникнуть проблемы из-за использования встроенной в C++ функции pow()

7536153

460C - Подарок

Заметим, что ответ положительное число, не превосходящее 10⁹ + 10⁵. Найдем ответ, используя бинарный поиск по ответу. Действительно, мы можем проверять за O(n) можно ли достичь определенной высоты. Для этого идем слева направо. Для текущего цветка посчитаем какое минимальное количество раз нужно полить текущий цветок, что бы он стал высоты не менее, чем проверяемая. Если текущий цветок нужно увеличить на h, то начнем h отрезков в этом цветке. Будем хранить массив, в котором st[i] — количество отрезков, начинающихся в i-ом цветке. Так же будем поддерживать переменную, в которой будем хранить количество отрезков, в которых содержится текущий цветков. Этот счетчик можно обновлять за O(1). Действительно, когда чтобы получить новое значение из предыдущего, достаточно отнять st[i - w], и, если мы создаем новые отрезки, прибавить st[i].

Также можно доказать, что работает простая жадность. На каждой из m итераций можно искать левейший цветок минимального роста, и поливать отрезок, начинающийся в этом цветке. Реализация "в лоб" отрабатывает за O(nm), поэтому для реализации нужно использовать структуру данных, поддерживающую операции взятия минимума и множественного прибавления на отрезке. Помочь в этом деле могут sqrt-декомпозиция или дерево отрезков с ленивым обновлением. Эти решения работают значительно дольше первого, но влазят в TL. Доказательство: Рассмотрим любую оптимальную последовательность ходов (то есть такую, при которой достигается максимальный ответ). Рассмотрим цветок, который изначально был самым левым из минимальных и рассмотрим все отрезки, в которых он содержится.(Предположим он содержится хотя б в одном отрезке, так как иначе, ответ равен начальной высоте этого цветка, а значит мы можем начать отрезок в этом цветке, и ответ не изменится). Предположим, нет отрезков, начинающихся в нем. Тогда рассмотрим отрезок, который начинается правее всех остальных (если их несколько, то любой такой). Тогда верно следующее: мы можем подвинуть этот отрезок вправо, так, чтобы он начинался в минимальном левом цветке. Действительно, цветы которые раньше находились на этом отрезке изначально были строго выше минимального и поливались как минимум столько же раз, сколько и минимальный. Значит после того, как мы сместили отрезок, их высота осталась не меньше, чем высота изначально минимального левого цветка. Таким образом новая последовательность ходов также будет оптимальной. Значит есть последовательность ходов, которая содержит отрезок, начинающийся в левом минимальном цветке. Тогда применим этот отрезок. Аналогично будем поступать в остальные дни, и тогда высота самого низкого цветка будет максиммально возможной.

7536171

460D - Витя и множество

Если r - l ≤ 4, то можно перебрать все варианты. Иначе, если k = 1, очевидно, что ответ l. Если k = 2, то ответ 1, т.к. можно выбрать числа 2x и 2x + 1, и их xor равен 1. Если k ≥ 4, то ответ 0, т.к. можно выбрать две пары чисел с xor 1, и их xor будет равен 0.

Осталось разобрать случай когда k = 3. Если k = 3, то выбрав числа 2x и 2x + 1 можно достичь значения 1. Поэтому остается узнать, можно ли получить xor равный 0. Предположим, существуют три числа x, y и z (x > y > z) которые лежат на отрезке [l, r], и их xor равен 0. Рассмотрим старший значащий бит числа x. В этом же разряде числа y тоже 1, т.к. xor равен 0, а y > z. Рассмотрим следующий бит. Если у z там стоит 0, то сделаем следующее: в предыдущем разряде чисел x и y 1 заменим на 0, а в этом бите чисел x и y поставим 1, если там был 0. Очевидно xor остался равным 0, число z не изменилось, а числа x и y стали ближе к числу z, поэтому они остались на отрезке [l, r]. Рассмотрим следующий бит чисел. Если там у z опять стоит только нуль, то опять заменим старшие биты в числах x и y и т.д. Т.к. z > 0, то когда-нибудь мы придем к разряду, в котором есть 1. Так как xor равен 0, то у числа x в этом разряде тоже 1 (x > y), а у числа y в этом разряде 0. В последующих разрядах будем заменять бит в числе x на 0, в числах y и z на 1. От этого число z будет не уменьшаться, а x не возрастать, при этом x > y > z будет оставаться верным. В итоге получили следующее: если такие три числа существуют, то существуют и три числа вида

1100…000

1011…111

0111…111

xor которых равен 0. Таких троек мало, поэтому их можно перебрать

7536186

460E - Роланд и роза

Формальная постановка задачи: даны натуральные числа R — радиус окружности, и N. Требуется выбрать N не обязательно различных точек A₁, A₂, ...A_N лежащих внутри или на границе окружности, таких, что величина

максимальна.

Сперва обозначим за вектор, ведущий из точки начала координат в точку A_i. Величина теперь равна , что равно , а это нетрудно расписывается как . Это наводит нас на мысль о том, что точки выгоднее расположить как можно ближе к окружности, чтобы |a_i²| был как можно больше, но сделать это надо так, чтобы было как можно меньше. В частности, становится очевидным, что если N четно, то можно выбрать один из диаметров, и половину точек покидать в один конец диаметра, а половину — в другой. Теперь попробуем сформулировать все более строго. Пусть мы нашли расстановку точек, на которой наше выражение достигает своего максимума. Обозначим координаты точек как (x₁, y₁), (x₂, y₂), ..., (x_n, y_n). Пусть первые N - 1 точка фиксированы, а координаты последней мы можем двигать — обозначим их, как (x, y). В терминах этих координат, мы хотим максимизировать выражение

Все квадраты, где не участвуют x, y мы отбросили. Максимизация этого выражения раскрытием скобок и отбрасыванием констант сводится к максимизации

Таким образом, мы свели задачу к тому, чтобы найти наиболее удаленную целочисленную точку от точки с координатами

. Теперь мы сделаем очень важный вывод: наиболее удаленная целочисленная точка находится в одной из вершин выпуклой оболочки всех целочисленных точек, находящихся в круге. Доказательство. Обозначим имеющуюся точку за T, а наиболее удаленную от нее, находящуюся в выпуклом многоугольнике P за X(она, очевидно, содержится в выпуклой оболочке). Теперь продлим TX до пересечения с одной из сторон многоугольника — обозначим этот отрезок за AB, а точку пересечения за X'. Ясно, что TX' ≥ TX. Нетрудно видеть, что один из углов и — тупой,следовательно, по свойству тупоугольных треугольников, или TA ≥ TX' ≥ TX или TB ≥ TX' ≥ TX, то есть, точку X можно заменить на одну из вершин оболочки и расстояние может лишь увеличиться.

Таким образом, каждую точку оптимального набора мы можем считать лежащей в вершине выпуклой оболочки. Соответственно, решение — перебрать всевозможные наборы точек и посмотреть значение выражения для них. Если R ≤ 30, то на выпуклой оболочке содержится не более 36 точек — можно проверить с помощью компьютера. Таким образом, перебор всех наборов точек займет порядка , что вполне укладывется в тайм-лимит, возможно, с некоторыми оптимизациями.

Немного о реализации перебора: в каком-то векторе хранится выпуклая оболочка. Заводится рекурсивная функция, параметры которой это:1) сколько точек уже добавлено 2) ссылка на вектор с точками 3) сумма x-координат точек 4) сумма квадратов x-координат точек 5) сумма y-координат точек 6) сумма квадратов y-координат точек.

На каждом этапе рекурсии берется последняя добавленная в растановку точку, и в расстановку по очереди добавляются точки, начиная с нее и до конца выпуклой оболочки — это начинает новый этап рекурсии. Также мы достаточно очевидно пересчитываем текущую мощность — это делается с помощью 3, 4, 5 и 6го параметров.

На самом последнем этапе, когда мы уже взяли N точек, мы определяем, была ли у нас когда-нибудь столь большая мощность. Если нет — копируем его во внешнюю переменную maxvalue, а набор точек — во внешний объект bestvector.

7536206

UPD Разбор задачи C был дополнен