А CFR129 давно был? И в нем анонс еще раньше сделан.

Он будет утром... если сейчас не анонсировать кучу народа может просто подумать что контест завтра вечером и проспать (вообще наверное это надо было напомнить в топике).

Why have negative votes,He is true.

There is dynamic scoring. Read this for more information: http://mirror.codeforces.com/blog/entry/4172

and have fun!

У меня один взлом на 1 1.

Меня на 1 1 =) я в цикле перебирал второе число до r — 1

translate from google: Explain, please, D div 2) more than an hour spent on it (

Hint: use Euclidean algorithm.

Think backwards: if a>b then (a, b) -> (a, b-a)

Это просто комменты на русском языке в непонятной кодировке. Обфускации тут нету.

С чего вдруг? У человека кодировка другая, комментарии вообще тебя не должны касаться.

А вот такое? http://mirror.codeforces.com/contest/218/submission/2027717

See this one and this.

Может тогда дашь пару хинтов по решению?

Wish meret would write the editorial.

I use UFS in this problem.I think this problem is very flexible,and there's more than one way to solve it.

shater -_-

UFS is a better choice.

Количеством ошибок считается кол-во пар рядомстоящих символов, которые одинаковы.

Вы не поняли, как авторы определили понятие "ошибки"

ответ это количество пар одинаковых соседних символов, а не количество расхождений с правильной последовательностью

Хаха, я ведь понял условие точно так же. Впрочем, все равно не знал, как решать.

You can use DSU.

Just wrote a code that solves it without explicitly involving graphs: 2031563

The idea is the same as in the graph solution, you just assign each point to a group as you process the input (creating a new group when a point you just added has no other reachable point), and if necessary merge groups if a point is found that merges some groups together. The result is the amount of groups minus 1.

Чтобы соединить n вершин в целую компоненту связности, нам же надо n-1 ребро. А, ставя сугроб в этой задаче, мы, как бы, проводим ребро. Значит ответ на ваш вопрос : "нет"

Нет, такого случая не существует.

Maybe problem is in stack size, because you use recursion.

Here, on CodeForces, stacksize is increased for g++ using compilation string

I feel your pain.

Это правильно. Нужно лишь правильно найти компоненты связности.

(1, 1) (2, 2) (2, 1) (1, 2)

Если добавлять по очереди, алгоритм даст 2 компоненты.

Ломал похожее решение, выше уже ответили, почему это не так. Количество компонент связности нужно было искать как количество компонент связности в графе, в котором ребра имели сугробы с одинаковыми x или y, то есть построить граф, а затем пробежаться несколькими поисками в глубину, или же как количество различных множеств в системе непересекающихся множеств, построенном по аналогичной схеме, что и граф, что почти тоже самое, но немного по-другому реализованное — здесь ты сразу все вершины из компоненты объединяешь во множество и таким образом тебе, как в первом случае, не придется бежать по этому всему поиском в глубину, а можно сразу выдавать ответ.

Вроде бы это верно. По крайней мере верно такое решение: считываем x, y. Если не было такого x, то увеличить ответ на 1, если не было такого y, то увеличить ответ на 1. И в любом случае вычесть 1. Если я понял, ты это и имел ввиду. Но только массивы нужно сделать размеров в 10000 элементов, а не 1000. Потому что координаты до 10^4.

To the opposite, it was really hard for me to compete here, in Russia, because of that awful Saturday morning:( I wish next time morning-contests would be held one or two hours later — just to have a good sleep... please!:-)

I have solved the problem.

you need idea? or to know how solved problem?

• to solved problem E link here
• and problems official tutorial(ideas) is not public but is 5 different accepted solution,which i think help you.

authors and solutios:

• xim97 _ 2032857
• ACRush _ 2029369
• neex.emil _ 2033123
• panyuchao _ 2028007
• hza _ 2033918

C (div1):

Основная сложность этой задачи, это найти, при каких условиях можно определить вид каждой колонии, а при каких нельзя.

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

Если первый вариант не выполняется, то рассмотрим более общий. Колонии можно определить, если выполняется следующее условие:

f (x1, x2, .. xn) != f (!x1, !x2, .. !xn), где x1, x2 .. xn — некоторые значения литералов (0 или 1), f — наша функция.

Допустим, существует такие x1, x2, .. xn, удовлетворяющие условию выше. Мы можем записать следующее:

f (0, 0, .. 0) = f (1, 1, .. 1) = f (x1, x2 .. xn) != f (!x1, !x2, .. !xn).

Мы можем предположить, что все x = 1 это одна колония, а все x = 0, это другая колония. И перебирать все комбинации двух колоний. Тогда у нас может получится один из 4-х вариантов, описанных выше. Если мы получили значение функции f (!x1, !x2, .. !xn), то мы сразу же можем определить вид наших двух выбранных колоний, а определить вид остальных колоний уже дело техники. Ну и следует заметить, что значение n нам вообще не важно, главное что оно >= 2 и что не все колонии одинакового типа.

Суть идеи помогает понять 3-й сэмпл. Для всех значений комбинаций литералов, выпишите значения функций. И вы найдете как раз ту самую, нужную нам 4-ку.

Теперь, как непосредственно технически решить задачу. Нужно распарсить наше выражение в дерево разбора, вершина это либо литерал, либо операция. У каждой вершины у нас будет не более двух сыновей. Мы можем запустить динамику по нашему дереву следующую [номер вершины][значение вершины при f (x1, x2 .. xn)][значение вершины при f (!x1, !x2 .. !xn)] = может такое быть / не может такое быть.

А пересчитывать совсем просто. Нужно брать значения двух наших сыновей у вершины и делать ту операцию со значениями f левого сына (x1 , x2 .. xn) и f правого сына (x1, x2 .. xn), f левого сына (!x1, !x2, .. !xn) и f правого сына (!x1, !x2, .. !xn), которая и стоит в этой вершине.

Ну и если мы в итоге можем получить в корне: d[корень][0][1] = true, или d[корень][1][0] = true, то очевидно, мы сможем подобрать f (x1, x2, .. xn) и f (!x1, !x2 .. !xn)

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

Думаю, не слишком понятно объяснил, но главное вкурить первую часть, а дальше можно и самому догадаться.

It sufficient to look at the subsets of size 1 or 2, instead of all subsets of colonies {c₁, ..., c_n}.

Replace each '?' by either c_i or c_j, i and j being arbitrary for now. Look at the values in the four cases (c_i, c_j) = (0, 0), (0, 1), (1, 0) or (1, 1).

For example, for (c_i&(c_i&c_j)) we would get 0, 0, 0, 1. Note that there's only one way to get 1.

• If a "3 versus 1" or "1 versus 3" can happen, then choose the right i and j, and the answer will be "YES".
• If a "2 versus 2" of the form 0, 0, 1, 1 or 0, 1, 0, 1 or 1, 1, 0, 0, or 1, 0, 1, 0 can happen, you can deduce c_i or c_j, the answer will be "YES".
• If none of those situations happen, the answer will be "NO".

This is how I did it in the code of the message, for some reason the system replaces it with the enumeration that you see.

Here