Добро пожаловать на Codeforces Round #134!
После более чем двух лет, я снова с большим удовольствием выступаю в качестве автора контеста на Codeforces. Большое спасибо Gerald за помощь по подготовке контеста. Я надеюсь, что вы получите удовольствие от решения задач ничуть не меньшее, чем получили мы, пока готовили эти задачи для Вас.
В этом раунде будет использована динамическая система оценки задач, при этом задачи будут расположены в порядке их предполагаемой сложности. Верны ли наши предположения? Посмотрим. :-)
Всем удачи!
P.S. Данный пост является переводом оригинального поста на английском языке. Комментарии на английском приветствуются.
Update: Контест закончился! Результаты:
First division:
Все участники из top 7 решили по 3 задачи. Обратите внимание, два участника заняли 2е место.
Second division:
Во втором дивизионе 17 участников решили по 4 задачи. Никто не смог сдать задачу E, которая так же была задачей C в первом дивизионе. Эта задача оказалась достаточно хитрой, даже для "прокаченных" участников из первого дивизиона.
Поздравляем победителей!
Анонс как-то слишком заранее сделан... Давно такого не было.
А CFR129 давно был? И в нем анонс еще раньше сделан.
Он будет утром... если сейчас не анонсировать кучу народа может просто подумать что контест завтра вечером и проспать (вообще наверное это надо было напомнить в топике).
Can someone translate this for me please? I feel left out!
...But when i do "you don't know what i am saying"
Неплохо было бы сделать регистрацию не с часа ночи, а с вечера, например, часов с 6.
Thanks for your hardwork,and I must say that I love the sentence "but the problems will be ordered by their expected difficulty, from easiest to hardest" most.Hope to solve as much as I can.
ждем)))
Registration duration is diffirence,only 9 hour and 30 minutes, will be start 01:00AM,will be end 10:30AM
Why have negative votes,He is true.
As mentioned before. One does not simply try to understand negative votes on codeforces.
And the score distribution is… :-?
There is dynamic scoring. Read this for more information: http://codeforces.net/blog/entry/4172
Good luck, everybody!
and have fun!
and read every problem statement! ^_^
attentively
I'm so happy, that round start 5mins after full hour :D
На чем ломали B?
У меня один взлом на 1 1.
Меня на 1 1 =) я в цикле перебирал второе число до r — 1
У меня на нем же слетит :)...Заметил после того, как заблочил :(
Спасибо за взлом, кстати =)
Всегда пожалуйста :)
Объясните, пожалуйста, D div 2) Больше часа на ней просидел( Explain , plz , D div 2)
translate from google:
Explain, please, D div 2) more than an hour spent on it (
Hint: use Euclidean algorithm.
Ok, thanks, I think about it
Think backwards: if a>b then (a, b) -> (a, b-a)
Great contest! All tasks were very interesting, even A(Div 2)!
Что представляет собой тест №9 в Е?
Сорри, поспешил.
2028500 — Не является ли это нарушением правил?
upd. Я просто спросил) Ибо второпях на контесте мне показалось, что это сделано именно для того, чтобы мне помешать поломать) Если все в порядке, то ладно, простите, ложная тревога.
Это просто комменты на русском языке в непонятной кодировке. Обфускации тут нету.
С чего вдруг? У человека кодировка другая, комментарии вообще тебя не должны касаться.
А вот такое? http://codeforces.net/contest/218/submission/2027717
See this one and this.
This is dsbuaa, who took 1st place, and their codes are look so same.
http://codeforces.net/contest/217/submission/2027994
Question to admins: will smth apply to contestants who copied?!
В бан обоих!
UPD: Всех троих, а насчет которые заканчиваются на "bua" надо еще посмотреть.
UPD: Задачи A div 2 и C div 1 также у этих "bua" совпадают, просим бана
UPD: и у domain тоже :) Наверное, если порыться, то и в прошлых контестах было аналогично, просьба забанить последних, аннулировать результаты и пересчитать рейтинг за те контесты, где эти люди читерили.
В прошлом контесте было абсолютно также domain и dsbuaa, код совпадает с точностью до знаков препинания. Дальше лень смотреть, но кажется тут с ними все ясно.
Сейчас в комнате заметил небольшой баг с отображением результатов: некоторые решения, которые были взломаны, а потом переотправлены помечены как "После блокировки решение было взломано пользователем ..."
Великолепнейший контест! Я в восторге! Спасимбо автору! Задачи, на мой взгляд, были сразу понятны и не требовали знаний каких-либо сложных алгоритмов (в первых 3-х задачках, просто другие даже не читал). Требовали от участника немного поразмыслить и хорошо реализовать.
Problem B is fine. Solution is easy but I could not guess it during the contest...
черт, моя С упала из-за одного криво перебитого из таблички байта. поправил — зашло =_=
UPD. контест, тем не менее, понравился. особенно когда после конца допер таки до решения B...) спасибо.
Может тогда дашь пару хинтов по решению?
Nice problem-set but two 500 pointers in div 2, and no 1500 or 2000 pointers in between 1000 and 3000 seemed odd.(Though it happened due to dynamic scoring)
It's a nice contest!Well done problemsetter meret!
How soon will the rating be refreshed?
Nice problems.I'm looking forward to tutorial because nobody solved all problems.
Wish meret would write the editorial.
I'm eager to learn to solve problem D and E.
Nice problem C div 2. I was studying Graph Theory some hours ago and I got AC in this problem with a DFS.
I use UFS in this problem.I think this problem is very flexible,and there's more than one way to solve it.
What is UFS, I never heard this algorithm, by the way I solved this problem with Union-Find Set.
Union-Find Set.A useful data structure.
shater -_-
UFS is a better choice.
Объясните мне, пожалуйста, ответ на 6-й тест в задаче B div1.
Ответ выглядит вот так: 6
TBBTBBBBBTBTBTTB
Теперь, приписывая снизу "правильную" последовательность:
TBTBTBTBTBTBTBTB,
я вижу расхождения в 10 символах, а не в 6.
Что я не так понял в условии?
Количеством ошибок считается кол-во пар рядомстоящих символов, которые одинаковы.
Мда, учимся читать...
Спасибо!
Вы не поняли, как авторы определили понятие "ошибки"
ответ это количество пар одинаковых соседних символов, а не количество расхождений с правильной последовательностью
Но в условии же было написано, что одинаковых соседних символов может быть больше, чем 2.
>> К сожалению, Байтек иногда ошибается и повторяет операцию два или более раз подряд.
И где противоречие между этими двумя условиями?)
Хаха, я ведь понял условие точно так же. Впрочем, все равно не знал, как решать.
Problem E is so Hard..
Задачки были супер! Лично мне очень понравились вторая (на реализацию) и третья (я делала системой непересекающихся множеств). Спасибо авторам за чудесный контест!
is there any other way (other than graph theory) to solve the problem C(div 2)?if yes,can anyone provide a hint..
You can use DSU.
sorry,what's DSU short for?
Disjoint-Set Union
Disjoint sets data structure
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.
This problem can be solved in N log N time with union find. I think I wrote a good example http://codeforces.net/contest/218/submission/2046921
А когда появится разбор задач? :о
С (div2). Я никак не могу понять одного момента.. Пусть нам дано n не связных между собой "сугробов". Разве есть случай такой расстановки этих "сугробов", что для их связывания необходимо создать минимум n, а не (n-1) дополнительных ?
Чтобы соединить n вершин в целую компоненту связности, нам же надо n-1 ребро. А, ставя сугроб в этой задаче, мы, как бы, проводим ребро. Значит ответ на ваш вопрос : "нет"
Нет, такого случая не существует.
[user:meret]will someone write the editorial???
In Problem B Div.1 (Blackboard Fibonacci), I try to run the large test case (
999997 999997
) inwww.Ideone.com
and my laptop then I got runtime Error. But when i submit it to Codeforces system, it accepted :-o (Although the final test has the same test case :-o)My submission:
Codeforces
Ideone
Can anyone tell me why?
Maybe problem is in stack size, because you use recursion.
Here, on CodeForces, stacksize is increased for g++ using compilation string
Thank you!
Upd: Another Online Judge don't increase stacksize :-(, so my solution can't get AC in some problems. Is it possible to increase stacksize in C++ source code :-(.
As far as I know
#pragma comment(linker, “/STACK: 268435456”)
works only in MS Visual C++.How about G++ compiler ?
AFAIK, there no way to do in G++, but you can write your problem not recoursively(or use MSVC++, of course)
I don't know if DIV I — C was so hard or DIV I — B was hard enough that people spent a lot of time in that problem and didn't have enough time for problem C.
BTW... My solution for DIV I — B was hacked during the contest and I couldn't fix it... The test case? 1 1... I hardcoded it as
T
instead of
0 T
EDIT: Fixing that case passed system test after contest was over.
I feel your pain.
Как решалась С div2 (A div1)? Почему с-1 (где с-количество компонент связности) неправильно? upd: Если это правильно, то как их тогда считать? Почему не работает такой подход: заведем 2 массива
bool
по 1000 элементов (назовем ихax,ay
— в них будем хранить в i-ом элементе true если на этой горизонтали(вертикали) есть вершина), пусть теперь добавляется вершина(x,y)
, еслиax[x]==false
иay[y]==false
— увеличим счетчик; потом установимax[x]=true, ay[y]=true
Это правильно. Нужно лишь правильно найти компоненты связности.
(1, 1) (2, 2) (2, 1) (1, 2)
Если добавлять по очереди, алгоритм даст 2 компоненты.
Ломал похожее решение, выше уже ответили, почему это не так. Количество компонент связности нужно было искать как количество компонент связности в графе, в котором ребра имели сугробы с одинаковыми x или y, то есть построить граф, а затем пробежаться несколькими поисками в глубину, или же как количество различных множеств в системе непересекающихся множеств, построенном по аналогичной схеме, что и граф, что почти тоже самое, но немного по-другому реализованное — здесь ты сразу все вершины из компоненты объединяешь во множество и таким образом тебе, как в первом случае, не придется бежать по этому всему поиском в глубину, а можно сразу выдавать ответ.
Вроде бы это верно. По крайней мере верно такое решение: считываем x, y. Если не было такого x, то увеличить ответ на 1, если не было такого y, то увеличить ответ на 1. И в любом случае вычесть 1. Если я понял, ты это и имел ввиду. Но только массивы нужно сделать размеров в 10000 элементов, а не 1000. Потому что координаты до 10^4.
Thanks for holding a match at a different time than usual. I enjoy Codeforces contests but have a hard time competing at the usual time. I enjoyed these problems and hope I don't have to wait so long before my next contest.
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!:-)
Oh, common, 11am is not a problem, SRM at 5am is :)
Please think about other countries.For example,the usual contest time(7:30PM Moscow Time) is 11:30PM in China.So I think we should have more contests at times like this one.
Ok, so why not to have contests always at different time?
Could anyone tell me how to solve Problem E of Div1?Thanks.
I have solved the problem.
YM I haven't solve C of Div1 now. I can't understand the code. So I play DotA.. How can you solve D and E?
Indeed,my solution is the same as panyuchao's
you need idea? or to know how solved problem?
authors and solutios:
Solutions 2032857 2029369 are very different.
Submissions 2033918 and 2028007 are also very different!
Как решать (D(div2), B(div1)) и (E(div2), C(div1)) ?
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)
Рассматривать отдельно первый вариант с заменами всех литералов либо нулям, либо единичками не нужно. Он просчитается в динамике корректно сам.
Думаю, не слишком понятно объяснил, но главное вкурить первую часть, а дальше можно и самому догадаться.
А можно пояснить, почему условие f (x1, x2, .. xn) != f (!x1, !x2, .. !xn) является необходимым и достаточным?
По-моему, возможна ситуация, когда f (x1, x2, .. xn) == f (!x1, !x2, .. !xn), но при этом f (x1, x2, .. xn) != f ( x1, !x2, .. !xn) и т.д.
x1, x2, .. xn это просто комбинация из 0 / 1, которые заменяют все '?' !x1, !x2, .. !xn это обратная комбинация.
Если такая комбинация существует, что f(x1, x2 .. xn) != f (!x1, !x2 .. !xn) еще при условии, что f (0, 0, .. 0) = f (1, 1, .. 1), то ответ можно найти. В задаче не важно какая это конкретная комбинация (можно сказать ученые могут найти все комбинации сами), их может быть несколько, нам важно только, что она существует. Ее и нужно использовать для определения колоний.
Мы перебираем и рассматриваем 2 колонии. Есть 4 варианта, какие конкретно виды бактерий находятся в этих 2 колониях — (0; 0), (0; 1), (1; 0), (1; 1). Вот мы и вставляем в x = 0, значение первой колонии, а в x = 1, значение второй колонии. И тогда все эти 4 варианта покрываются. 3 из них дадут одинаковое значение, а 4-ый даст противоположное. Вот как раз (0; 1) или (1; 0) даст нам наше противоположное значение и мы сразу же можем определить их вид.
спасибо за пояснение, буду дальше осмысливать..
Друзья, кто нибудь знает, появится ли разбор контеста от автора? Очень жду)
Could anyone tell me how to solve Problem C of Div1 (Problem E of Div2)? I have seen some codes but I still can't understand them. Who can give me some hints or useful conclusions to solve this problem? Thanks very very much!
It sufficient to look at the subsets of size 1 or 2, instead of all subsets of colonies {c1, ..., cn}.
Replace each '?' by either ci or cj, i and j being arbitrary for now. Look at the values in the four cases (ci, cj) = (0, 0), (0, 1), (1, 0) or (1, 1).
For example, for (ci&(ci&cj)) we would get 0, 0, 0, 1. Note that there's only one way to get 1.
Thank you very much.Supose that F(ci,cj) is the result of permulation,what is the inital value of F(0,0) F(0,1) F(1,0) F(1,1)? Thank you.
You can compute the values taken in the four cases recursively. Look at this submission for a better idea: 2032900
Could any one can explain why "not all colonies are of the same type" is so important ? ..
“not all colonies are of the same type” is important for '((?^?)&?)'
I Got!..
Could anyone provide some tricky test cases for Div1-C? I am failing case 13 and its huge :/ (all the tests after 13 are huge too..) Thank you.
'((?^?)|(?^?))'
why the editorial is not uploaded yet ?
It looks weird to have 7 people in top 6 when the "6th" place is non-tied. If there is a 2-way tie at place n, I believe the standard way is to denote the next place (n+2), not (n+1).
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.
No editorial yet ... :/
Here
I meant editorial for all problems. In the link given by you, there is no editorial for 218B - Airport. I was searching for its dp solution.