Всем привет.
Сегодня я (ir5) и rng_58 — авторы раунда. Во время контеста вы повстречаете разных животных и попробуете решить несколько задачек для них.
Мы искренне благодарим координатора задач (RAD) за тестирование и прорешиваение, Maria Belova за вычитку английских текстов, и MikeMirzayanov за отличную систему.
If so including images will be nice :)
С удовольствием бы написал, но время для меня неудачное.
Будут когда-нибудь раунды не в 19:00?
D: x3
По-моему, что-то тут не так :)
жружду разбор задачи D.Iterative-deepening :)
Но я не до конца уверен в правильности своего решения.
Сначала делаем подмену. Рассматриваем разности соседних лампочек (или что там было).
Теперь одна операция - это изменение двух лампочек на расстоянии a[i]. А всего надо поменять ≤ 2K лампочек. Строим граф с вершинами (0, 1, ..., n) и ребрами между u и v, если |u - v| = a[i]. В нем находим БФСом попарные расстояния между вершинами, которые надо менять. И в полученном графе из ≤ 2K вершин находим минимальное по весу паросочетание (тут как раз у меня только примерное доказательство правильности).
UPD. Прошла. Значит, все таки правильное решение.
Жаль так и не смог во второй задаче проблему со временем устранить ><
abcabcabcabc 3 abcabca bcab cabc
Ответ 4 0 или 4 6 или может ещё какой-нибудь 4 x. =)
мда натупил ...:)
As for me, I expected at least 30+ contestants would solve D correctly, but the result was only 6 ACs.
Overall, it seems that A,B was all right. C was solved by 200+ contestants, so I think C was actually not so very easy.
D,E are solved by only about 10 people yet. I believe those(D,E) are nice problems and you may learn something here.
---
Thank you for comments, Sir ivan.metelsky.
I could find no clue to solve...
I'm waiting for editorials.
Написано : К счастью, ей вскоре повстречался ее друг — бобром Таро.
Как мне кажется правильно: К счастью, ей вскоре повстречался ее друг — бобр Таро.
Если не сложно исправьте.
пока с глючным инетом боролся fsb4000 уже написал про неё.
теперь хз что с этим дурацким комментом делать...
Suppose one is hacking others' solutions and searches for a particular bug. When a solution seems to contain that bug, one is likely to challenge. Now, if the bug was in fact covered by pretests, he is surely wrong and is wasting time (and points if he is impatient with hacking). On the other side, if the bug was not covered by pretests, then the time is not surely wasted.
I propose that after locking a problem, one can submit solutions for that problem, they are checked on the pretests, and the result is reported back.
An existing way to get the same information is to first write and submit the wrong solution, and then submit the right one. But this way, it costs additional and points for the resubmission and for the time taken to write the wrong solution first. In my opinion, being able to get this information without the penalty would be fair and won't cause any harm when the problem is already locked.
But in general I completely agree with you.
Кому не лень, посмотрите http://pastebin.com/EUGZhij6
Где там ошибка ?..
Попробуй тест
3 0
тест
У вас выводит Ciel, правильный ответ - Hanako
Вообще, можно посмотреть протокол тестирования
Of course no, it's only an ethics, there are no any special secrets at that article.
EDIT: омг, и правда) спасибо)Однажды на ТС из-за такого бага я занял >100e место вместо примерно 20-го. С тех пор да, (int) пишется всё время и на автомате ;)
Кстати если Вы тоже используете компилятор g++ (насчёт студии не знаю), опция -Wall помогает отлавливать такие места, если они вдруг ускользнули от внимания. Да и вообще -Wall помогает против кучи глупых ошибок.
Ой, Аня, это ты =) а я в профиль не посмотрел, так официально на "Вы" обратился =) Этим летом поедешь в ЛКШ? ;)
А ты под линуксом, видимо, пишешь? У меня в Windows MinGW на scanf не ругается даже и со включенным -Wall. Ещё настоятельно рекомендую не забивать на ворнинги касательно приоритета булевых операций друг с другом (suggest parentheses around '&&' within '||') и с арифметическими (suggest parentheses around '-' inside '<<'). В последнем случае так вообще можно искать ошибку долго и упорно, если захочешь получить маску из единичек с помощью 1<<n-1, а не (1<<n)-1.
Cтранно...
Будем хранить максимальную длину ответа на предыдущем шаге.
Как пересчитывать - если мы сейчас стоим в позиции pos, и никакая из bi не является подстрокой s, начиная с pos, то мы можем увеличить ответ на 1 - ничего не испортится.
Если хоть одна из bi является подстрокой, то очевидно, что такую длину мы брать уже не можем. Поэтому новый ответ будет равен минимальной длине совпадающей строки минус один.
Итого решение за O(|s| * suml) (где suml - суммарная длина всех строк = 10 * 100) - прекрасно укладывается в TL.
Некоторые забывали проверить, что тупое решение укладывается и писали КМП или Ахо-Корасик :)
Для каждой неклёвой подстроки тупо посмотрим все её вхождения в исходную строку и для каждой позиции в исходной строке будем хранить две битовые маски - какие подстроки в ней начинаются и какие заканчиваются. Потом динамика такая: параметры - текущая позиция в строке и маска тех неклёвых подстрок, которые начались, значение - максимальная длина набираемой подстроки; в переходах маски начал плохих подстрок надо аккуратно складывать, а с масками концов - очень аккуратно перемножать. Работа над всем этим счастьем у меня заняла всего-то 79 минут, да при том, что я ещё зачем-то предварительно причёсывал набор стрёмных подстрок, чтобы они точно не были подстроками друг друга.
P.S. Позабавил товарищ подполковник, который, видимо, посмотрев на мои тонны кода, решил, что это должно отловить TL. Не, я, конечно, дурак, но не клинический всё-таки - предполагать, что на контесте по системе Codeforces я не проверю решение по такой задаче с грубой оценкой асимптотики самой трудоёмкой части алгоритма в O(|s|*2n*n) на простеньком макстесте, - это, простите, обвинение в вопиющем непрофессионализме.
У кого-то просто увидел такой код.
Я имел в виду того, кто пытался меня взломать.