Ищу человека на МКОШП. О себе : участник Всеросса(122 место), участник дисттура, фиолетовый на codeforces, желтый на codechef. В лс.

842A - Кирилл и игра)

Пусть exp – количество опыта в зелье, а cost — его стоимость. Мы хотим узнать есть ли такие exp и cost чтобы выполнялось условие . Решение этой задачи: перебрать cost с x по y и проверить, что exp = k·cost находится в отрезке с l по r.

https://ideone.com/a8syda

842B - Глеб и пицца)

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

Рассматривать взаимное расположение окружностей удобно, опираясь на их радиусы и расстояние между их центрами.

Чтобы кусочек колбасы находился внутри корки, он должен, во-первых, находиться в пицце ) и, во-вторых, не должен включать в себя кусок пиццы без корки ).

Пройдёмся по массиву и для каждого кусочка узнаем, лежит ли он в корке.

https://ideone.com/Jd66XL

842C - Илья и дерево)

Заметим, что если значение a_i в вершине дерева i не равно 0, то красотой вершины и красотой её потомков будут являться какие-то из делителей a_i.

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

Давайте подсчитаем красоту для каждой вершины, если мы сделали значение в вершине корня дерева равным 0. Это можно сделать обходом по дереву, где для каждой вершины i её красоту будем считать равной gcd(a_i, ans[par_i]).

Если значение в вершине корня не равно 0, то возможными значениями красоты для всех вершин будут являться делители значения в корне. Мы можем для каждого из этих делителей поддерживать информацию, сколько чисел на пути от корня до текущей вершины делились на него. Обновлять эту информацию нужно при входе и выходе из вершины, перебирая делитель значения в корне. Обладая этой информацией и зная, на какой глубине дерева d мы сейчас находимся, мы можем найти красоту вершины дерева. Она равна наибольшему делителю значения в корне, встретившемуся хотя бы d - 1 раз на пути от корня до текущей вершины.

https://ideone.com/uQNFX3

842D - Витя и странный урок)

Если у нас был запрос x_i, а дальше x_i + 1, то в качестве второго запроса можно рассматривать число , оставляя массив неизменным после первого запроса. То есть мы можем держать одну переменную, которая будет означать текущий xor запросов.

Заметим, что если у нас есть все числа до 2^k - 1 и мы выполняем операцию \xor с любым числом, меньшим, чем 2^k, то все эти числа останутся в массиве.

Построим бор по двоичному представлению чисел и посчитаем количество листьев в поддеревьях.

На каждый запрос будем спускаться по бору. Нам нужно получить как можно меньшее число, поэтому, если текущий бит числа из запроса равен i (i = 0 или i = 1), то нужно рассмотреть сперва поддерево, соответствующее биту i. Мы можем спускаться дальше по бору только в том случае, когда поддерево не является полным бинарным деревом глубины, равной количеству не рассмотренных бит. Как только мы не можем куда-то пойти из-за того, что сын отсутствует, добавляем текущий бит и обнуляем все следующие.

https://ideone.com/gVE1kC

842E - Никита и игра)

Самая удалённая вершина от любой — одна из вершин диаметра.

Допустим у нас диаметр (a, b), где a и b — его концы, и добавляется вершина с, тогда диаметр может либо остаться таким же, либо увеличиться на единицу (концами диаметра тогда будут вершины (a, c) или (b, c)).

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

Построим дерево отрезков по эйлеровому пути, в котором будем хранить на отрезке [l, r] максимальное расстояние от вершин отрезка до ближайшего центра и количество вершин с таким расстоянием. Тогда ответ для запроса будет хранится в корне дерева.

Когда поступает новая вершина, нужно понять, увеличивается ли диаметр при ее добавлении в дерево. Это можно сделать с помощью двоичного подъема. Если диаметр увеличивается, то нужно обновить центры дерева и расстояния до ближайшего центра для вершин.

https://ideone.com/5tXC92

Всем привет!

29 августа 2017 в 18:05 (по московскому времени) состоится рейтинговый Codeforces Round #430 для участников из второго дивизиона. Как всегда, участники из первого дивизиона смогут принять участие вне конкурса.

Задачи для вас готовили Глеб Glebodin Лобанов, и Илья Ilua Максимов. Большое спасибо Алексею Perforator Рипинену за помощь в подготовке раунда, Даниилу qoo2p5 Николенко, Ильдару 300iq Гайнуллину и Алексею Livace Илюхову, Ивану BledDest Андросову, Максиму HellKitsune Финютину за тестирование задач и конечно же Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и 2 часа на их решение.

Разбалловка — стандартная: 500 — 1000 — 1500 — 2000 — 2500.

Надеемся, раунд вам понравится! Всем удачи!

Поздравляем победителей!

Div. 1:

uwi

vintage_Vlad_Makeev

natsugiri

kmjp

victoragnez

Div. 2:

fatego

sufficiently_large_boss

qscqesze6

white_flag

Panole2333330

Разбор : http://codeforces.net/blog/entry/54179

Сегодня прошел отборочный этап RCC! Я тоже его писал, к сожалению я неправильно прочитал первую задачу и подумал что требуется минимизировать произведение! Теперь, когда мы с другом начали ее обсуждать, мы тут же подобрали контр-тест! https://ideone.com/XVegLq мой код и тест! В связи с этим вопрос: у кого еще что-то было с RCC? http://codeforces.net/blog/entry/52023