982A - Row
Из двух, описанных в условии правил, следует, что рассадка является максимальной тогда, когда в ней не встречаются две единички рядом или три нолика. Также необходимо аккуратно обработать концы данного ряда — надо проверить, что нельзя посадить человека на самый правый или самый левый стул.
982B - Bus of Characters
Заметим, что финальные пары интроверт-экстраверт определяются однозначно, а также, что с помощью стека, можно восстановить, какой экстраверт к какому интроверту подсядет (заметим, что нолики единички будут образовывать правильную скобочную последовательность). Тогда одним из решений может быть такое:
- Сортируем массив длин рядов по возрастанию
- Для каждого интроверта пишем номер очередного свободна ряда и добавляем его в стек
- Для каждого экстраверта пишем последнее число из стека и удаляем его оттуда
982C - Cut 'em all!
Заметим, что если есть какое-то ребро, которое можно удалить, то мы можем сделать это, без каких-либо последствий. Рассмотрим такое ребро, что в одном из полученных поддеревьев уже точно нельзя удалить больше, а его удаление возможно. Что произойдет, если мы его оставим в дереве? Относительно другого конца ребра четность поддерева не изменилась, что означает, что на дальнейшие удаления это ребро не повлияло. А значит, если мы его удалим, то ответ улучшится.
Отсюда следует жадное решение: в дфс-е насчитываем для каждой вершины размер поддерева, включая текущую вершину, и если он четен, то ребро в потомка (если он существует), можно удалить.
982D - Shark
Давайте посортируем массив и будем вставлять числа в порядке сортировки от меньшего к большему. Используя структуру данных "Система непересекающихся множеств" можно легко поддерживать информацию о текущем количестве отрезков, а также используя map внутри функции объединения, и информацию о текущих размерах отрезков (локаций). Тогда остается лишь обновлять ответ, когда это требуется.
982E - Billiard
Если симметрично отражать прямоугольник на плоскости относительно своих сторон, то новая траектория движения шара окажется куда проще. А именно — прямой. Одно из возможных решений такое:
- Если вектор направлен под углом в 90 градусов к осям, то пишем if-ы.
- Иначе поворачиваем поле таким образом, чтобы вектор удара стал (1, 1).
- Выписываем уравнение прямой движения шара: – 1·x + 1·y + С = 0. Если подставим изначальное положение шара, то найдем коэффициент C.
- Заметим, что в бессконечно замощенной плоскости координаты любой лузы представимы в виде (k1·n, k2·m).
- Подставим координаты лузы в уравнение прямой шара. Получается диофантово уравнение A·k1 + B·k2 = C. Оно разрешимо в случае, если C | gcd(A, B). В противном случае решений нет.
- Из всех решений данного диофантово уравнения нас интересует наименьшее на положительной полуоси.
- По найденным k1, k2 легко получить координаты соответствующей им лузе
- Повернуть поле обратно, если требуется.
982F - The Meeting Place Cannot Be Changed
Предположим, что решение существует, и будем искать решение исходя из этого предположения. В конце проверим найденное решение за линию, и если оно решением не является, то предположение было неверно.
Пусть решение существует. Значит пересечение всех циклов не пустое. Возьмём один любой цикл, который назовём главным. Можно представить его как окружность с направлением по часовой стрелке. Отметим на этой окружности все искомые вершины, принадлежащие всем циклам.
Рассмотрим только циклы, которые выходят из вершины главного цикла, приходят в какую-то вершину главного цикла, а дальше движутся по главному циклу и замыкаются. Если цикл выходит из главного цикла, то он должен на него вернуться где-то дальше по направлению главного цикла, при этом не перескакивая отмеченные вершины с ответом (иначе будет пустое пересечение, а мы предположили, что не пустое) (считаем, что если цикл вернулся не по главному циклу туда же, откуда вышел, то он совершил скачок длинной весь главный цикл, а не 0). От вершины, в которой рассматриваемый цикл возвращается на главный, до вершины, из которой он выходит с главного, проведём дугу в направлении главного цикла. Те вершины главного цикла, которые такая дуга не покрывает, заведомо не могут являться ответом. Пересечение всех рассмотренных циклов с главным определяется пересечением всех таких дуг.
Мы не рассмотрели только циклы, которые несколько раз выходят с главного и несколько раз возвращаются на главный цикл. Но пересечение такого цикла с главным циклом будет таким же, как если пересечь отдельные циклы между соседними выходом/возвратом. Поэтому такие сложные циклы можно не рассматривать.
Теперь нужно отметить все дуги между возвратом-выходом с главного цикла. Для этого будем запускать dfs из всех вершин главного цикла и пытаться вернуться на главный цикл как можно дальше (расстояние измеряется по количеству вершин главного цикла между выходом и возвратом). Как было отмечено выше, циклы, выходя и возвращаясь, не могут перескакивать ответ. Значит все dfs'ы, стартующие между границами ответов, стремятся к какой-то вершине главного цикла, которая является граничной в дуге с возможными ответами. Значит если в одном dfs'е мы выбрали самую удалённую вершину из нескольких вариантов, то в другом dfs'е рассматриваемые варианты не поменяются ролями, и старая самая удалённая вершина так и останется самой удалённой среди тех же вариантов в новом dfs'е. Значит можно запускать все dfs'ы с общим массивом used, в котором кэшировать самую удалённую вершину.
В итоге решение сводится к тому, чтобы найти главный цикл, отсортировать его вершины по направлению обхода, запустить из них из всех dfs’ы с общим массивом used’ов, между стартом и финишом всех dfs’ов отметить дуги и пересечь их все, на пересечении всех дуг взять ответ. Если после удаления вершины-ответа в графе не останется больше циклов, то это действительно ответ, а иначе предположение было не верно и ответа не существует.
waiting translation~
I have a slightly different solution for E. We notice that the movements along the X and Y axis are independent. Therefore, instead of solving a 2D problem, we have to solve two simultaneous 1D problems.
We notice that for the X dimension, if the ball first hits a margin of the table at time
x_i
(which will be either equal tox
or ton - x
, according to the direction of the X speed vector), then it will keep hitting the edges at timesx_i + t * n
, wheret
is a non-negative integer. We judge the same for Y. The solution of the problem is found when both axis hit an edge at the same time (therefore, a corner). So we need to solvex_i + t_x * n = y_i + t_y * m
.Can you explain how to solve the last equation I am having hard time solving it
It's a classic problem, Linear Diophantine Equation. You then have to bring the solutions to positives, you can check out my submission to see how I did that (there's probably multiple ways).
This is a great way to solve it, thank you very much!
Hope that translation will come soon, I have been waiting for the solution that I can understand one day long.
try google translate extension to translate the page
I don't think google translate is good, I can hardly understand the translation by the google translate.
It seems that the English version has been disappeared. o(╥﹏╥)o
I'm sorry for taking so long. It has happened because of onsite contest in another city.
I think D requires more explanations.
D has very simple solution required sort O(nLog(n)) and linear O(n) operations:
1) sort given array with indexes, i.e. sort b[] = pair(a[i], i ).
2) i = 0 .. N-1, add b[i].second to set of intervals - it's required O(1) operation:
Let Left[i] - indicated left index of interval which end point is i.
Let Right[i] - indicated right index of interval which start point is i.
so when add 'u' element to set of intervals, only required update L[u], R[u], Left[u-1] and Right[u+1].
``
3) Let cur_i - number of intervals, cur_l - length of last interval, max_l - maximum length of interval's, max_i - number of such maximum intervals.
` if cur_i == max_i -- so all interval's have identical length.`
See solution 38374571 (Note: This solution is not my own idea).
please elaborate your approach!! Still not clear
For example:
We have 7 10 4 5 numbers
indexes: 1 2 3 4
1) build index pair array : (7, 1) (10, 2) (4, 3) (5, 4)
2) sort (1) array : (4, 3) (5, 4) (7, 1) (10, 2)
3) we have empty interval set: {}. or imagine no colored line: 0 0 0 0.
4) take first element: (4,3) index is 3. to color line[ 3 ] position. line: 0 0 [ 1 ] 0 - number of intervals = 1. length of last interval = 1, number of longest intervals = 1. --> update answer.
5) take second element: (5, 4) index is 4. to color line [ 4 ] :
0 0 [ 1 ] 1 -- as you see, left side of 4 also colored, so colored interval will be: 0 0 [ 1 1 ]. - number of intervals = 1 , length of last interval = 2. number of longest intervals = 1, -- update ans.
6) take third element: (7,1) index is 1: to color line [1] :
[ 1 ] 0 [ 1 1] -- number of intervals = 2, length of last interval = 1. number of longest intervals = 1 (think about).
7) take last element : (10, 2) index is 2: to color line [ 2 ] :
[ 1 ] 1 [ 1 1 ] -- as you see, left and right side also colored, need increase left side and right side, line will: [ 1 1 1 1] - number of intervals = 1. number of longest intervals = 1 --> update ans.
thanks for your explanation. great job!!
Is there anyway to sovle D using Tenary Search. As i did i tenaried the K,but i came into a problem that the graph may have the plain field where alot of K satisfied the answer, so how can we solve this or this way is just invalid ?
You can't apply any searching algorithm, because there is no available convex or covariance function with k from 1 to inf.
Can we solve C using DP?
Can C be solved using DP?
I think, To find the number nodes in a subtree of a node is a DP.
Because we use previously computed results and don't repeat it !!
Which is I guess DP, isn't it?
Correct me if i am wrong. Or tell, if there is another interesting solution using DP or anything.
AGrigorii The tutorial/Editorial is not linked up with the problems.
waiting the code link of every problem.
I dont get why cant we put a person of left most and right most seats?
Can someone explain the question D alomg with the sample test cases?
The English contest doesn't link to the announcement or this editorial. I had to switch to Russian to find this blog. Please fix it, thanks.
thx. Fixed
for problem shark ,why can't we take k=1 every-time and hence all conditions are satisfied this way?
we need to maximize the segments created with a given k.
For k=1 every element in array will be one segment hence there will be n segments maximum
The travelling day is not considered a segment. Eg 1 2 3 3 3 3 2 1 , K=3 , number of segments are 2
OK thanks
Can someone explain D problem more clearly and detailed please?
if ((double)clock()/CLOCKS_PER_SEC>0.95) break;
Why this line is used in prpblem F??can anyone explain.. why selecting any node as root gives the same number of even subtrees? what's the proof?