Блог пользователя Endagorion

Автор Endagorion, 13 лет назад, По-русски

Привет.

Сегодняшний раунд подготовил я. Меня зовут Михаил Тихомиров, я студент 4 курса мехмата МГУ, помимо этого работаю в Яндексе разработчиком-исследователем.

Хочется сказать спасибо Артему Рахову (RAD) за значительную помощь и грамотную координацию, Марии Беловой (Delinur) за традиционно качественный перевод условий, а также MikeMirzayanov за то, что все мы здесь сегодня собрались. =)

Раунд будет для обоих дивизионов. В каждом дивизионе, как и всегда, будет по пять задач, некоторые из которых будут общими, но не все.

Разбалловка:

Div1: 500-1000-2000-2000-2500.

Div2: 500-1000-1500-2000-3000.

Сегодняшний раунд - последний в 2011 году. Я хочу поблагодарить команду Codeforces, всех, кто придумывал, готовил или помогал готовить задачи в этом или прошлых годах, а также тех, кто способствует развитию проекта. Codeforces давно перестал быть просто платформой для соревнований по программированию, сейчас это - место, где каждому есть чему научиться у других, каждый может почерпнуть частичку опыта у более опытных товарищей при непосредственном общении, повысить свой уровень на контестах и тренировках, или просто получить удовольствие от красивых и оригинальных задач.

Пожалаем проекту удачного развития в следующем году и долгих лет существования.

Всем удачи. Желаю получить максимум удовольствия от сегодняшнего раунда и выступить на уровне.

И да, всех с наступающим! =)

UPD:

Раунд окончен. Всем спасибо за участие! Надеюсь, вам понравилось.

Победители.

Div1:

1. ivan.popelyshev

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: разбор из ап.

  • Проголосовать: нравится
  • +227
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
С наступающим!
»
13 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится
я думал последним будет 100 раунд :)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится
    Сотый раунд будет первым в сл. году, и я думаю первым без приставки Beta.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      Вот это очень вряд ли. Ведь  смысл Codeforces не в раундах, а в том, что в будущем можно будет самому делать контесты вообще без каких-либо контактов с администрацией.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится
        Жаль. Просто это было бы очень символично.
        А в сл. году планируются существенные сдвиги в сторону изначально задуманной философии Codeforces ?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится
    представь что нумерация с 0...
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Последний?
Жалко, как никак еще одна неделя до НГ, так что 100, юбилейный можно было бы сделать.

Спасибо за #99. Ждемс.

PS
>>в Яндексе разработчиком-исследователем.

Можно чуть-чуть по-подробнее? Интересно.
»
13 лет назад, # |
Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

The score of problem E(Div.2) is 3000! Unusual!

»
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Merry Christmass for you all.
It's Christmass now in indonesian ^_^
I got a gift from Codeforces : 
Beta Round #99
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится


»
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Merry christmas everyone!
I also wish the whole codeforces team a very successful year 2012 and wish all the participants high ratings and great accomplishments!

»
13 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится
Ааа я думал турнир как обычно вечером - не успел зарегаться =( Админы зарегайте меня на турнир, если это ещё возможно...
»
13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
Билайновцы козлы. Ровно за 10 минут до начала раунда у меня отрубился интернет и начал функционировать только сейчас. Почти все цели, поставленные мной в этом году, окажутся не выполненными. Как же я хотел написать этот раунд, хотя бы попытаться закончить год на положительных эмоциях. Увы. 
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    всмысле?) цель мне помниться была стать красным.... и ты за один раунд хотел выйти в красные?  и вообще может это и к лучшему, что не участвовал, исправил бы положение к прошлый раз
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Русским языком повторяю - цели я не выполнил, хотелось просто закончить год на положительных эмоциях.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ссылка на 60 раунд, конечно же, в тему.
»
13 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится
Readforces has come again...
»
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Problem B was out of my mind...Can someone explain what problem B really is....
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I don't know too!
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You have to paper a room using one wallpaper only. However, multiple room can have same wallpaper. So, for each room you go through all the wallpapers and decide which one to buy.
    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.
»
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
You should extend the contest. Server wasn't responding during (at least) one last minute.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    I was trying to hack, and had a test ready 70 seconds before the end, but it wasn't submitted when I pressed "hack".
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится
      Well, now I'm not disappointed: this hack wouldn't affect my awesome 2nd place :).

      P.S. Аааа, я на глагне!111
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Even though I got the rating increase I think that this contest should be unrated...
»
13 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится
Только у меня Codeforces последние две-три минуты раунда все грузил очень-очень долго?
»
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Отличные задачи, спасибо! Жду еще ваших контестов =)
Только у меня CF не хотел принимать решения? За 3 минуты до конца нажал "отправить", так и не приняло... Будет очень обидно, если оно зайдет в дорешке.
»
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
I can't submit in few last minutes (502 Bad Gateway) :(
»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Спасибо автору за раунд. За возможность поторчать половину контеста в тройке лидеров :-)

Решать нужно было в порядке ACBDE, видимо. Расскажите, как решалась E?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я решал в идеальном для себя порядке (т. е. перестановка с максимум очков при условии, что на каждую задачу я трачу столько времени) и у меня получилось CADB
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я видел. Если бы контест длился час, то ты бы был на первом месте, а я на втором :-)

      Обидно, что я написал D и только к концу раунда понял, что задача решается независимо по чётным и нечётным клеткам. Я сначала прочитал условие таким образом, что волна не может пересекать место, где проходила другая.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Обясните, пожалуйта, почему ето верно.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          В силу того, что волна идет только по диагонали, она может задеть только клетки, совпадающие по цвету с нашей в шахмтной раскраске. Стало быть когда мы активируем клетку, можно обрщать внимание только на клетки того же цвета. Значит решать задачу можно по отдельности для черных и для белых. Как-то так?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я сначала писал по схеме ACDB, потом понял, что кое-что не додумал в D и поменял схему на ACBD.
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Блин, написал C за минуту до конца, захожу отправить - CF висит :(
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Это нормально, что в последнюю минуту посылки не отправлялись?
»
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Hard Contest :\
»
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Я забыл про перекрестную рифму и заблокировал задачу. Нужно было лучше слушать на литературе.
»
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
I don't think this is a good contest.It is hard for me to understand the meaning of the description.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    yeah, I think so. I don't know the meaning of the problem B yet.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    I got a Accepted at problem C, the decription of the problem is very bad , I think ,not only at this problem. " The total length of the lines does not exceed 104 " don't you think this sentence is strange?
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
отличные задачи, злые правда :)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I also ca not submit during the last minute.......which is very serious for me.....sad
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Hi there
I have submitted a problem in last few seconds but got a 504 error! And now it's not submitted!!! :(
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Even I couldn't submit in the last couple of minutes. The site went unresponsive and I got some 502/504 error. It appeared with 30s left on the clock . I selected the file and clicked on submit and that request also timed out.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как решать задачу С(див1)? 
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Матожидание линейно, значит матожидание суммы крутизн выживших грибов это сумма матожиданий крутизны каждого гриба по-отдельности (т.е. нуля, если он умер, или его магической силы, если он выжил).

    Для каждого гриба такое матожидание есть Zi * p1 * p2... * p2n, где pi - вероятность того, что его накрыло i-ым деревом. (Для удобства каждое дерево раздвоим на два - левое и правое). Соответственно, можно, например сортировкой событий для каждого гриба такуб вероятность посчитать.
    Но я побоялся это делать - т.к. для этого пришлось бы какую-то временную переменную постоянно делить-умножать на разные вещественные числа. Поэтому я считал эти суммы с помощью дерева отрезков - от этого точность хромать не будет.
    Такая паранойя обоснована, кто подскажет?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Я тоже самое написал. Вроде норм, хотя я видел у ivan.popelyshev, что он брал логарифм и делал прибавление на отрезке, а не умножение
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Обоснована переполнением экспоненты. А вот если умножение заменить на сумму логарифмов, то всё будет хорошо :)
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      хм. Я писал сортировку событий, но повалился на пятом претесте.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я делал почти также, только вместо произведения переводил все в логарифмы и получил дерево с интервальным добавлением и одиночным запросом. Не успел заслать.
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      >pi - вероятность того, что его накрыло i-ым деревом

       или все-таки "не накрыло"?

      UPD делить/умножать переменную в дорешке зашло...
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      постоянно делить-умножать - проходит и с long double и просто c double
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Сначала идем слева направо и поддерживаем информацию, с какой вероятностью ни одно дерево не упадет на текущую позицию, если упадет направо (здесь не учитываем те деревья, которые точно упадут направо) и количество деревьев, которые точно упадут направо. Пересчет легко - надо просто помнить для позиции, какие деревья тут находятся и какие концы деревьев, упавших направо тут находятся. Проставляем вероятность выжить для каждого гриба (если есть хоть 1 точно упавшее - 0, иначе - та самая вероятность). Отдельно рассматривать точно упавшие направо деревья надо, чтобы операция была обратима. Потом проходим так же справа налево, домножаем на новую вероятность выжить. В конце просто перемножаем вероятности и силу
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I couldn't access the site in the last 5-6 minutes! Kept on giving me 504! Also, problem B? What was that? The question seemed fine, but the explanation of the test cases was just... weird!
»
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
В чем особенность 5-го претеста задачи С?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Обидно, Е упадёт по ТЛ-ю, времени улучшить не хватило ровно столько сколько я тупил над тупой багой в D.
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I couldn't submit at the very last moment... after fixing the stupid bug of D... and the problem description was horrible to understand.....
»
13 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится
It is a very bad contest.
Each problem has 40-50 lines
And for me to translate the questions is very hard during the contest.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только сейчас подумал... в 138C - Грибные гномы - 2 сложность O(n*m)?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Не думаю, что пройдет. У меня O(n log n + m log m)
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится
      Почему-то проходит O(nm) за 560 мс, sqrt-декомпозиция - за 250 мс
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I liked the contest, though problem B was exceptionally weird. Also, during last one minute I wasn't able to open solutions for hacking.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Why do you think problem B is weird?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      A single sentence had several conditions. The conditions should be broken down in form of points, so that they are readable and understandable.
      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.
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I was stuck in Problem A due to a little bug that crept in...  I turned it to a problem:

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::npos otherwise.

size_t kth_vowel(const string& s, int k) {
  assert(s.size());
  size_t pos = s.size();
  for (int i = 0; i < k; ++i) {
    --pos;
    pos = s.find_last_of("aeiou", pos);
    if (pos == string::npos) return pos;
  }
  return pos;
}
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::npos though it should.
»
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Сегодня тестов меньше или улучшили процесс тестирования? 
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
одна опечатка и 220ый вместо 11ого... жесткий раунд.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я 15 минут не мог сдать первую задачу, потому что был уверен, что в неделе 6 дней...
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
1 2
eeereaatktb
bee
iaattb
ottbee
Вывод
abab
Ответ

NO

isn't abab answer for this example ??? 

  • »
    »
    13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    aatktb = aattb ?
    So?

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      тот же тест. Всегда думал что s.find(char) вернет s.size() если нет элемента но он вернул -1 =(
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      there was written that you must check only vowels now t,k,b and other 
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        "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?

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hello,

would it be possible to upload somewhere test no 37 (problem C div 2)?

Thanks.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What was the intended solution for E? It seems like everyone timed out on case 27.
I had O(NK log K) where the K log K came from just a single sort--seemed like it should be efficient enough.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It can be solved in O(NK).
    I already wrote the editorial in Russian, and soon wiil translate it in English (if someone doesn't do that earlier).
»
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
ДАААААА!!!! Я всё таки буду встречать Новый Год красным!!!!!
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сдал 1 задачу на 11 минуте, получил 178 баллов. Почему так?)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    с 6 попыток. Каждая попытка отнимает баллы.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ппц, я прогоняю) Уже 5-ый раз участвую, и только сейчас заметил и узнал это... Эх, надо было внимательнее читать правила)
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Although the statement for problem B was understandable and I solved it correctly, It was not easy to comprehend all the conditions at once (may be my mind is slow).
[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" .
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ratings have been updated already.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    actually I can't understand problem B very well,the statement is quite complex.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Yes, It gives advantage to people knowing Russian.
      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)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задача С, второй див.
Объясните, пожалуйста, откуда здесь рифма?
Test: #48, время: 10 мс., память: 1368 КБ, код возврата: 0, код возврата чекера: 1, вердикт: WRONG_ANSWER
Ввод
1 1
e
e
a
e
Вывод
aabb
Ответ
NO
»
13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
First Contest to use google translate more than eclipse :)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Отправил это решение - получил WA 1 из-за того, что оставил отладочный вывод. Стер его, но отправить не смог из-за ошибки 504 (посылка в дорешивание). Вопрос к администрации: какого рода была перегрузка сервера - по процессорному времени или по интернет-каналу?
»
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Very nice contest. Thank you, Endagorion . I am blue for first time :)
Merry Christmas everyone :)
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ненавижу такие задачи, как первая - которые как бы привязаны к жизни, но при этом к какой-то такой странной жизни, с комнатами без окон и дверей (не, ну будем считать, там люки в полу и потолке - эдакая квартира-башня) и какими-то невменяемыми правилами нарезки рулонов. Типа, разрезать и доклеить поперёк персонажу религия не позволяет, а резать повдоль - милое дело. :D
Но в целом очень круто, мне понравилось.

»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Merry Christmas!!!
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
А может автор объяснить, почему он решил сразу раскрыть 12 претест к задаче C? Просто это бац и делает задачу в полтора раза проще.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Автор может.
    Потому что у решения "отсортировать, потом умножать и делить вероятность" был подвох в том, что после многократного умножения вероятность обращается в ноль, чего допускать нельзя. Поскольку это решение предполагалось очевидным (после осознания основной идеи), а предусмотреть такую багу было практически невозможно (во всяком случае, без претестов на это никто бы, скорее всего, об этом не подумал), было бы куча сабмитов, проходящих претесты, но валящихся на нормальных тестах. Это как-то не входило в исходное видение задачи (я про эту багу сам узнал вот недавно). Поэтому сложность была повышена, и участникам предлагалось это как-то дополнительно ко всему побороть "в светлую".
    Однако были решения (которые я не предвидел), в которых такой проблемы не было и все было хорошо сразу. Это - недосмотр, каюсь.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Такая бага предусматривалась: я о ней подумал, и решил нестандартным образом: с помощью одного дерева отрезков.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        Почему же нестандартным, я тоже так решил :)
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ты крут. =)
        Дерево отрезков помогает, да. Сканирующую прямую тоже можно довести до ума, чтобы она на этом не портилась.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Можно было не в дерево, а в массив добавлять, так константа чуть меньше.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        У меня дерево Фенвика, наверное идея такая-же.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        В итоговом решении я считал сколько раз нужно возводить в степень число x/100, для каждого x от 0 до 100. Но у меня на этом тесте решение много раз падало совсем по другой причине.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я делал так же, как Вася :) Всё ОК, работает за O(n log n + m * 101 * log n) = O(n log n + m log n), ведь 101 -- это константа ;)))
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Программа работает за 2с => O(1)
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится
              Странная какая-то у вас, Алексей, импликация :)
»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
The problem statement for problem B Div. 2 was very weird. I had the right solution but didn't submit it thinking there might be some extra conditions. Finally submitted and got WA ! Checked the test cases after contest and submitted my original one ! Accepted ! 
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    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.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    I have no idea what are you talking about, you submitted 3 times always with different source code:
»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
how to get the complete testcase ?
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 ?
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Очень порадовали задачи, респект =)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Да, задачи просто супер! Мне очень понравились тоже. Спасибо, Миша! ;)
    Ещё бы аксептедов штуки 3-5 по Е -- и вообще супер было бы. Оцениваю контест в 95 из 100 =)
»
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Although I have already accepted problem B div2 ... I still don't fully understand it :D
»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
In practice, what does the strange time 596523:14 mean?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Thanks codeforces for everything!

But please have some graph problems in future contests!

Thanks, Happy new year!