Привет.
Сегодняшний раунд подготовил я. Меня зовут Михаил Тихомиров, я студент 4 курса мехмата МГУ, помимо этого работаю в Яндексе разработчиком-исследователем.
Хочется сказать спасибо Артему Рахову (RAD) за значительную помощь и грамотную координацию, Марии Беловой (Delinur) за традиционно качественный перевод условий, а также MikeMirzayanov за то, что все мы здесь сегодня собрались. =)
Раунд будет для обоих дивизионов. В каждом дивизионе, как и всегда, будет по пять задач, некоторые из которых будут общими, но не все.
Разбалловка:
Div1: 500-1000-2000-2000-2500.
Div2: 500-1000-1500-2000-3000.
Сегодняшний раунд - последний в 2011 году. Я хочу поблагодарить команду Codeforces, всех, кто придумывал, готовил или помогал готовить задачи в этом или прошлых годах, а также тех, кто способствует развитию проекта. Codeforces давно перестал быть просто платформой для соревнований по программированию, сейчас это - место, где каждому есть чему научиться у других, каждый может почерпнуть частичку опыта у более опытных товарищей при непосредственном общении, повысить свой уровень на контестах и тренировках, или просто получить удовольствие от красивых и оригинальных задач.
Пожалаем проекту удачного развития в следующем году и долгих лет существования.
Всем удачи. Желаю получить максимум удовольствия от сегодняшнего раунда и выступить на уровне.
И да, всех с наступающим! =)
UPD:
Раунд окончен. Всем спасибо за участие! Надеюсь, вам понравилось.
Победители.
Div1:
2. al13n
3. WJMZBMR
4. yeputons
5. romanandreev
6. dolphinigle
7. wata
8. Shef
9. shangjingbo
10. azizkhan
Div2:
1. s-quark
2. wayne-ho
3. emrevarol
4. agh
5. lzqxh
В конце раунда по техническим причинам несколько минут был недоступен сервер. К сожалению, мы не имеем возможности принять решения, которые вы не смогли из-за этого сдать. Из двух неприятных вариантов: делать раунд нерейтинговым и оставить все, как есть, мы решили выбрать второй, поскольку это затрагивает меньше участников. Мы приносим извинения тем участникам, на которых влияет это решение.
UPD2: разбор из ап.
А в сл. году планируются существенные сдвиги в сторону изначально задуманной философии Codeforces ?
The score of problem E(Div.2) is 3000! Unusual!
I also wish the whole codeforces team a very successful year 2012 and wish all the participants high ratings and great accomplishments!
Now, according to the given conditions, stripes must be vertical, i.e, the length of the wallpaper should go along the height of the walls. So, if length of wallpaper < height of the room. Cost is infinity.
Also, the wallpapers should only be glued vertically, i.e, when you cut the roll in pieces you have to discard the paper that is less than height of the room. For eg, If length=10, h=3. it will be cut in 3 pieces of 3 height. The 1x3 cut will go to waste.
You can assume that there is one wall with length=2*l+2*w and height=h, for a single room.
Решать нужно было в порядке ACBDE, видимо. Расскажите, как решалась E?
Обидно, что я написал D и только к концу раунда понял, что задача решается независимо по чётным и нечётным клеткам. Я сначала прочитал условие таким образом, что волна не может пересекать место, где проходила другая.
Cool story, bro.It isn't something strange that server becomes very slow for last few minutes, isn't it?
Для каждого гриба такое матожидание есть Zi * p1 * p2... * p2n, где pi - вероятность того, что его накрыло i-ым деревом. (Для удобства каждое дерево раздвоим на два - левое и правое). Соответственно, можно, например сортировкой событий для каждого гриба такуб вероятность посчитать.
Но я побоялся это делать - т.к. для этого пришлось бы какую-то временную переменную постоянно делить-умножать на разные вещественные числа. Поэтому я считал эти суммы с помощью дерева отрезков - от этого точность хромать не будет.
Такая паранойя обоснована, кто подскажет?
>pi - вероятность того, что его накрыло i-ым деревом
Each problem has 40-50 lines
And for me to translate the questions is very hard during the contest.
Aim of the problem statement should be to explain the problem to the participant not confuse him.
PS: I got 3 WA's on C, because I missed the following line "If a line has less than k vowels, then such line can't rhyme with any other line". It was written separately from other conditions.
Look at the following C++ function that is supposed to return the position of k-th vowel from the right of nonempty string s if the number of the vowels does not exceed k, or
string::nposotherwise.Is this code correct? If not, why?
Answer: when s has k - 1 vowels and (k - 1)-th vowel is at the beginning of s, this function does not return
string::nposthough it should.eeereaatktb
bee
iaattb
ottbee
Вывод
abab
Ответ
NO
isn't abab answer for this example ???
aatktb = aattb ?
So?
"For example, if k = 1, lines commit and hermit rhyme (the corresponding suffixes equal it), and if k = 2, they do not rhyme (ommit ≠ ermit)." So what was written?
this is test kind of this:
I have a wrong answer on test 39, too
Thank you very much.
I had O(NK log K) where the K log K came from just a single sort--seemed like it should be efficient enough.
I already wrote the editorial in Russian, and soon wiil translate it in English (if someone doesn't do that earlier).
Это всегда так смешно, когда ты называешь его черепашкой!
Жаль, что не смог поучаствовать в раунде.
Прошлый Новый год встречал синим, теперь фиолетовым. Прогресс на лицо и на лице :)
[The joins must be vertical and you cannot rotate. ]
A figure could have made the statements better.
And Is the match rated ?( as lots of people cannot submit in the last moment.)
Don't make it as "vote if you want it to be rated" .
May be we sud start learning it.
(It is the only contest being held in multiple languages)
(May be some day, it follows ICPC style or Topcoder style and make a single language contest, that way , nobody will get unfair language advantage.)
(Maybe its only my concern)
Это к тебе вопрос. Твоя программа aabb вывела.
Ненавижу такие задачи, как первая - которые как бы привязаны к жизни, но при этом к какой-то такой странной жизни, с комнатами без окон и дверей (не, ну будем считать, там люки в полу и потолке - эдакая квартира-башня) и какими-то невменяемыми правилами нарезки рулонов. Типа, разрезать и доклеить поперёк персонажу религия не позволяет, а резать повдоль - милое дело. :D
Но в целом очень круто, мне понравилось.
Потому что у решения "отсортировать, потом умножать и делить вероятность" был подвох в том, что после многократного умножения вероятность обращается в ноль, чего допускать нельзя. Поскольку это решение предполагалось очевидным (после осознания основной идеи), а предусмотреть такую багу было практически невозможно (во всяком случае, без претестов на это никто бы, скорее всего, об этом не подумал), было бы куча сабмитов, проходящих претесты, но валящихся на нормальных тестах. Это как-то не входило в исходное видение задачи (я про эту багу сам узнал вот недавно). Поэтому сложность была повышена, и участникам предлагалось это как-то дополнительно ко всему побороть "в светлую".
Однако были решения (которые я не предвидел), в которых такой проблемы не было и все было хорошо сразу. Это - недосмотр, каюсь.
Дерево отрезков помогает, да. Сканирующую прямую тоже можно довести до ума, чтобы она на этом не портилась.
Yes, I agree that this problem's difficulty is a bit too high for B div 2 (because of the statement). But anyway, I don't understand, why many people couldn't solve it. The comments to the example help very much. My first attempt got RE4 (because of division by zero), but it's pretty easy to see the source of it.
i failed in 37th testcase for problem 3 in div2..
on checking my submissions i am only able to see the small part of the testcase...
how to get the complete testcase ?
2 1
a
bi
bi
a
a
a
a
But please have some graph problems in future contests!
Thanks, Happy new year!