haha,friend,You are very speedy.

Надо будет зайти в гости)

Подожди меня, нам по пути.

Пацан сказал — пацан сделал.

No, hardly every contest. Count contests per year and think: could there really be so many existing calendars?

what about other rounds you still wish same thing

Since you know that, so it won't be surprising ;)

Ночь, ледяная рябь канала,
Аптека, улица, фонарь.

I was going into BIT ideas, Then I thought that why is GF(2) given, find solution was really cute =D

Div1-A/Div2-C, aka "how to solve a problem while ignoring over half of the input". Pretty nice :P

Чисто за n² + nq не подразумевалось. За (n² + nq) / 32 — может быть. То решение прошло тесты?

Ok, i just solved it.

Stack works when you can't see a hill again after removing it, which doesn't work in this case.

The LCA is correct (that's pretty easy to see). To find the next hill a climber goes to from hill i, you add the points from right to left, remember the top convex hull (well, it's actually a concave curve, but it uses the same idea as convex hull algorithm) of these points, update it when adding points and always pick the leftmost point in the hull so far (after the just added point, from which the climbers go to the next point of the hull). This can be done using vector cross product — as long as the leftmost 2 points of the hull (if they exist) are placed in such a way that the leftmost one is below the line from the just being added point to the one to its right, you remove the leftmost point of the hull — because it won't be in the top convex curve ever again. It works the same way as the standard convex hull algorithm.

Another contest where D appears simpler than C. At least to those who are used to more algorithmic problems — like me :D. Too bad I missed the start of the contest (thanks to the modern world's stupid shopping obsession), I think I could've done well.

And I am probably going to fall at my lowest rating in the last 2 years or so. Last two contests have been miserable for me. Making a lot of silly mistakes, I dont know what has happened. :( T_T . But both of these contest had very exciting problems.

Вывод по одному символу. Такие решения у нас работали по 4 секунды.

раскрой скобки в выражении

там получится что ответом является сумма произведений диагональных элементов

Изначально скажем, что этот "предок" — первая справа гора, если такая вообще есть.

Далее будем делать итеративный "подъем" — если наш предок не закрывает видимость на своего предка, то делаем нашим предком предка нашего предка. Иначе останавливаемся. Фактически в задаче от нас требуют выпуклую оболочку — и этот алгоритм проще понять, представив его, как построение выпуклой оболочки.

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

cin/cout does usually works longer than printf/scanf...

use read/write instead!

Each operation on cin flushes cout by default. Use cin.tie(NULL); to prevent this.

Чем же подозрительных?

Там нет формулы. Просто если увидеть, что каждое произведение по сути встречается дважды

В итоге получается сумма произведений диагональных элементов, что в свою очередь является просто суммой диагональных элементов. Произведения всех остальных пар производятся дважды и дают в результате либо 0, либо (2 * 1) % 2 = 0, стало быть, их можно не учитывать вовсе.

Очевидно [прямо из условия следует], что ответом на задачу будет

(tr(A^2)) mod 2

По свойству следа матрицы получаем:

tr(A^2) mod 2 = (tr(A)*tr(A)) mod 2 = tr(A) mod 2

UPD: Пояснение здесь

матрица a размера n*n

скобки

(a(1,1)*a(1,1)+a(1,2)*a(2,1)+...a(1,n)*a(n,1))+(a(1,2)*a(2,1)+a(2,2)*a(2,2)+...a(2,n)*a(n,2))+ ...

(a(n,1)*a(1,n)+a(n,2)*a(2,n)+...a(n,n)*a(n,n))

скобки по строкам — отбрасываем(они не влияют)

получаем ситуацию, когда каждая пара произведений (кроме a(i,i)*a(i,i)) встречается по два раза их сумма всегда ноль(1+1=0б 0+0=0) остаются пары: a(1,1)*a(1,1)+a(2,2)*a(2,2)+...+a(n,n)*a(n,n)=a(1,1)+a(2,2)+a(3,3)

Ну а каждое изменение матрицы меняет только одни диагональный элемент. всё

По сути, нам нужно посчитать . Сразу можно видеть повторения. :)

Спасибо... :) Рад, что наш контест в ПТЗ понравился.

Чтобы запретить оптимизированные решения за n² + nq, в общем.

Rating updated just now. +26 :p

global array overflow will not lead to runtime error(if only a little), but local one does. overflowed parts may not be initialized correctly.

UPD overflowed 2-dimensional array will get wrong answer. See the implementation of 2d arrays: the i+1-th row is placed right after the i-th row. So if you write overflow data in i-th row the result is the data in i+1-th row is modified.

When you do something wrong in C++, you don't get a runtime error. You get undefined behavior, and today you saw one of the many ways how it can behave.

The editorial will be posted tomorrow, we are working on it!

Maybe you have copied the solution or commented about the solution outside

I had a similar solution which failed on case 50. Weirdly, converting everything to long long got AC.

Аналогично

меня не только выбрасывало но и язык на английский меняло

I think this rule only means that there are no penalties for a compilation error or failed on pretest 1 ...

However, I think it is quite fair to get your rating changed, cause u actually tried to solve a problem during the contest ...

Построим дерево обхода. Запустим рекурсивную процедуру, которая будет разбивать все ребра в поддереве (в том числе обратные ребра, которые начинаются в поддереве) на пути длины 2, возможно, используя ребро, входящее сверху в корень поддерева. После рекурсивных вызовов для детей непристроенными будут только некоторые ребра, инцидентные корню поддерева; в зависимости от четности, либо берем ребро наверх, либо нет.

Собственно, явно дерево строить не нужно, можно за один ДФС все сделать.

Я не знаю, как рассуждал Endagorion, поэтому опишу свою цепочку рассуждений (решение в итоге получается идентичное):

1. Ориентируем ребра произвольным образом. Условимся, что объединять в цепочки мы можем только те ребра, которые входят в одну вершину.
2. Некоторые вершины имеют нечетную входящую степень. Если мы проведем между двумя такими вершинами путь и развернем все ребра на нем, их входящая степень станет четной, а входящая степень всех остальных вершин на пути не изменится.
3. Из предыдущего пункта очевидно, что путь нас устраивает абсолютно любой. Давайте же будем искать его на произвольном подвешенном остовном дереве.
4. Заметим, что развернуть все ребра на пути между двумя вершинами — это то же самое, что и развернуть все ребра на пути до корня от каждой вершины.
5. Соответственно, данное конкретное ребро будет развернуто тогда, когда в поддереве, куда оно ведет, нечетное количество вершин с нечетной входящей степенью.

Итого, моя реализация — DFS для разворачивания ребер и восстановление ответа циклом.

Будет завтра.

Maybe it makes sense to integrate your statistics into codeforces instead of creating a blog?

Just now I translated my code into c++, and I used "scanf" for console input.It passed.

I used BufferedReader in java (Scanner will not do with 1000000 lines) and it worked perfect.

By the way I see no solution with BufferedReader among your 3 submissions.

Many Java coders use a self-written FastScanner class or something similar. For implementation details please look at any of my submissions.

me too

Read it, I say now. :)

For those, who didn't find it — see the tutorial Here :DD Thanks gen for the excellent round! :)))

The Style and the format of problems were very interesting (especially prob. C and D in div. 2)! I liked the problem statements, they were very clear and easily understandable.

Maybe the only thing that I didn't like so much, is that there was little opportunity of hacking someone's solution, maybe for some of us it's good, but I think that passing the pretests almost meant passing the System Testing.

But, in general I hope seeing more this kind of rounds here at CF. It can serve as an ideal example for the upcoming contests. We are waiting for other, even more interesting and challenging problems!

Thank you for the hard efforts ! :)

I liked that the authors messed with my head in Div1 B/Div2 D by making an example where |X| did not equal |Y| (because one term was 0 and could be omitted), and then writing

instead of

Thanks for organizing the round. I tried to solve problems A-C in Div1. Problem C was excellent: a "natural" problem and a very clear problem statement. Problems A and B were also interesting, but they were somewhat difficult to understand due to the complex problem statements. In addition, it's not nice when cin and cout are too slow (and warning about this makes the problem statement even longer) — maybe it wouldn't have been necessary to use so large test cases.

I think div1 problems (A-D, I don't know how to solve E so far) are really awesome. Thank you for the contest.

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

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

С другой стороны: если, например, в претестах 5 и 6 соответственно ограничения 10000 и 100000, большой ли смысл ускорять решение, которое не работает для 10000 только до такой степени, чтобы оно свалилось на 100000? Скорее, лучше сразу получить информацию, что решение не проходит во время в худшем случае (то есть макстест).

http://codeforces.com/contests/407,408