Привет всем! Я автор задач сегодняшнего раунда. Меня зовут Артур, я учусь в лицее №31 города Челябинска.
Благодарю Gerald за координацию подготовки контеста, Delinur за перевод условий, MikeMirzayanov за замечательную систему, dolphinigle за прорешивание контеста, вычитывание условий и множество ценных советов, fdoer, grey_wind, Skird и alger95 за помощь в придумывании задач.
Пока ничего практически полезного сказать не могу. Как вы, надеюсь, догадались, контест пройдет в каждом дивизионе отдельно. Система подсчета очков будет стандартная, разбалловка, скорее всего, нестандартная, пока не знаю, какая именно, ближе к делу напишу.
Объемных фабул и историй не будет. Надеюсь, что контест и задачи вам понравятся и все пройдет гладко.
UPD: Разбалловка следующая:
В первом дивизионе: 500-1000-2000-2000-2500.
Во втором дивизионе: 500-1000-1500-2000-3000.
UPD2: появился разбор Пока частичный и на русском. скоро будет больше.
Поздравляю победителей, особенно решивших задачу D.
Div1:
Div2:
How can I register as virtual contestant?
Now you can only register as real contesant. There is no way to register out of competition.
А в письме про раунды они по прежнему beta:
Wow, dolphinigle as the tester? I would expect clear problem statements and a stable, rated round then :)
I agree. He always explains everything clearly in all of his problem statements. :)
the contest will be interesting if the scores for tasks are unusual. And I hope the contest be rated.
Ну так какая все-таки разбалловка?
P.S. Уже добавили, спасибо.
And the score distribution is... :-?
is ... published
Division 1: 500-1000-2000-2000-2500
Division 2: 500-1000-1500-2000-3000
it is writen now.
Can anyone give me a formula that can count new rating? Thanks very much. :-)
The formula is not public.
Закончилось... На чем С(div 2) ломали?
1 3
###
4 4
UPD : че-то криво скопировался тест.
Исправлено.
.##
###
.
на этом
5 5
..###
..#.#
#####
#.#..
###..
Решение проще некуда, жаль понял это слишком поздно. Если есть точка сочленения, то ответ 1, если нет, то ответ 2. Ну и если вершин меньше трех, то ответ -1.
наверно у кого-то слетит задача)
5 4
####
####
...#
####
####
Взломал 13 человек на этом
еще на
но таких меньше
Лично меня поочереди сначала вашим, потом моим сломали.)
Ну тех, кого я ломал этим(а потом и меня) выломал tourist тоже(чем то в духе вашего)
в C у всех Гаусс?
Можно было руками решить систему из трёх уравнений, не?
Как из трех? Я умею из шести.
Вообще говоря, у меня 4 переменные и четыре уравнения. Но четвёртую переменную лично мне проще перебрать одним циклом, чем впихивать в систему.
А можно поподробнее про переменные и уравнения?
Ниже ответил al13n'у.
у меня из 7, как из шести?
Переменная — сколько раз взяли какую-то четверку символов (7 осмысленных четверок — 7 переменных). Числа из инпута — правая часть системы (соответственно, уравнений 6).
еще одно уравнение, учитывающее общее количество, не?
Можно вместо этого взять одну из этих за свободную и перебирать ее, выбирая руками лучшее решение.
логично, но не суть важно в целом =) все равно прошла
Почему из трёх, а не шести?
Мое решение с бинпоиском по длине ответа, вложенным перебором еще одного параметра и внутри Гауссом с 8 переменными больше не выглядит так хорошо:) Можно поподробнее?
WolframAlpha же
Хех, а как Гауссом? Там же недоопределённая система, и надо в целых числах и что-то минимизировать — т.е. искать целую точку на гиперплоскости, минимизирующую какой-то функционал....
Одну переменную перебираем, потом гаусс и проверка на целочисленность решения.
Я писал, добавляя еще одно уравнение на сумму, собственно перебирая ее. Не успел отдебагать. Кстати, ЛНЗ уравнений в моей системе вообще верный факт? Похоже, что верный)
P.S. как можно было посеять столько багов?! О_о сдал после часа мучений..
У меня сначала гаусс в целых числах, выражающий 6 перемнных через седьмую, свободную, потом перебор значения свободной (от 0 до 100 тысяч). Чтобы обойтись без дробных результатов делений, перед вычитанием строк домножаю обе строки, чтобы в ведущем столбце оказалось LCM. Правда, на самом деле там получаются максимум двойки.
Может я чего не понимаю? Почему нельзя сказать, что нулевая строка принудительно состоит из 'a'. Тогда сразу мы знаем количество букв 'b' в первой, второй и третьей.
Также мы знаем, сколько 'b'шек в пересечении каждых двух из них. Казалось бы, теперь нужно всего лишь оптимально уложить 'b'-шки в строчках, это делается за один цикл. Что я упустил?
Я решал именно так (и в итоге зашла), но но за один цикл уложить b-шки у меня не получилось: например, для теста из примера существует еще такой ответ:
aaaaaaaa
bbbbaaaa
aabbbbaa
aabbaabb
Так что там все-таки нужно делать один перебор внутри.
Как делал я (можно посмотреть сюда: 1757176). Я нашёл количество общих 'b'-шки у первой и второй строки (нумерация с нуля!). Пусть их q штук. Пусть в первой строке оставшихся 'b'-шек — p штук, во второй — r штук. Говорю, что вид первых трёх строк определён однозначно.
Переберём значение параметра t в порядке возрастания — это сколько 'b'-шек из третьей строки не пересекаются ни с 'b'-шками первой, ни с 'b'-шками второй. Дальше обозначил за x, y, z количества 'b'-шек третьей строки соответственно в p, q и r-секции, составилось уравнение относительно трёх переменных и параметра t в духе:
x + y + z = cnt3 - t
x + (q - y) + (r - z) = A23 - t
(p - x) + (q - y) + r = A13 - t
где cnt3 — количество 'b'-шек в третьей строке, A — матрица расстояний по хэммингу. Решили её, проверили, что x, y, z имеют приличные значения. Как только для какого-то t всё сошлось, выводим ответ и умираем.
Я в ваших обозначениях перебирал, сколько букв b в четвертой строке находится в q-секции. Дальше все восстанавливается однозначно, из из всех валидных решений выбираем таковое с минимальной длиной:
http://codeforces.com/contest/193/submission/1758827
Нет, у меня какая-то ботва с перебором одного параметра внутри, сложность O(длины ответа). Посмотрим, зайдет или нет...
UPD: зашла
Неет... Пары минут не хватило на отправить E :-(
Отличный сет! С первого взгляда трудные задачи оборачиваются халявной догадкой. Спасибо!
D клевая! С нетерпением жду разбора, час голову ломал.
So what is the observation that solves B?
Eliminate any sequence that contains two consecutive XOR operations.
It's WA :) Sometimes you need to make only XOR operations without adding to get better result.
tourist's test:
Input: 1 2 1 10 20 -100 1
Output: -1200
Answer: -1000
Yes, because of that you assume that you can't do consecutive XOR operations, BUT ALSO NOTE: after that you should also assume that the length of operations can be u, u — 2, u — 4, ... u — 2k
While adding new operation if (u-operations_done%2==0) you can actualize result (later operations will be only xors).
Hmm I still got a time limit even after implementing something like that.
You need to check sequences shorter than u as well, right?
EDIT: Aha you already answered :) thanks.
Yes, please see the message above. Regarding to time limit, all possible sequences are about 2mln, and for each of them you need to do 30 operations, so 4s time limit should be ok.
А почему на сайте не поддерживается Python>=3.0?
Where/How do I report cheaters?
Check out this 2 guys codes for problem A:
http://codeforces.com/contest/193/submission/1756318
http://codeforces.com/contest/193/submission/1756337
Its the same code, they are both from the same country and they submitted at the same time..
You'd better contact either Gerald, or author of the contest, or MikeMirzayanov.
Their rating graphs since mid-April 2012 don't look vastly different either. Or their avatars, for that matter. Why would someone submit exactly the same stuff from two accounts anyway?
Maybe it is one user that has another account for testing and when he gets accepted he submits the same code with his real account. Either way it should be penalized by admins. Cheaters are never welcome.
Sorry, That accounts is mine, I always use 2 accounts to join codeforces beta round, but I am not a cheater, I don't know that, and I will use only one account to submit on next contest. Sorry, because I don't know.
Can't help wondering what could be the reason for always using two accounts, if not cheating?
как решать B (Div 1)?
Заметим, что не имеет смысла делать более 2 подряд операций ксора, так как 2 операции — это исходный массив, 3 — операции — это одна и так далее. Делаем тупой перебор, в котором параметры сколько операций сделано, и правда ли то, что последняя сделанная ксор. Проверяем, если осталось четное число, то пытаемся заполнить их ксором, и далее по алгоритму. Таких комбинаций не более FIB(31), что около полутора миллионов.
Иногда выгодно много раз ксорить, т.к. иначе ответ ухудшается.
в смысле? Если это между двумя периодами операций второго рода, то тоже самое, или 0 раз, или 1, потому что оставшиеся ксоры мы тупо в конец пихать можем, разве нет?
UPD — 1761428 — AC
а откуда информация про fib(31) есть теория о которой я не знаю?
Выпишите время работы как функцию от n. Получится f(n) = f(n - 1) + f(n - 2): либо мы сейчас делаем перестановку, либо ксор, а потом сразу же перестановку. Поэтому получаются числа Фибоначчи.
Или же посчитаем число нужных нам масок
f(i, 0) — число хороших масок длины i, заканчивающихся на 0, аналогично f(i, 1)
f(i + 1, 1) = f(i, 1) + f(i, 0)
f(i + 1,0) = f(i, 1)
f(u, 1) = FIB(u)
f(u, 0) = FIB(u — 1)
total = f(u, 1)+ f(u,0) = FIB(u) + FIB(u — 1) = FIB(u + 1)
MAX_U = 30
Представь себе, есть теория, о которой ты не знаешь.
В предыдущей правке идейно неправильное ДП. Конечно, только перебор.
Соревнование очень понравилось. Не удивился, когда увидел, что задачи готовил школьник: ничего заумно-теоретически-скучного, от задач веет чем-то живым. В общем, как сейчас модно говорить, "аффтар пеши исчо!" =) (а вот сложность задач можно немного снизить)
Its only 8 minutes after the end of the contest and the system test for DIV-2 has completed 77% ... Blazing fast :)
Nice problemset. Hard, but fun :)
Thank you =)
Yes the contes was verry good and interesting and the there was no problems with the tasks.
Отличный контест! Авторам спасибо! Когда разборов ждать?
Разбор Див2 на русском уже есть.
Чудной контест вышел, необычный.
Красивые, необычные задачи. Контест очень понравился.
Отличный челендж-контест
Подскажите, пожалуйста, где я набагал в B(div 1)...1761150 А то не могу найти баг...Наверное, какой-то мелкий и идиотский. Заранее спасибо.
UPD: спасибо за помощь, проблема решена.
У Вас kol с единицы, поэтому по ходу проверку на нечетность разницы нужно делать, а не на четность
Спасибо. Как я и говорил, ошибка идиотская. UPD : все же не в этом дело
Отличный контест, интересные идейные задачи с несложной реализацией. Спасибо tunyash!
Hi guys, I solved problem for the first time (in 2 participation) and my rating decreased as for the time I do not solve any problem. Is it normal ? Thanks for the contest,
Rating is change depend on your ranking, not from your submission :)
Thanks, i just do not noticed that I effectively less ranking than the first time one.
Really enjoyable and challenging contest. I could've done much better, but I still had lots of fun doing it and it's all that matters. Congratulations to the organizer!
Спасибо за контест!
I like the problem E in Div 2.
Any idea how to solve this equation?
I thought that queue is too slow for this, but only "trick" (I do not know if it's working — if it is enough) is the one from statement — we can combine 6 combination to get [ 4; 4; 4; 4; 4; 4 ]...
Although i don't think this equation related to Ediv1, Use some of method like Gauss-Jordan Elimination to solve it. After did elimination you will get 1 free variable, Bruteforce on that variable is enough to pass Ediv2 problem
you are correct, it's E in div2 (C in div1), thanks for hint ;-)
Эх, а я после 20-минутного ступора над A решил воспользоваться методикой Петра. В то же время как B минут за 10-15 можно было спокойно написать...
Не думаю, что это достойно подражания. Хотя правила не нарушаются...
Great contest ... analytical problem set and clear statement ... really enjoyble .... and thtz the spirit of CodeForces ... :)
a really great contest. thanks for bringing such a great time to us. of course the problems were hard. :D
I hope there will be an editorial for this round too.
thanks again.
Спасибо за контест. Мне кажется что из условия задачи C (div.2), не совсем очевидно что на тест 1 2 ## надо выводить -1 (меня на этом взломали).
В условии написано, что пустое множество и мн-во из одного элемента связны. Значит, что бы мы не удалили из набора, множество останется связным. Получается -1. Все было в условии.
Значит я туплю.. извиняюсь.
Вообще хотя бы простейший случай с -1 (как выше — 1 2 ##) следовало включить в претесты, чтобы лишние вопросы у участников не возникали. То же, кстати, и по задаче C.
В претестах был тест в одним #. А что было в задаче С?
Тьфу, прошу прощения, не в претесты, а в примеры. В задаче C то же самое — странно не найти в примерах к задаче, в которой тесты с отсутствием решения встречаются чаще, чем с его наличием, примера с ответом -1.
Замечание, конечно, несущественное, и совсем не портит впечатления от этого замечательного контеста, но все же...
Зато не было ни одного теста с 1, где точки есть хотя бы в 2 строчках.
В претестах был тест
Точки в 3х строчках. Или что вы имели в виду?
Челябинские контесты настолько суровы, что даже Гена решает там 3 из 5.
Но успевает сломать 18 участников :-)
Гену подвело стремление к первому месту, а для этого надо было, как минимум, успеть и наломать, и сдать Е. Наломать он успел, а на Е не хватило, буквально, 10 сек. Правда, как в итоге выяснилось, это не имело значения.
can u explain me how to solve the problem 194B? thanks so much :)
We take the square's fields as a linear sequence of 4*n fields. To simplify our calculations, we'll mark the fields starting from 0 (the bottom left corner).. all the way to 4*n — 1. In every move we will traverse n+1 fields, thus landing on the field marked as k * (n+1) mod 4*n, where k is the amount of moves we made. Now it is obvious that the solution to the problem is the smallest positive k for which k * (n+1) gives a remainder 0 when dividing with 4*n, plus 1 (because we have to count the initial cross too).
Hope this helped.
thanks very much :)
Hey skyocean1996 I post an explanation in my blog here
So where is the English editoral?
It's hard for me to write it, but you can see editoral for the first 3 div2 problems. Today I hope, you will see editoral of all div2 problems.
I`m 204th coder in ranking, but my profile shows I got 206th.
Two cheaters were deleted from the standings. And places wasn't updated. I'm not sure, but it looks like truth.
Куда делись условия задач?
UPD. Все, исправили.
Why does it say "Statement is not available." when I try to access a problem statement from this contest?
Fixed now. Thanks!
пожалуйста помогите у меня проблема в задаче 193А посылка номер:1771411 . На моем компе все работает но когда я посылаю задачу на проверку выходит СЕ.
Попойму на codeforces нельзя изменять значение функции. Ну т.е нужно создать дополнительную переменную и в конце функции, ей присвоить значение переменной! UPD: вот исправил твою посылку 1771428, зашло!