Всем здравствуйте)
Рады приветствовать вас на очередном раунде Codeforces #117 для участников Div. 2. Традиционно, остальные могут поучаствовать в нем вне конкурса.
Задачи для вас были подготовлены группой авторов в составе: Павел Холкин (HolkinPV), Иван Фефер (Fefer_Ivan), Николай Кузнецов (NALP) и Геральд Агапов (Gerald). Мы благодарим Михаила Мирзаянова (MikeMirzayanov) за систему Codeforces и Марию Белову (Delinur) за перевод условий.
Распределение баллов вновь будет динамическим) Подробнее об этом можно найти здесь.
Обращаем внимание, что все задачи сегодня будут даны в произвольном порядке.
Некоторые участники Див. 1 зарегистрировались на соревнование раньше, чем была произведена настройка регистрации. До начала раунда это будет исправлено, и они будут участвовать вне конкурса.
Надеемся раунд пройдет успешно и всем понравится. Желаем удачи и высокого рейтинга!
UPD: условие задачи 182E - Деревянный забор было сформулировано неверно, что привело к несоответствию решений, правильный вариант условия появится совсем скоро, приносим участникам свои извинения.
UPD2: контест объявлен нерейтинговым.
UPD3: разбор задач можно найти здесь
Почему не все красные, желтые и фиолетовые отмечены звездочкой в списке зарегистрировавшихся, они же вне конкурса?
And are there dynamic problem max scores used?
And again score distribution will be dynamic) More information you can find here.Hm, that's nice, but I asked before it was written in post. HolkinPV updated the post later (I can't delete my comment)...
Задачи по сложности расположены будут?
"Обращаем внимание, что все задачи сегодня будут даны в произвольном порядке."
UPD. Окей, виноват=(
Сообщение было написано до объявления.
На этот контест уже 161 аккаунт с рейтингом "0" зарегистрирован =)
502 Bad Gateway...Please allow me to enter
UPD:Oops...Did not realize that we have been given 10 more minutes to get ready :)
Классно. Не успел зарегистрироваться, расстроился, а оно возьми и упади вместо начала. +5 минут для регистрации и довольный я.
Problem A will be the easiest one as the first dynamic contest ?
No
Yes. With probability 1/5.
Note that all problems today will be given in random order.
No, "Note that all problems today will be given in random order." ;-)
07:00 PM (Moscow Time), is the ideal time for a programming contest, please to keep this schedule for the future competitions.
В задаче C нету ошибки в выходных данных в третьем примере?
Нет. Там 4 надо на -1 умножить, сумма получится -11.Это и есть возможный максимум по модулю.
не хорошо обсуждать задачи во время контеста.
А вас бы побанить.
В следующий раз при возникновении вопросов используй кнопку "задать вопрос" на странице с задачами. Если действительно где-то ошибка, авторы контеста заметят ее и все исправят. Иначе ты получишь заслуженный "No comments" и будешь уверен, что все в порядке.
Почему все время выдает ошибку "Невозможно обработать взлом, попробуйте еще раз" ?
В претестах к задаче Е и самом авторском решении ошибка. Читаем условие. "Два забора будем считать одинаковыми, если соответствующие последовательности типов древесины досок заборов совпадают, в противном случае заборы различны" То есть, например, на тест 2 3 1 2 1 2 правильный ответ — 2. Действительно, если нас интересуют именно типы древесины, то очевидно что два типа переставить можно никак не больше, чем 2 способами. Однако, если не заметить этот нюанс, то несложно написать решение, которое ответит 4. Но 4 — ответ на другую задачу, на задачу, где было бы указано "Два забора будем считать одинаковыми, если соответствующие последовательности досок заборов совпадают по всем трем параметрам (длина, ширина, древесина), в противном случае заборы различны". И авторское решение также отвечает 4. Также можно посмотреть на 3-й претест из условия. Динамика, не учитывающая этого нюанса отвечает 20, правильное же решение — 16.
А откуда информация, что авторское решение отвечает 4? Из неудачного взлома?
В любом случае, до конца соревнования такие комментарии следует отправлять как вопрос по задаче, а не выкладывать публично.
Отправлял. Не ответили. А про контест — я, после того, как это обнаружил, как-то забыл, что он был перенесен на 10 минут.
может лучше написать вопрос авторам а не сюда?
писал.
Мы не можем давать ответы на такие вопросы. Это дало бы вам дополнительный пример входных-выходных данных.
Ну тогда поясните хоть сейчас что имелось ввиду?
Тогда поясните, ошибка в условии или в решении?
И вопрос вдогонку: как решать Е с текущим условием?
Неужели такая проблема в самом тексте условия? Разве можно не так понять условие и написать из-за этого неправильное решение, которое проходит добротный третий тест из условий?
Я написал два решения. Одно — неправильное — проходит претесты, про полные тесты пока неизвестно. Правильное не проходит 3-й претест, потому что у авторов ответ 20, а правильный — 16.
Ну, я вообще не так понял и решал другую задачу; но я так подумал, что можно посчитать обычные способы и потом отнять повторяющиеся по этому условию. Такими могут быть только те, которые составлены из блоков одинакового размера. А там получается что=то вроде x·(n - 1)!·n способов, если можем поставить x одинаковых, а типов таких досок — n.
UPD: Упс, неправда; на самом деле n·(n - 1)x - 1.
Ну да, что-то в этом роде и я писал, правда не заморачивался с делением всех досок на типы, а просто для каждой пары, если доски одинаковы и сумма длины и ширины делит нужную длину, вычитал единичку. Порисовав на бумаге несложно доказть, что это должно работать.
Да я полностью с вами солидарен, сам просидел над этим кучу времени. Но наверное под типом подразумевалось с учетом поворота, то есть если ты визуально можешь их отличить.
p.s. А вообще условие очень муторное, особенно если стараться понять легенду)))
Это понятно, что подразумевалось. И определение с учетом поворота действительно более логично. Но решать-то нужно задачу, не в том понимании, которое кажется подходящим и простым, а точно в том, которое указано в условии.
Меня такое определение тоже сконфузило...
Unable to ask questions. Getting "Field should not contain more than 1,000 characters" when the question is much shorter than that.
Maybe you have some copy-paste from HTML. And HTML source of your question exceeded 1000?
I did not copy paste the question initially, I just typed it in the box. I also tried using the "Remove formatting" option.
Thank you. I'll try to investigate it.
На чем валили D?
На много чем. Люди забывали, что делители не только должны быть одинаковой длины, но и совпадать (aa, bb), что делится надо нацело (aba, aba), ну и еще какие-то мелочи
Понравился ли вам этот контест???
Я в очередной раз убедился, что условия надо читать внимательно)
Не особо) Но это потому что я тупой )
Нет
Да:) Задачи были классными.
Да, мне очень понравилось. Хотя я ничего не решил, но у новичков бывает. постораюсь в следуюшии раз попытаюсь решить.
Задачи хорошие, а вот условия в некоторых задачах сформулированы не очень понятно.
Почему ответ на тесте 3 5 2 3 2 3 2 3 - 12 а не 6
ведь первую доску мы выбираем тремя способами а вторую двумя
Потому, что авторы не смогли правильно сформулировать, что они хотели
Ох и плохо будет мне, если упадёт А.... ;)
Ну что ж.. Расскажите мне, пожалуйста, кто-нибудь, как пишется динамика в Е, а то я так и не придумал :(
У меня f[i][j][k] — i — последний вид древесины, j — текущая длина забора, k — текущая ширина. Персчет, думаю, очевиден.
Я брал такую же динамику, но вот как раз-таки пересчет мне не был очевиден, не объясните ли?
f[i][j][b[i]] сумма всех f[t][j — a[i]][a[i]], где 0 < t <= n, t != i; Для улучшения асимптотики храним se[i][j][k] — сумму всех f[t][j][k], где 0 < t <= n, t != i. Затем меняем местами a[i] и b[i] и повторяем данную операцию.
Эх, ясно, спасибо. Совсем в другом русле мыслил, когда я уже с ДП подружусь(
Я писал так — d(i, j, k) — колличество способов сделать забор длины i так, чтобы последняя доска была типа j, причём k = 0, если она не перевёрнута. O(l * n^2).
А пересчет как?
Перебираем длины заборов, для каждой фиксированой длины попробуем закончить забор такой длины доской каждого типа. Для фиксированого типа доски мы отберем все типы досок, которые могут предварять этот тип, и увеличим ответ. Кроме того, нужно аккуратно обрабатывать доски, в которых ширина равна длине, можно всегда считать, что d[i][j][1] = 0.
Я бы написал формулу, но в моей реализации она вышла уж очень громоздкой.
Может кто-нибудь подсказать, что за коварный 15 претест на С? так и не преодолел его (
Условия непонятное. Не хрена не понял.
В этом авторы не виноваты.
Unsuccessful challenge on problem E:
Input: 2 4
1 3
1 3
Output: 4
Answer: 4
How the answer is 4? It should be 2.
1) #1, rev#2
2) #2, rev#1
I asked a lot of questions during contest and got answers that for example (#1, rev#2) and (rev#1, #2) are same variants. In that case the answer should be 2 for the case above.
I think answer is 4,not 2. You get 2 combinations putting type 1 first, and 2 putting type 2 first.
According to the problem description 2 out of those 4 variants are the same.
P.S. I even asked a question to jury by specifying exactly such 4 variants, and got a response that 2 of them are duplicate.
i think that they assumed that a rotation is considered as new type
In problem E.
What is the answer for the input (2 3 1 2 1 2) ?
There are 4 sequence of fences.
seq0 : fence[0] -> turn(fence[1]).
seq1 : turn(fence[0]) -> fence[1].
seq2 : fence[1] -> turn(fence[0]).
seq3 : turn(fence[1]) -> fence[0].
But seq0 and seq1 are same, And seq2 and seq3 are same too.
So I think it is 2.
But if so, the answer for sample3 is 18 not 20.
Same issue for me :) Spent 1 hour on discussions with jury
I'm surprising when my not-finished solution passed examples(as well as the pre-tests). That is the same question. The admin's reply is just:
"I can only say, that rotation of the board does NOT change its type. So sequences with same boards but with different rotations are same."
So I don't know what is wrong: the standard solution, the statement or my understanding?
Второй раз подряд пишу почти правильное решение и нахожу недочет за 5 минут до конца контеста :(. На этот раз так получилось с С.
Вижу у тебя тоже 15 претест валился... Так в чем недочет был?) Уж больно интересно, все мои тесты проходит, а на 15-ом валиться...
мне помог тест:
исправить — исправил, а засабмитить не успел =(
Против моего решения тест более сложный:
7 5
1 1 1 -2 10 10 -9
1
Недочет такой: мы поменяли k элементов на отрезке [i; i + len — 1] и нашли сумму. Теперь мы переходим к отрезку [i + 1; i + len], и нам выгодно вернуть оригинальный знак какого-то элемента и поменять знак у элемента на позиции i + len.
ага, а кто-то просто индекс в одном месте забыл инкрементить
Problem C: Many people have wrong answer with pretest #15 (include me). Good pretest :D
в задаче Е мне было неудобно работать с шириной и длиной. Логичнее представить высоту и ширину... Мелочь а все равно влияет
Как в первом семпле в задаче А получается 19? Ведь есть же путь A -> 1 -> 2 -> 3 -> B длины 1 + 4 + 1 + 4 + 2 + 4 + 1 == 17
Из А за 1 секунду добегает, проходит ещё 1 секунда, затем 4 секунды луч работает и т.д.
[upd: sorry for asking the same questions other people already did. I typed the question at the same time.]
I have a question about problem E. Consider this test case: 2 3 1 2 1 2 Considering that "Two fences shall be considered the same if the corresponding sequences of fence boards' types are the same", I think the answer should be 2 — a fence with board types A and B ((1,2),(2,1)) and another with types B and A (also ((1,2),(2,1))), where A and B are the two given types of fences. ((2,1),(1,2)) would be equal to one of these solutions, since only the type (and not the rotations) are considered during comparation.
However, according to an unsucefull hack attempt, the answer is 4. I asked it during the contest, and they said that a fence with types (A,B,A) and (B,A,B) is also valid, but I can't figure out how it's possible with fence lenght 3... Can somebody? Thanks!
If we called the first block A (1,3) and the second block B (1,3) The 4 valid fences are : (A , rev_B) , (B , rev_A) , (rev_A , B) , (rev_B , A)
(B rev_B) and (rev_B B) are not allowed:
Update: the upper comment has been changed. See reiracofage's comment below.
But "A, rev_B" is equal to "rev_A, B" according the statment...
Почему мой говнокод вечно проходит претесты :(
I took a look at the last example case and "deduced" that rotation also matters in the sequence comparison... I was getting WA locally for a long time, because that was not so clear from the problem statement, but I finally got it when there were about 10-15 minutes left; otherwise, I could have gotten C I think, using BIT :(
I took a look at the last example case and “deduced” that rotation also matters in the sequence comparison… I was getting WA locally for a long time, because that was not so clear from the problem statement, but I finally got it when there were about 10-15 minutes left; otherwise, I could have gotten C I think, using BIT :(
Does anybody know the solution to the Problem C? I try to use the Red Black Tree, but my answer is wrong..
It can be solved with treap.
Can I have the solution?
Авторского разбора контеста ждать?
Да, было бы неплохо)
on a separate note, why isn't the system test starting?? [NOTE: I said this at the time when the blog did not contain the update; don't get this wrong :)]
There is a mistake in author's solution for problem E. Now authors are trying to fix it.
would that mean the problem would get invalidated? the last example case would not be reconcilable... if the statement is wrong/example case is wrong, IT SHOULD HAVE BEEN ANNOUNCED during the contest. I took it as a case where the statement is wrong AND the example case is right...
I think trying to fix the solution retroactively won't really work.
This will be another unrated round now i think.
let's see what the admins say about this.
I think there is no mistake, just a problem is missing something like: Two fences shall be considered the same if the corresponding sequences of fence boards' types and dimensions are the same.
Too much thinking :) Your version and the initial one are different problems. Let's just wait the officials. Don't overthink.
I think missing something is also a mistake. I spend some time thinking and coding another method, and found I get WA on sample 3.
yea, I had to change my solution assuming something not stated within the problem statement, so as to fit the example test case (I thought something was missing in the statement but moved on, being under a time pressure) ;P
I didn't have any idea to count different types of board sequence. Can you share your code ?
you should get 18, on third sample.
Got the same answer. I wrote recursive DP with some hashes, comparing them at the end of recursion.
UPD: My Code here:
Usual dynamic programming, but as it will count duplicate cases also (like the ones on which author solutions are wrong) there is a way to count the number of these duplicate sequences separately and then subtract from original answer. To calculate duplicate cases, you need to consider the quantities of equal boards with different types, for example if there are K boards with the same size A x B and if required length is divisible by (A + B), then there are K * (K-1) * (K-1) * ... * (K-1) duplicates ((K-1) is repeated (length / (A+B)) * 2 — 1 times).
I`m not sure your solution be correct. there is a lot of possible paths (to build a fence), that have same sequence types with different width and length. I meant your solution doesn't count all paths.
Show example in that case.
I have a close idea with yours during the contest. But I think the subtract method you mention works only for A[i]!=B[i]. If A[i]==B[i], you should have a different subtract method or deal with it when dynamic programming.
I have excluded A[i] == B[i] during dynamic programming, you can just check if A[i] == B[i] then don't consider the variant when the board is rotated.
There is a bug in authors solution to problem E...Read the blog again...Its updated...I think this round is going to be unrated :(
I respect your opinion but I think that should be rated for div 2 because several people made a big effort to solve other exercises, including me. Thanks.
а как решалось D?
Думаю, что префикс-функцией.
а можно поподробнее?
Она решалась чем-угодно. Нам подойдет даже обычный перебор, ведь нас интересуют числа, которые являются делителями обоих длин. Максимальное число делителей числа в диапазоне 1..100000 — 128. То есть 128 раз будем втупую проверять.
Мда... Ну люди и извращенцы. Мой напарник написал КМП, теперь от Вас слышу ту же идею. Можно тупо перебирать все делители длин строк и двумя вложенными циклами проверять: действительно ли можно разделить строку на столько частей. Дальше, я так думаю, решение очевидно.
так писал 10 раз получил ТЛЕ, на 11 прошло но 770мс
Вы, возможно, извлекали подстроки и попарно за линию их сравнивали?
я тоже так подумал, пока её не сдало далеко больше 100 человек :)
Заметим, что длина искомого делителя должна нацело делить длину обеих строк. Т.е. перебираем все делители длин строк(их будет порядка корня какого-то, может кубического, из длины). А дальше для каждой длины в лоб проверяем подходит ли.
В лоб. У нас порядка log(N) делителей длины. Проверка "s[:i] — делитель s?" делается за O(N). Итого O(N logN)
Откуда такая оценка?
http://www.codeforces.ru/blog/entry/651
http://www.codeforces.ru/blog/entry/3863
Из прекрасного сна (я туплю). Да, кубический корень. Что всё равно, казалось бы, нормально проходит.
При больших ограничениях, чем эти, ты бы серьезно прогадал с такими оценками.
Контест то что надо, правда без авторских ошибок было бы на много лучше !!!
Ошибки в условии после контеста это то что надо ? мда..
Да, но в целом всё было нормально , и давайте простим авторам эту редкую ошибку.
скорее за то, что автор накосил с решением, а не условием
Как-то долго систесты не начинаются...
Соглашусь с предположением выше: думают, что делать с Е.
Пусть tourist норм решение им напишет :)
Как можно решить задачу 182B - Календарь Васи?
for (int i=1;i<=n-1;i++){cin>>x;ans+=d-x;}
молча, не?
Да ты опасен, не?
да
ААА) Только сейчас твой ник увидел :DD
:D
А если я люблю поговорить?
разговор с самим собой? ты еще более опасен
Как ее можно не решить?
Спроси у последних 60 человек
Черт, да здесь полно людей, которые могли бы на полном серьезе написать: "Как тут можно все 5 за час не решить?оО" Не знаешь, почему они так не делают?
может потому что они написали все за час и ушли, не?
Я говорю о тех, кто див2 даже и не пишут. Проблема в том, что далеко не все любят тешить свое самолюбие, гоняя понты перед зелеными после див2.
С учетом того, что автор вопроса сдал совершенно адекватное решение B на 20й минуте, я рассматривал вопрос как шутку на тему вопросов "как решать".
Как мы можем решить 182D - Общие делители?
я писал изврат с кмп, но можно гораздо проще влоб ищем общие делители длин этих строк и за линию проверяем требуемое условие
:)
универсальный алгоритм...
Спасибо, но я не понял этот язык.Я знаю С++.
Зачем голову столько раз включать?
Потому что у многих людей после head.think() она вырубается :).
и в конце: head.turnOff();
Наверное, turnOff должен при необходимости вызываться в Head.
Не знаю, лучше без этого, а то можно RE словить :\
Я просто для длин строчек находил делители, потом проверял является ли делитель длины делителем строчки, а потом за квадрат находил общее.Не знаю только пройдёт ли, как вы думаете?
почему?
потому что 10^5 в квадрате это 10^10
Максимум делителей у числа от 1..100000 — 128, тогда 128^2 влазит в 2 сек спокойно!
тогда выражайтесь точнее за квадрат чего вы решаете. вообще странное решение...
По-моему самое простое...
Согласен.
Такое, странное, решение писал почти каждый 5-й.
Но только у избранных оно прошло :))
42
М-да, я в этой задаче тоже залажал, ибо не сразу понял, что соль в делителях чисел, и делал перебор, но, благодяря тому, что сравнения строк делал с помощью хэшей, асимптотика получилась вполне сносная)
Прошла!))
UPD: к сожалению обнаружена ошибка в авторском решении по задаче 182E — Деревянный забор, ситуация будет исправлена как можно скорее, приносим участникам свои извинения
Значит ли это что вы собираетесь исправить авторское решение и тесты после контеста, то есть после того как участники приложили двойные усилия и постарались понять что вы имели ввиду, а не то что было написано?
Да-да, пожалуй, лучше считать, что бага не в решении, а в условии.
Бага в текущем положении. Моя задача D сейчас показана как упавшая, хотя до ее тестирования еще далеко. (она у меня была поломана и отправлена ближе к концу контеста).
system testing is in progress... what's admins final decision?
See blog above: UPD2: the contest is declared unrated.
it's a pitty
Я, конечно, в контесте налажал, и, скорее всего, получил бы минус к рейтингу, но все равно жаль, что нерейтинговый контест(
Капец, так хорошо написал и тут вдруг: UPD2: контест объявлен нерейтинговым.Нет слов!
С января пишу только анрейт контесты. Тиммейт попросил пописать раунд, потренироваться. Написал. Анрейт. Судьба. :)
Ненавижу анрейты — нет никакого адреналина от их написания.
Был, особенно когда Д тестировалась, но потом резко упало настроение, ну жизнь то продолжается :D
Ну тогда же еще не было известно, что контест анрейт.
Но хотя тренировка никогда не помешает.
Несправедливость!!!!!!!!!!!!!!!!!!!!111
да что ж такое, все никак cf не начнет стабильно хорошо делать контесты(
да нормально, хватит ныть =)
да мне как-то параллельно, но почему то тс может нормально раунды делать, а кф иногда косит (скажем так, кф косит чаще, чем тс)
Особенно последний раунд TCO)
В силах каждого участника — попытаться это исправить, став автором.
I didn't consider to types of board, just i checked rotation of square board with same type shouldn't count twice, and got Accepted! I think something is wrong yet.
Прощай мечта стать синим до следующего контеста !
Прощайте, опасения стать зелёным по итогам этого контеста)
Хехе, +1)
My comment was wrong, sorry...
Right, you suddenly decided that your comment became wrong the moment it got downvoted a lot :)
Может для подобных случаев сделать опрос среди участников? или бредовая идея?
Какой опрос? Явная бага в условии => анрейт раунд. Все в порядке вроде бы.
Whats case 15 in Problem C?
Try this smaller test cases:
out 16
out 7
Обидно, что так получилось с Е все-таки.
Приношу авторам контеста свои извинения за, возможно, некоторую резкость.
Большое спасибо за контест. В целом, он, скорее, всё же понравился.
Задачи интересные были, жаль что идею на задачу 'С' не успел реализовать(
у всех нас уже далеко не первый, не второй и не третий контест) но кстати первый анрейт( самим обидно, ведь все задачи были хороши
Был интересный контест.Жаль что я не сделал Д только по тому што думал што ето решение с поиском делителей долго работает.
Орфография? Не, не слышал...
spending my time from 22.00 — 02.00 waiting the systest while I have mid test in the next day and the contest end with unrated. . what a pitty. .
Comment deleted after a bit of thought, for more details read my reply 2 branches down this comment :)
Oh seriously, how the hell is that anywhere near a trivial question or a "bad contribution to the community" that it gets downvoted?
Is it a good contribution or a non-trivial question, really? :-)
On a serious note, the editorial is already published here, it's just not translated into English yet. Most problem setters on Codeforces are Russian-speaking, so translating editorials takes longer than writing them, and it's a lot of work. Have patience.
Yeah, thanks Nickolas. I'm not trying to justify my comment or anything; but I was frustrated about my bad performance yesterday :) To tell you the truth, I think I don't actually care about the editorial, I just wanted something to complain about. Sorry and thanks again!
There is russian one
Thanks!
How did so many manage to solve E during the competition? It only passes if you make the same mistakes as the author; the answer to the first test case should be 3 since the second board lying down is a beautiful fence as well. You can see on the second test case that just having one board is okay.
Very old blog, but incase someone is stuck on problem C like I was, the idea is to maintain a set of K maximums using two sets.