Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC). ×

Sereja's blog

By Sereja, 10 years ago, In Russian
Задача А. Лифт
Задача, на аккуратную реализацию:
- если мы находимся в пункте назначение, то ответ T.
- иначе лифт может находится в 2*М-2 состояниях, которые будут циклично повторятся. Состояние это номер этажа и направление, таких состояний будет 2*М-2. что-бы узнать состояние можно просто взять время по модулю. По состоянию можем определить этаж и направление, для удобства напишем функцию, которая определяет время которое нужно лифту что-бы добраться от одного этажа со стартовым направлением до другого, там нужно рассмотреть 4 варианта, этаж выше/ниже, и направление вверх/вниз. Дальше ответом будет функция от начального положения лифта в момент Т до старта+расстояние от старта до финиша.

Задача Б. Очень занимательная игра
Перебираем какое число мы поставим(I) первым оно будет от 1 до min(mod-1,A) потому-что дальше mod перебирать нет смысла, числа по модулю будут повторяться. Дальше домножим наше первое число на (109)%mod и возьмем произведение по модулю, пускай оно будет X тогда число I подходит если X!=0 и X+B<mod, что вроде-бы очевидно.
Задача С. Цикл
Тут было много решений с ДФС, но я писал немного другое:
Зафиксируем вершину V и разобьем все вершины на 2 группы, те которые имеют ребра в V и те которые имеют ребра из V. Теперь ребра делятся на такие группы: идут в V(d1), идут из V(d2), лежат в первой группе(m1), лежат во второй группе(m2), выходят из первой во вторую(n1), выходят из второй в первую(n2). Теперь мы можем утверждать что ответ есть если последняя группа не пустая. Как нам посчитать величины групп? Для начала посмотрим на то что мы знаем: по степеням входа и выхода вершин мы знаем значение n1+m1 и n2+m2, так-же мы знаем значение n1+n2 которое очевидно равно произведению этих двух групп, так-как между каждой парой есть ребро. Из этого несложно выразить значение n2,если оно положительное то переберем все пары и проверим их, хотя-бы одна найдется, так-что асимптотика O(N2).
Задача Д. Небыстрое преобразование
Делать можно разбиением задачи на подзадачи. Для начала заметим что любой отрезок до того как его преобразовали можно задать 2мя числами: 1м числом и разницей между числами, то-есть последовательность ничто другое как арифметическая прогрессия. При разбиении на два отрезка мы из состояния (l,r,q,w) l,r - границы отрезка, q - первое число,w - разница между числами. перейдем в состояния: (l,(l+r)/2,q,w*2) и ((l+r)/2+1,r,q+w,w*2). Теперь если мы попали в отрезок который полностью лежит в той области которая нас интересует, то нам не важно как стоят числа, нам важны сами числа. Суммы можно посчитать обрезав ненужные части как сумму арифметической прогрессии. В ненужных отрезки(которые не имеют общих частей с интересующих) мы просто ходить не будем. А кол-во отрезков будет как при подсчете суммы на отрезке в дереве отрезков, то-есть порядка O(log(N)). Что довольно мало.
Задача Е. Дерево или не дерево
Ее не сдавал, но решение придумал. Рассмотрим наш граф, он является деревом + одно ребро, то-есть цикл к вершинам которого прицеплены деревья. Рассмотрим задачу для дерева, сначала посмотрим на связь кол-во включенных вершин и количеством компонент связности: в дереве без выключенных вершин 1 компонента , при каждом добавлении выключенного ребра кол-во компонент увеличивается на 1, то-есть кол-во компонент в дереве это просто 1+кол-во выключенных ребер. То-есть нам каждый раз нужно знать кол-во включенных вершин. Эта задача решается с помощью Heavy-light декомпозиции, в подробности вникать не буду, если знать ее, то решение становится ясным, единственно над чем стоит подумать, это как поддерживать в дереве отрезков кол-во вершин с непарными числами. Теперь что-же делать если у нас есть цикл, все так-же просто у нас путь всегда будет один из: путь по дереву которое "свисает с цикла" решается стандартно, и если начало и конец пути лежать в разных деревьях, то-есть проходит по циклу, это можно решать так: решим задачу для корней деревьев которые содержат наши старт и финиш и старта и финиша, и осталось малая часть: разобраться с циклом. Замечу что лексикографичность(по какую сторону будем идти) выбрать не сложно, там всего максимум 2 варианта, то-есть можно сказать что отрезок на котором мы будем менять цвет мы знаем. Осталось установить закономерность как влияют кол-во выключенных клеток. Замечу что то какие деревья и сколько в них чего нас не интересует, нас интересует только их кол-во и кол-во выключенных ребер в цикле. Сначала если у нас все включены, то от ответа нужно отнять N и добавить 1, потому-что у нас все компоненты объединены, при добавлении выключенного ребра ответ будет увеличиваться на 1, то-есть нам нужно будет еще всего-лишь узнавать кол-во выключенных ребер. Вроде-бы все.

Если-что-то не так, то пишите. Надеюсь вам понятно.
 
 
 
 
  • Vote: I like it
  • +34
  • Vote: I do not like it