Не сложная задача на перебор. Переберем параметр a. Если 12 не кратно a, пропустим. Вычислим b = 12 / a. Переберем столбец (от 1 до b) и для всех его клеточек (i, j) проверим, стоит ли там X. Клеточка (i, j) — это ((i–1) * a + j) -ый элемент строки.
400B — Инна и новая матрица конфет
В остаточной постановке задачи выбираются все линии, в которых еще не победили. Если есть строка, где гномик уже правее конфеты — ответ -1.
Иначе, ответ – количество разных расстояний, так как за один ход убиваются все расстояния минимальной величины.
400C — Инна и гигантская матрица конфет
Заметим, что повороты по часовой можно брать по модулю 4. Горизонтальный — по модулю 2, а против часовой — по модулю 4, причем 1 такой поворот — это 3 поворота по часовой.
Поворот по часовой: newi = j; newj = n–i + 1 не забываем swap(n, m).
Поворот горизонтальный: newj = m–j + 1
Если расклад правильный, то после удаления всех ненулевых ребер наш граф распадется на компоненты соответствующих размеров. Проверим это. Да, заметим, что вершины пронумерованы, так что необходимо проверять, что из запустив дфс из первой вершины каждого типа, мы получим ровно все вершины нашего типа (их номера и кол-во нам известно) и никакие другие.
Теперь можем запустить обычного флойда-уоршала, поставив в матрицу смежности для двух компонент наименьшее из рёбер, ведущих из одной компоненты в другую.
Будем решать задачу побитово. Зафиксируем какой-то бит. Поставим числу 1, если бит имеется, и 0, если нет. Получили последовательность, к примеру, 11100111101.
Возьмем кучку из последовательных единиц, для нее бит войдет в операциях над каждым из этих чисел на первом этапе, на втором, и на этапе с номером размера кучки.
Осталось научится поддерживать модификацию. Для каждого бита будем держать сет кучек из единиц. При «выпадении» бита, одна кучка либо распадается на две, либо уменьшается на 1. При добавлении, одна кучка появляется, либо вырастает на 1, либо две соседние кучки срастаются.
Тест из задачи B (присутствующий в наборе тестов для проверки решения) :
Но правильный ответ 2: вначале выбираем 3 и 4 строки, потом 1,2,3.
Приходил следующий клар: "В задаче B была ошибка в условии. Вы должны выбрать все строки, в которых гномы стоят не в конфетах на своем ходу. Сейчас условие правильное. Наши извинения за неправильное условие."
Небольшое замечание по поводу D. распадется на компоненты соответствующих размеров. Проверим это. — разве это будет работать? Нам нужно проверить, что все бактерии одного цвета — не в разных компонентах, т.е. использовать DSU или один DFS в конце; но реально граф может вообще в одну компоненту срастись, что нам скажут размеры компонент связности?
По поводу В — как решать оригинальную задачу (ту, в которой можно выбрать подмножество строк)?
В условии задачи С x раз повернул по часовой, затем y раз горизонтальный поворот, а затем z раз против часовой стрелки.
Возьмем из теста задачи конфету с координатой(1,1) и произведем преобразования
123 123 123 123
1к.. 1..к 1... 1...
2... 2... 2... 2...
3... 3... 3..к 3к..
затем горизонтальное преобразование
123 123
1... 1...
2... 2...
3к.. 3..к
и последнее против часовой стрелки
123 123
1... 1..к
2... 2...
3..к 3...
По условию задачи координаты вводятся xk, yk. Выводить их надо в таком же формате x y? У меня получается координата xy (1,1) дает (3,1) а в тесте (1,3) не могу найти ошибку.
x — номер строки, а y — номер столбца, сам по привычке спутал с ориентацией стандартных X и Y на плоскости
Так в чем тогда изюминка задачи? В том что в ней x и y поменяли местами?
В том, чтобы сделать то, что написано в условии задачи. X и Y тут не причем, это лишь невнимательность при реализации.
Сделать то, что сказано подходит для задач A, а для задач С надо что нибудь поинтереснее. Хотя глядя на то, как уменьшается количество участников решивших задачи, в зависимости от сложности, она вполне подходящая.
Вероятно, многие сидели на неправильном B и просто не дошли до C. Согласен, что на C задача не тянет.
Возможно если бы это было так просто сделать, то она бы и не была на этом месте. Как видно не все с легкостью реализовали это, в том числе я
Когда ответ No в задаче D? никак не могу понять(
Когда в группе бактерий одного типа нельзя добраться от любой бактерии до любой за бесплатно.
Я уже понял, спасибо) Есть вопрос: у меня не проходит мое решение 41 тест. Когда я просто заифил его, оно прошло. Подскажите, в чем баг? http://codeforces.net/contest/400/submission/5945704 http://codeforces.net/contest/400/submission/5945671
Вот здесь бага, при инициализации DSU. Там на самом деле элементов N (по одному на бактерию), а не K (по одному на цвет), а при такой инициализации элементы 502...100000 сразу в одной компоненте (у них у всех parent[i]=0).
упс, да, спасибо, задумался, наверное, вот и накосячил ещё раз спасибо!
Моё решение задачи D было взломано 5942167 , но на дорешивании оно получило вердикт полное решение 5948769. Получается, что тестов недостаточно, чтобы проверить правильность решения?
Ну да, так бывает.
Возможно у Вас какая-то ошибка, которую не предусмотрели авторы...
Смотри внимательнее вердикт. Solution verdict: TIME_LIMIT_EXCEEDED
Во время контеста сервер сильнее загружен.
Но ведь решение действительно не укладывается в TL. К тому же, мне кажется, что загруженность сервера не повлияла бы на верное решение.
Problem "A" using Perl regular expresions 5953657 (more clear 5953597). Idea: to find in a row these combinations of symbols: 1) X, if you find X, then it makes column in 1x12, 2) X.{5}X, if you find X + 5 any symbols + X, then it makes column in 2x6, 3) X...X...X, X + 3 any sym + X + 3 any sym + X, then it makes column in 3x4, and so on.
Problem "B" using regexp — G\**S. I use the length of match of regexp, and make set. Answer is number of elements of set. (Perl 5953796).
i got one WA on problem C because i forgot to
swap(n,m)! this was a good thing "hidden" in the problem statement!Буду благодарен, если кто-нибудь объяснит как реализовать вторую часть разбора (модификация) задачи E. Не могу представить как это сделать с помощью set.
Вроде можно сделать так: для каждой кучки возьмем самую левую единицу и позиция в которой она стоит — ключ этой кучки, а кол-во единиц — значение. Построим дерево поиска для ключей с значениями. Теперь модификация : нужно найти такой ключ, чтобы он был максимальным среди всех, которые меньше позиции, где происходит обновление. Спустимся по дереву пока можно, то есть найдем такой ключ, найдём следующий за ним. теперь по 2 ключам и значениям можно делать модификацию: объедение, распадётся, +-1 к значению, добавится или пропадёт кучка. Построение за линию, модификация за логарифм.
Спасибо.
Is the explanation for 400D correct? I get WA for the below test case when I implement a solution as described in tutorial.
"be sure that we receive exact all nodes of this type and no ohter."
Even I think that the statement "be sure that we receive exact all nodes of this type and no ohter." does not hold.
it is possible to reach from 1 to 2 via zero weight path (1->3->2), so as per question
"Dima's Chef (Inna) calls the type-distribution correct if there is a way (may be non-direct) to move energy from any bacteria of the particular type to any other bacteria of the same type (between any two bacteria of the same type) for zero cost"
Or you can use dsu for all nodes which can be reached via zero weight path and check whether the representative of kth category is the parent or not.
Here's my solution: 38347316
"no other" part is wrong
Couldn't understand B clearly :( can someone help me?
yeah I am also unable to understand the first sample test case.
could someone please explain ?
What is wrong with my solution to Problem E
Your
numbers.
buildfunction is somehow invalid. Would you mind explaining your approach? As far as I can tell, you are using segment tree to calculate SUM and AND over entire array. This confuses me. The problem asks you to take AND on multiple "layers". So if the array has length N, then you must output sum ofBesides, in this problem answer can be as high as
, which exceeds
int.as I understood from the problem statement, the first layer contains the N elements I read from the input.
For each new layer I should apply AND operation between every two consecutive numbers and add the result to the new layer's sequence.
The final answer is the sum of all elements in All layers.
so when calculating values of the tree, for each individual element of the first layer, the answer is the element it self.
Then for each node I will merge the left and right child with these steps:
1- Add the sum of all elements on the left and right children.
2- Take the result of AND between the left and right children and add it to the result.
3- Now if neither one of both children has one element then you have a missing element in the new sequence which is the AND operation between the right most element of the left child and the left most element of the right child, I'll add the result to the sum.
Example on the 3rd step:
1st layer: 1 1 1 1
you will notice that there are two nodes will be merged together, a node with the first two elements and a node with the last two elements, but the resulting node will be missing the AND between the two elements in the middle, so I have to handle this case.
but in given test case: 1 1 1
you will have a node with the first two elements and a node with last element
and the result in the upper layer will have no missing elements.
the same steps are applied in the update part.
ok I got where I was mistaken, No I thought of another Idea, I will complete the array of the first layer to the next power of 2 so I wouldn't have any individual element in any other layer except the last one, and I'll set 1 to each valid element and 0 to any other.
Then the merge step will depend on the element if its valid or not, because in my first approach some if you have an array of 5 elements the last one will be presented in two layers and must be counted twice.
will the above suggestion fix this problem ??
Solution of problem D is wrong, this:
"If the distribution is correct, after deleting all ribs with cost more than 0 graph will transform to components of corrects size. Also, the nodes are numereted so we should turn dfs for the first node of each type and be sure that we receive exact all nodes of this type and no other."
Should be:
"If the distribution is correct, after deleting all ribs with cost more than 0 if we do dfs for the first node of each type we must visite every node of the same type."