Всем привет!
Как многие из вас уже знают, сегодня в обоих дивизионах состоится Codeforces Round #127, пропускать который очень не рекомендуется ;)
Оригинальные задачи для вас придумывали и готовили tourist и Romka. Мы старались сделать упор на идейную составляющую задач, поэтому надеемся, что вам придётся думать дольше, чем набирать код. Отдельное спасибо за помощь в подготовке контеста координатору Codeforces Gerald. Также благодарим Delinur за перевод условий и Alex_KPR за вычитку условий.
Надеемся, что этот раунд будет для вас не просто очередным раундом на Codeforces, а принесёт вам новый опыт и новые знания. Авторам все задачи кажутся одинаково простыми, но мы всё-таки постарались расположить их в порядке убывания простоты :)
Разбалловка в первом дивизионе: 1000-1000-1500-2000-2500. Разбалловка во втором дивизионе: 500-1000-2000-2000-2500.
Успехов!
UPD: Соревнование закончено, всем спасибо за участие. Надеемся, вам понравилось :)
В первом дивизионе безоговорочную победу одержал rng_58, решив все пять задач за полтора часа! Решить все задачи за два часа больше не удалось никому.
Победители в первом дивизионе (полные результаты):
Во втором дивизионе каждая задача была кем-то решена, но решить все задачи не удалось никому. Борьба оказалась очень упорной, а разрывы -- очень маленькими.
Победители во втором дивизионе (полные результаты):
Поздравляем победителей!
UPD2: Опубликован разбор задач.
Заранее говорю спасибо. Очень ждал контеста от Геннадия.
И всё же это контест не только от Геннадия :)
Не только, но и от Геннадия тоже. И я говорю "спасибо". И Роману я тоже говорю "спасибо"
Серёга советую не писать)
позабавило)
Задача А — "Сокобан")
Кстати, извиняюсь за оффтопик: кто-нибудь в курсе, можно ли впихнуть что-нибудь вроде решения сокобана во что-нибудь вроде кандидатской диссертации? :)
Можно что-то вроде запихивания сделать)
Я этот вопрос адресовывал тем, кто что-то понимают в теме, а не тем, кто будут кидать вот такие шутки.
Тогда пишите получателя, как в письмах. Я ориентировался на смайлик
Да просто бессмысленный вопрос. Уточни, что ты понимаешь под "что-нибудь вроде" в обоих случаях.
This will be my 1st participation ever on a codeforces round!! I am looking forward to it
good luck then ;-)
As points seem to be in increasing order, it suggests that also the difficulty of tasks is increasing rather than decreasing... am I right? :)
Yes, you're right: in Russian version it's written: "in decreasing order of simplicity".
Thanks man, always good to know where to start :)
Yes, I meant "in decreasing order of simplicity" :) Thanks, I've corrected it.
I'm learning Einglish！>_<
"yet we tried to arrange them in decreasing order of difficulty :)"
decreasing order with points increasing?
That was a mistake, sorry. It should be "in decreasing order of simplicity", of course.
I really like the idea ;-)
А почему такой же пост от ilona насильно запихали в черновики, а автору сделали письменный выговор?
Потому что MikeMirzayanov добрый и педагогичный, т.к. дает троллям возможность исправиться и встать на путь истинный вместо того, чтобы сразу их беспощадно банить.
ilona не тролль.
У Вас есть доказательства?
Девочки не умеют троллить же.
А ilona девочка?
Думаю, это по нику понятно :)
Я тоже не сразу догадался
xDА по каким это признакам Вы догадались?
по первичным половым :D
"For the authors all problems are equally easy, yet we tried to arrange them in decreasing order of simplicity :)" Nevertheless, we recommend you to read all the statements and hope you won't get stuck on one problem losing possibility to solve other problems.
Так, а теперь вопрос: откуда пользователь ilona узнал, кто авторы контеста?
по почте
I Hope Short statements ,easy to understand and more thinking.
I like such problem statements too, like the one in SRM 547, Div I, easy.
Totally agree with you.
ой, какая я популярная.
Ага, наслаждайся.
I feel it will be hot !!!
А то, что мне при попытке открыть страницу с условием выдаёт "Условие недоступно." это всё норм?
UPD. Уже прошло
Спасибо авторам за контест ,было очень интересно, жаль что я опять зеленый..
Откройте секрет 7 теста задачи А!
3
Ответ — 5
100 010 001 upd. да. действительно
Не симметрично.
матрица должна быть симметрична по вертикали и горизонтали. если есть 1 не в центре — то и еще в 3 точках. потому 3 на матрице 3х3 не получишь.
Не совсем так. Еще может быть в центре боковой стороны, тогда можно получить 2 единицы. Но да, при этом блокируется диагональ.
x = 1 -> ans = 1 x = 3 -> ans = 5, x <= 5 -> ans = 3; x <= 13 -> ans = 5; x <= 25 — > ans = 7; x <= 41 -> ans = 9 x <= 60 -> ans = 11; x <= 85 -> ans = 13 x <= 100 -> ans = 15
Для 1, казалось бы, ответ 1, а не 3.
I was the author of this problem... http://community.topcoder.com/stat?c=problem_statement&pm=11133
So Ivan won't accept that problem for Torcoder? :)
I don't think the SRM's problem contains a permutation of the codeforces's problem as a subsequence :)
Turns out it wasn't a brand new problem [:|||:] :)
We're really sorry that this happened. We both missed that SRM, so there was hardly a chance for either of us to find that out.
I know it's impossible to completely avoid "duped" problem. I'm just a bit surprised.
Подскажите как С решать плиз
Ответ по рядам не зависит от ответа по колонкам
Это вы про Б наверно?
Ох, да
В С динамика — сколько концов пути слева от нас (0, 1 или 2). Если 0 или 2, то мы берем четное число ребер, если 1 — то нечетное (максимально возможное). Если ребро 1, то 0 и 2 присваиваем 0 (так как тогда весь наш путь лежит по одну из сторон). Ну и на каждом шаге делаем ans = max(ans, dyn[2]) и dyn[1] = max(dyn[1], dyn[0]), dyn[2] = max(dyn[2], dyn[1]) (назначаем один из концов в этой вершине)
Спасибо за подробное разъяснение.
What is the logic behind Div-2 Problem C ??
just try it out wid some input values and observe the pattern....look for dependencies if any cell is 1..u wil find cells dependent in groups of 4, 2 and 1..so each square of size n gives some 4 pairs, some 2 pair and 1 one. now all possible combinations of sums from these pairs can be reached with square of size n. max sum dat can be reached using square of size n is sum of all pairs of 4, 2 and 1.
Why is the output of x=3 is 5 ..Cant we have something like:
it is not symetric.
Oh..I just read "Let's call matrix A symmetrical if it matches the matrices formed from it by a horizontal and/or a vertical reflection" and skipped the formal description.. From that statement I had made the conclusion that if we place a mirror on the bottom or the right and take the reflection and match then if we get the same array ,Its done..
y not..
0 1 0
0 1 0
0 1 0
for x=3...??
You have adjacent "1".
oh shittt....
jst got lost with that symmetric thng....
thnx.
Задачи понравились, спасибо за раунд!
В E Div 2 верно считать 4 dp — сколько наберём уйдя влево и вернувшись, и не вернувшись, тоже для правой стороны?
Как делать D Div 2?
UPD: да, верно, жаль не успел отладить
D div2 (B div1):
Заметим, что можно решить отдельно по X и по Y.
Далее за квадрат: перебираем позицию для текущего измерения, для каждой за линию ищем сумму произведений квадратов расстояния до столбца/строки на сумму этого столбца/строки (суммы предподсчитать)
В ответ сумму минимальных сумм для строк и столбцов, и номера строк и столбцов, в которых достигается минимум.
P.S. Мне одному нужно в комментариях <br> для перевода строк ставить? Или это нормально?
Спасибо! Пора бы уже научиться видеть боянистые идеи ><.
можно еще в конце строки ставить 2 пробела
Тест двух пробелов
(раньше всегда <бр> ставил)
Тут комментарии форматируются Markdown'ом, в нём между двумя параграфами должна быть пустая строка, чтобы они считались двумя отдельными параграфами.
Я ведь прав, да?
Похоже оба способа работают, но мне как-то не нравиится дыра между абзацами в случае пустой строки между абзацами, поэтому два пробела.
Спасибо!
Надо минимизировать
. Дифференцируем, получаем формулу, находим дробные x и y, смотрим точки по соседству.
подобное решение я взломал
Да, моё решение тоже упало. Есть даже гипотеза почему. Но скорее всего падает из-за кривой реализации. По крайней мере ошибки в теоретической части я не вижу: минимум квадратичного функционала на целых числах должен достигаться на одном из соседних к точному минимуму чисел. Или нет?
Если 20 тест то это тест из всех нулей, при попытке посчитать x0, y0 будет деление на 0
Нет, это я как раз предусмотрел отдельным условием. Упало на 11м тесте.
контест сложный, но задачи отличные
Лично мне понравилась только задача С div 1.
The Div1-E has been mentioned on Topcoder before (check SRM 484 Div1-Hard editorial) for reference). EDIT: Too slow
Спасибо за контест!
Боян очень порадовал (в т.ч. формат вывода :)
[:||||||||||:]
:))) До меня только дошло, что это рисунок бояна. :)))
Всё-таки, это рисунок бАяна.
Даже не знаю, кому верить: википедии или авторам задачи :)
Ибо в условии написано «боян» :)
В условии написано "обидное слово". Обидное слово могло быть хоть "фывапрол" ;)
Так, как я понимаю, и надо различать: боян — специфичный термин СП, определяющий засвеченную задачу, баян (музыкальный инструмент) к этому не имеет отношения. А авторы хорошо обыграли созвучность этих слов.
Не только СП: http://ru.wikipedia.org/wiki/Боян_(значения)
Думаю в данном случае значение имеет [:||||||||||:], а не его название:)
Вопрос снят
Отличнейший контест, пишите ещё!!!!
с чем связанно именно 500015?
15 слов (однобуквенных для уменьшения размера теста) в задаче Лёши + 500000 слов в задачах в архиве
Ну зачем переопределять существующие понятия??? (задача А, определение симметричности) Задача B — гуд, но я почему-то несказанно тупил весь контест и вообще всё слил. Когда хотел почитать задачу C, загрузилась страничка что сервер занят, а потом страница с сообщением "Условие недоступно." ... И тут я понял — всё против меня.
в задаче А 100 тестов из 100 возможных, not bad!
да ладно? николас_кейдж_фейс
А чего мелочиться :)
Тем более каждый тест генерится за O(1) :)
И в идеале за столько же проверяется.
Отличный шанс заддосить тестер :)
Только если специально :) чего каждый участник обещает не делать при регистрации на контест :)
Лично мне разумного решения медленнее чем за квадрат в голову не приходит.
Итого тестирование за O(N^3), что при таких N более чем быстро :)
Можно решить за O(n): 1841493
Спасибо за отличный контест))))
Никогда не ставьте максимум 12345678912345ll. До — 1842078. После — 1844086.
Like the problem set! e.g., for problem C, after analyzing a bit we can actually come up a very simple DP algorithm. Problem A (the easiest one) is too tricky to trap me for a long time...
Какая будет матрица в задаче A при x=6?
Один возможный пример:
1 0 1 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 1 0 1
Задача B, тест из всех нулей, деление на 0, жесть!
-100 мест и фиолетовый...
Задача B: тернарник вместо очевидного O(m * n) — потратил 49 минут времени. Задача А: написал правильный брутфорс, но тупо не заметил, что на тест 3 ответ 5 — итого все еще фиолетовый и не сильно быстро приближаюсь к оранжевым...
В-общем, беда у нас с Вами одинаковая.
Как над этим выражением только не издеваются =(
Я Вас не совсем понял...
>В-общемAny one Can tell me the Connection between Problem E with NumberMagic? ( SRM 484 Div 1 1000 ? ..
In Div2-C, how does the square look like for x = 3 ?
It can be done in matrix of size 5, but no less.
00000
00000
10101
00000
00000
[Edit:Slow]
0 0 1 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 1 0 0
00100 00000 00100 00000 00100
Somebody can tell me the value of n for x = 2 in problem C (div 2) and how the matrix looks like? Thanks.
n = 3
0 0 0
1 0 1
0 0 0
n=3 010 000 010
I really dint want to do this.But I am facing a strange trouble in the submission of the problem-B of div 2. It gives wrong answer on pretest 11 but when I run the program in my system for the same input it is giving correct answer. Here is the link http://www.codeforces.com/contest/202/submission/1844228
Firstly u have given the wrong link.. The link is link
sry the correct link is http://www.codeforces.com/contest/202/submission/1844228
Задача Div2-A порадовала :) жаль ограничения не 105.
А что бы изменилось?
Не проходило бы решение за 2^(длина строки).
Та задача, которая была в Петрозаводске этой зимой на контесте Токио Кроликов все-таки поинтереснее :).
Excellent contest. It was not very suitable time for me but I don't regret that I tried to compete.
Output format in D was ridiculous (bad that non-Russian speakers won't get it).
Я один писал в А динамику по профилю с изломом, а потом забивал ею массив констант?
Я хотел сделать то же самое, но потом написал брутфорс и по нему вывел закономерность (см. выше).
Will it have an editoral?
Может кто нибудь, пожалуйста, объяснить, как в таком тесте тесте в С получить 48:
9
9 2 8 7 1 4 10 9
3210101010123232323(влево)
434343456787656787878767676765(вправо)
0 — based
спасибо, кажется я немного туплю...
в итоге остаются первое и последнее ребро. А весь обход такого вида: начали с 4-й платформы, сделали 3 шага влево, потом до противоположного края и 3 шага влево (по ходу нужно ходить туда-сюда по ребрам, если есть возможность).
FAIL:(
Minor mistakes (less than 5 chars of code each, one per task) in tasks B and C and I am 221th instead of ~90th.
I need to exercise more often.
Good contest anyway!
I have had a lot of fun!
[:||||||||||:]
:-)4 a b c d 1 11 b c b a d d d a a c b for this test in B problem i am getting wa when in my pc i am getting the correct ans. code can anybody explain?
even iam having the same problem. If you get why it is happening please post it here
what is test case 11 in Div2 B?
what is test case 11 in Div2 B?
4
a b c d
10
20 d c c c c c b b b b b a a a a a a a a a
20 d c c c c c b b b b b a a a a a a a a a
20 d c c c c c b b b b b a a a a a a a a a
20 d c c c c c b b b b b a a a a a a a a a
20 d c c c c c b b b b b a a a a a a a a a
20 d c c c c c b b ...
How does the answer(p) come 1?
I got it.
Когда будет разбор?
Редкий контест, когда у Гены не было шансов победить.
When will editorial be available?
I didn't understand the definition of "clear" matrix in "Clear Symmetry." "Clear" means that no two or more adjacent "1"s never appear? Thank you in advance.
Thanks for the advance. :P
Мое решение 1843679 задачи D требует примерно 500000 * 2^15 * 15 операций в худшем случае (такой случай существует). Но за счет эвристики против случайных тестов получает Accepted.
Не каждый день удается подловить UPD: все-таки Рому, а не Гену :)
перепутал кое-что, написал глупость :)
Во-первых, эту задачу делал я :)
Во-вторых, тесты там далеко не случайные
В-третьих, у нас было около 5 неправильных решений на эту задачу с разными эвристиками/жадностями/отсечениями, и против каждого были тесты
Всех эвристик, разумеется, не предусмотришь — а в этой задаче их можно выдумать не один десяток. Тем не менее, я хочу сказать, что умение написать качественную эвристику тоже не у каждого есть, и человек, написавший достаточно продуманную и обоснованную эвристику тоже в какой-то мере заслуживает поощрения в виде АС.
Странно. Все C (про симметрию единичек) циклами решали, а я прямую формулу на бумажке вывел. Т.е. у меня самое короткое решение и еще O(1), lol.
Понятно. "Не смог написать эффективное решение – заминусуй того, кто смог". Я думал, тут умные люди собрались, а оказалось словно на хабре. Дети.
Я лично Вас не минусовал, но пост прокомментирую.
Во-первых, опытные СПшники, если им моментально приходит в голову решение с циклами и если позволяют ограничения, пишут именно его, а не тратят драгоценное время на вывод формулы.
Во-вторых, Вы в данном посте де-факто выпендриваетесь: "Все тупые, пишут решение с циклами, а я умный, написал решение с формулой". Еще раз см. пункт выше.
Пример того, как можно было бы написать то, что Вы написали, но "по-нормальному": "С-шку можно решить циклов одной формулой за О(1) без всяких циклов. На Ruby это вообще вмещается в две строчки.".
Я уверен на 99%, что ваш вариант комментария получил бы ровно такую же оценку. Он по сути ничем не отличается – если решение является д'Артаньянским, то как ни пости, вызовет баттхерт.
я вас плюсанул, только не плачьте
и кст, я думаю здесь все решившие ее циклом, знают, как сделать это формулой, просто не захотели еще и формулу выводить, так что понт по этому поводу не уместен, вот если бы вы Д див2 решили за О(1)
Формула была написана в две попытки, менее, чем за минуту даже без черновика, могу хоть фотку бумажки прислать. Где тут "тратить время на выведение вместо того, чтобы написать цикл на 10 строк и накосячить в куче всяких i и j", я не понимаю, как ни крути. (если у кого-то возникнет вопрос, почему введение i и j вызывает ошибки, пусть не спрашивает меня, а идет сразу на википедию читать о функциональщине)
какой цикл на 10 строк, наркоман что ле?
цикл пишется так же быстро, как формула
Если ты не смотрел чужие решения, значит я наркоман?
ну просто понимаешь, решил ты за О(1), ты молодец, ну это не повод для понта
А тут и не было понта. Тут был массовый баттхерт
ну все расценили это как понт, и вполне справедливо, на мой взгляд
где тут можно ошибиться? и это долго писать?
Я пару минут назад свой комментарий выше дописал скобками, чтобы мне не пришлось никого учить.
Много кого ты тут научишь наверно. Ладно бы также легко решил D и E вот это было бы круто, да еще бы без i и j, чтобы ошибок не наловить.
После таких сообщений хочется вспомнить Ферлона, его мнение насчет "я красный, а ты — синий, вот и молчи". Я решаю ненамного лучше вас, но, все же, нелепо обвинять всех участников, что "решают они неоптимально". Есть мнение, что оптимальным нужно считать решение которое придумывается и реализуется максимально быстро и получает АС.
И разводить холивары по таким глупостям — как-то нелепо. Да еще и детьми всех называть :)
Нелепо было минусовать коммент только за то, что в нем утверждается, что задача была решена за О(1), а теперь можно утверждать, что я везде неправ, если каждый мой комментарий вырвать из контекста.
например, я вас вообще не минусовал (мои то решения по-крайней за этот контест вообще трэшовые). Просто вы утверждаете что оптимальность в асимптотике алгоритма, хотя понятно тем кто придумал другое решение сразу оптимальнее писать было его и сэкономить на нем минуты/баллы, чем придумывать формулы (придумали которую как вы говорите за минуту, хотя странно, что у вас первая попытка и правильная отличаются минут в 20). В общем удачи в следующих контестах всем нам.
Я смотрю, тут некоторые перешерстили все мои коммиты, и даже детально изучили время их отправки. Коль уж я вызвал у них такой большой интерес, потыкал в их ники тоже. Чего и следовало ожидать: все брызжущие пеной ненависти эту задачу сами-то и не решили )
Очень порадовала задача D. Не форматом вывода, который тоже хорош, а именно тем как я её выдумывал, пришлось поломать мозги некоторое время. Идея моего решения в том, что ДП нужно вести последовательно по массиву слов слева направо, в состоянии кроме позиции в массиве слов присутствует маска и текущее число инверсий. Если у нас ранее (на более ранней позиции массива) была обработана пара (число инверсий, маска) то теперь нет смылса снова считать её снова, вроде как выходит 15 * (500 000 + 2^15 * (15 * (15 — 1) / 2). Интересно увидеть авторское решение, жду разбора.
Можно другое ДП делать: номер позиции в которой может заканчиваться такая маска и кол-во инверсий, там еще нужно будет предподсчитать для каждого символа номер следующего каждого цвета. Тогда отсечения не нужны вроде, и сложность легко считается.
А разбор будет?
Тебе дают возможность решить самому))
А почему никто не заметил, что в задаче 202B - Инновационно новая простая задача пример с копипастой из мультфильма 12oz Mouse
Div 1. A 201A - Четкая симметрия: "Назовем матрицу A симметричной, если она в точности совпадает с матрицами, образованными из нее горизонтальным и/**или** вертикальным отражением.". Зачем писать "или"?