Контест

  Мне контест очень понравился, как отличная тренировка решения ботвистых задач. Мне не нравится, когда условие неполно, некорректно, неоднозначно. Здесь же все условия интуитивно понятные (мне) и, вроде, абсолютно корректные.
  Также, по задачам подготовлены очень хорошие тесты (могу оценивать только то, что дорешал A-C).
  Так что, к авторам вообще не может быть претензий, они подготовили оригинальный, качественный сет  задач. Лично мне контест очень понравился, хоть и поверг мой рейтинг в пучины отчаяния =).
  В каждой комнате все равны перед задачами и взломами, поэтому не вижу проблем с "неравенством" положений, о которых все пишут. Ну сразу же понятно, что в A всякие крайние случаи сыплются, а значит либо аккуратно на бумажке придумываешь решение, либо злостный тест, а лучше и то и другое. А дальше все покажет опыт, как и на других контестах.

Да, мы действительно написали n*log(n). И действительно TL. Видимо бага.
Если кто-то найдет её в алгоритме или пошлет мне хороший тест буду очень признателен.

// Генерил рандомные деревья (через снм), ежей, цепочки и т.п., на ноуте за 1.5 сек работает.

Условие:

В дерево T ответить на запросы radius[v, i] - количество вершин достижимых из v не более, чем за radius[v, i].
|T| <= 10⁵; |{radius[v, i]}| <= 3*10⁵

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

По мне, так смена цвета, это всегда очень приятно, вносит некое разнообразие в обычные цифры, поэтому изменение (увеличение числа цветов) мне нравится.

У меня появилась идея, что можно цвета интерполировать по текущим опорным цветам.
(на отрезке рейтинга [a_i, a_i+1] цвет участника color_i * (a_i+1 - rating) + color_{i + 1} * (rating - a_i))
С такой идеей можно добиться многих интересных эффектов (например, к топу можно интерполировать не линейно, к какому-нибудь target цвету).

Что-то вроде этого:


Тоже самое, но включая начальный отрезок:

Понятно, что с такой системой данные цвета не очень идут, это только для наглядности.

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

A. Треугольник

Из трех палочек с длинами a, b, c > 0 можно составить треугольник ненулевой площади тогда и только тогда, когда:
|a - b| < c < a + b (+)
При вырожденном случае в (+) одно из неравенств обращается в равенство. (Для обоснования можно построить окружности радиуса a и b с центрами в концах отрезка длины c, и проверить когда они пересекаются).

Таким образом, можно перебрать все тройки чисел из данных 4-х и проверить (+).

A. Арбуз

Чтобы арбуз мог быть разделен на две четные части, данное нам число w должно быть представимо в виде 2m + 2k (две четные части).
Таким образом w = 2(m+k), где m, k ≥ 1, то есть
(w ≥ 4 и w - четно) - необходимое и достаточное условие разделения арбуза