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

Автор Ripatti, 14 лет назад, По-русски
Привет всем!

Автором задач сегодняшнего раунда буду я. Это мой второй раунд на codeforces. Надеюсь, он Вам понравится так же, как и первый.

Удачи!

UPD.
Победитель - unicef.
Разбор задач.
  • Проголосовать: нравится
  • +102
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

а на какие темы будут задачи?

14 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Удачи всем! 
14 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится
Скажу уже традиционное: пусть победит сильнейший :)
14 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Всем удачи на этом контесте и easy hacking!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Which was your first one?
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
It was Round #59
14 лет назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Блин, прозевал регистрацию :\
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Оказывается в России время передвинули
Я чуть тоже не прозевал =)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не знал, что Россия перешла на летнее время. Из-за этого пропустил раунд, которого 2-3 дня ждал...
  • 14 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится
    Больше смен летнего/зимнего времени в России не будет. Этот переход был последний.
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
I have a doubt regarding the contest timings.In the mail I received , its mentioned that the timing is Tuesday, March, 29, 2011 16:00 (UTC)  
which turns out to be 8:30 pm in India.
But in the last codeforces match codeforces beta-64 the timing mentioned in the mail was  Saturday, March, 26, 2011 16:00 (UTC)
which turns out to be 9:30 pm in India.
How is it possible that the same time on different days is differed by 1 hour?
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Problems D and E were not what I expected from codeforces.
Reading input and Writing output in Problem E was the hardest point in this problem and this is not how the standard codeforces tasks look like.
I hope problem setters understand that it's not cool to make the output readable for humans by making it long and hard-to-print.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится
    I guess that output format that contains not only "YES" or "NO" is needed to check that answers found by participants are correct as well as to check that situation when contestant found the solution while the author program didn't , doesn't happen. I didn't like it much either, but it is understandable.

    Besides that I don't think that reading input and writing output is the most difficult part of problem E but we shall not discuss that before the end of the contest:)
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится
    Think output format for D should be tested on pretests completely and not give penalty for it, because I received +3 on it with forgotten dot at the end and double space :( .
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
глянул задачу E - что-то не очень понравилась

вбивать 100 констант - это, извините, перебор =/

и почему 100? для 112 химических элементов установлены общепринятые названия; вряд ли кто побежит за книжкой двадцатилетней давности, чтобы выписать оттуда все элементы
  • 14 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится
    Саш, я согласен по поводу некорректности задачи, но я сделал так: взял таблицу из википедии и скопировал в текстовый файл, удалил немного лишнего, после чего прочитал cin'ом и сгенерировал код инициализации map'а :)
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится
    эта задача искренне улыбнула )
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
  • 14 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится
    А чего тут такого сложного?.. из педивикии одной строчкой на perl-е выдирается ;)
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      да, печально, что это не какой-нибудь онсайт, где нельзя пользоваться интернетом...
      • 14 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится
        Разве что это был бы онсайт для студентов-химиков...
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Я, когда был маленький, помнил и таблицу Менделеева, и столицы всех стран, и всю транспортную сеть своего города наизусть... Сейчас совсем ничего не помню :)

          А контест хороший получился. Жаль, что я большую его часть ехал домой

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какой 4-й тест у задачи D?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У Б написал интуитивное решение. Но почему 12 1 9 ответ 1 0 0 ( ...нули), а у 12 1 8 ответ 0 0 0 (...нули)?
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Наверно, потому что 0.08 < 0.08(3) < 0.09.
    А откуда у вас такой тест?

    upd. А, поняла, видимо, это ваши взломы.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится
Очень понравился контест, спасибо!

Во-первых, порадовали факты о претестах, упомянутые в условии. Побольше бы так.

Во-вторых, весело, что в задаче E ВНЕЗАПНО нужно уметь пользоваться поиском. На Div2-контестах, которые позиционируются как учебные — учить околоконтестным вещам, таким как использование поиска и обработка его результатов, я считаю вполне уместным. Те, кто выписывал руками 100 строк из книжки, вероятно, поругаются, зато узнают, как делать это быстрее.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
-67 взломов это рекорд? =)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хнык, не успел отправить 5-ю из-за того что сначала не написал YES потом написал Yes и ток потом исправил на YES :(
14 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится
 Уважаемый администратор, можно пожалуйста сделать так, что бы отправки которые в очереди, не выделялись красным цветом, а выделялись например серым или желтым. А то смотрю у меня все красные, я чуть со стула не упал, а оказалось они просто в очереди ;)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Присоединяюсь к просьбе, уже давно, по-моему, пора это исправить...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Третья задача очень понравилась. Жаль что так долго тупил с ней. :))
14 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
problem C was nice, understandable and approachable both :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry, I am afraid of  saying that this contest is a little boring,the last two problem needs too much code ,but few about algorithm!.

14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
оууууу... Ну зачем так много реализации? Пол часа не мог заставить себя начать писать 4-ю T_T
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно каким образом происходит тестирование? Потому что у меня уже AC по С, но B даже нету еще в очереди, хотя я её сдал гораздо раньше, чем С и, вроде, у всех она уже протестирована =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Все сабмиты тестируются по времени их отправки. Присмотрись внимательнее- может уже есть вердикт.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Только что протестировалась.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Иногда бывает, что решение зависает на каком-то тесте(у меня один раз такое было). В этом случае задача будет тестироваться после того как протестируются все решения остальных участников.
14 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
I agree with what some people have said, problems D and E were not quite the best.

A: was very straightforward, but that's fine, specially in div 2 only.
B: was easy but needed a little thought.
C: was great, the statement was clear, needed thinking and solutions were nice.
D: was long and boring overall, just tons of code without much thinking was enough.
E: I didn't have time to tackle it in the contest, but seemed approachable, but I really didn't like the fact that looking for periodic tables was part of it. That may be more real life like, but in programming contests the speed and skills to find a periodic table that can be put on code fast seemed overly boring to me.

NOTE: I just mentioned this as my opinion, I appreciate all the effort the codeforces team puts into the contests, but those last two problems seemed to me that having div 2 only so often is making the writers to run out of nice problems quickly.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    The problem setter could have easily replaced the atomic symbol with just atomic number or provided atomic symbol along with atomic number. Then it would have been a great problem... In programming contest even in the online contest searching google for data can be just interesting but not conventional. Here we are for our coding and algorithmic contest , not for searching contest... by the way problem E was very good if we ignore this fact..
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче B многие участники писали реализацию с действительными числами, что несколько затрудняло взлом. (Вроде и понятно, что этот код не проходит все тесты, а искать числа на которых округление произойдет неправильно -- лень.)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hi, firstly, nice contest!

But… :) I think there was too "coding hard" problems D and E. In problem E, i would appreciate for example list of all possible atoms, cause i won't have to rewrite them by hand…
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Yes, they were hard to code, but they were interesting) 

    I also think, that is was good contest!
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
my C failed just because of array size,RTE. felling terribly bad.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кажется, в середине системных тестов C задача была отмечена как непрошедшая тесты, а в конце всё-таки прошла. Интересно, это банальные ошибки в тестах или что-то еще случилось?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не обращай внимания на отметки в середине процесса тестирования.
    Двойной клик на ячейке с задачей покажет, что действительно с ней там сейчас творится: не прошла систест, или ещё в очереди.
    Здесь интерфейс построен так, что, если задача послана не с первой попытки (скажем, +1), то, пока она ещё в очереди и систест до нее не дошел, в таблице она отображается как -1, хотя в принципе вполне может быть правильной. Двойной клик покажет, что она "в очереди". Когда до нее дойдет систест и проверит, и она окажется верной - "-1" изменится на число очков.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Нет-нет. Именно наводишься и видишь "Не пройдены системные тесты". Примерно так. То есть она была выделена была ярко красным, а не просто -1
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Why is ratings change taking so long?

Plus, it is a bit weird that so many people end up having the same standing in the contest (same score). Thus you could have a standing of say a 90, only to find out that there are actually 300 people above you. I think we need a more granular scoring system.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
system test taking longer than usual.. I guess ratings change will take longer too..
14 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
system test taking longer than usual.. I guess ratings change will take longer too..
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин! Выводил в D, когда два джокера, ответ для каждого джокера в отдельной строке, а не в одной, поэтому свалилась на 4 претесте и я не понимал почему, что за фэйл =( читать условие надо нормально -_-
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
народ......а этот контест был рейтинговый????
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Такое ощущение, что задачи D и E были сделаны от безысходности. Как будто автор посчитал, что первоначальные задумки слишком легкие для уровня D и E и решил напихать побольше всякой всячины в условия и входные данные, чтобы повысить уровень сложности. Лучше бы D сделали на какой-нибудь стандартный алгоритм типа MaxFlow, Ахо-Корасик. А E сделали просто с обычными числами. Было бы гораздо приятнее решать и пользы было бы больше. Все же лучше много думать, чем много писать.
А так могу сказать, я что я просто убил 2 часа времени впустую, львиная доля которых пришлась на D.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня вот почти два контеста готово для первого дивизиона, но нет ни одной достойной 2500й задачи (тем более 2500 див 1). :-(

    Вот сам не знаю что делать с ними...
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А у меня почти готов Div 2 контест, но нет, как ни странно, одной из легких задач. Ничего в голову не приходит! Удивительно просто
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Можно сделать 2 контеста с совместным авторством.

        Да, с простыми у меня тоже были проблемы, но их то придумать легче, чем 2500е. :-)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Аналогично.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а можно как-то посмотреть каким тестом взломали? а то взломанное решение все финальные тесты проходит.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ух ты. А что, взломы не добавляются в комплект финальных тестов?
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Что-то рейтинг долго не обновляется...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
да, что-то очень долго....
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I have a question about Problem E. 

Input:
5 2
H H H H H
He He

Which is expected answer ?
---
NO
---
or
---
YES
H+H->He
H+H->He
---

In fact, I passed both pattern solutions in practice.

... Or , is this invalid input?

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Н-да... в C, оказывается, полный перебор укладывается в TL. А я мудился с отсеиванием делителей...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
you mean problem 3?
14 лет назад, # |
Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится
Problem E was too easy to code? You could have replaced the atom names with the number of their atomic number in words. In other words, you would say ninety nine instead of 99. This can be variable (ex you can say ninetynine or ninety-nine or in any human understandable format, occasionally also replacing with roman numerals). Also you could have removed the restriction of 100 and made it all the way to thousand (or one thousand). This would have made the contest more interesting.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    I don't agree. For me the most difficult part of your problem is English knowledge.  (native speakers have too much advantage).
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Вы видели, участник Vasya умудрился набрать -2886(с минусом)! И при этом он сержант после первого участия. :-O
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    О_о у меня первый раз когда писала было 222 место, 2 решенные задачи, а тут есть люди без единой задачи, местом гораздо ниже... а рейтинг больше чем у меня после первого контеста... КаК?
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
      У этого молодого человека зашла задача А. Он не без единой задачи. Вы выступили лучше, но судя по http://codeforces.me/blog/entry/1601 ваш рейтинг считали по др. формулам.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        У Vasya да, одна зашла. Я про других. 


        Да и вроде форму подбили так, что наоборот должно было быть)

        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Формулу подбили так, что абсолютное значение изменения рейтинга уменьшилось, ведь действует принцип, что сумма изменений равна 0, следовательно если рейтинг увеличивается меньше, то и уменьшаться он должен меньше.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Думаю, дело в том, что каким бы маленьким штраф бы не был, ниже последнего места он не упадет. Рейтинга до этого у него не было, и его ожидаемое место считалось по формуле 1 + n / 2, где n– общее число участников раунда . Число участников 1103, значит ожидаемое место 552, он занял 664, согласитесь, разница не большая. Вот он и упал на 79 (как такая цифра получилась, не могу сказать, так как формулы мне не известны). Автоматически присваивается рейтинг 1500, как результат с таким падением у него зеленый цвет.
    Все просто.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Непонятно, почему при количестве участников 1103 последнее место - 664-е.
      Логично было бы рассчитывать ожидаемое место среди тех, кто участвовал, а не среди тех, кто зарегистрировался. Особенно если учесть, что регистрируется почти в два раза больше народа, чем участвует (если будет в два раза больше, а до этого недалеко, у новых участников вообще не будет шансов упасть в рейтинге?).
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Формула (и цитата) взяты отсюда http://codeforces.me/blog/entry/102 . Если честно, я сомневаюсь, что расчет идет от 664, потому что не могу представить как при seed  равном 332 можно получить изменение рейтинга -79, если занял место в два раза хуже.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А вот смотрите, там же,
          339 место - MuravjevSlava, до контеста у него был рейтинг 1636 - то есть почти максимально возможный для div2, соответственно, ожидаемое место, наверно, в двадцатке. Разница в ожидаемом и занятом примерно та же. Изменение рейтинга - -77.

          (Дурацкое какое-то занятие, гадать, лучше бы эти изменения были более прозрачными.)
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Мне не понятно, к чему ваш пример. Формула написанная мной используется только для тех, кто не участвовал прежде, как ваш пример опровергает то, что n– общее число участников раунда до раунда? 
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Пример к тому, что вы не можете представить, как можно получить изменение рейтинга -79, заняв 664-е место при ожидаемом 332-м (думаю, тут важна разность позиций, а не их частное). При этом есть еще один участник, который занимает 339-е место при ожидаемом хотя бы двадцатом (точно считать лень, но где-то так). Разницу здесь можно считать известной, и она примерно та же, больше 300. Изменение рейтинга примерно то же, -77.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Я думаю, что на самом деле расчитывается исходя из 664 мест, т.к. тем, кто не участвовал рейтинг не пересчитывают.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
пост не в тему:
(не знаю где написать)


когда следующие контесты?
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Spasibo Ripatti. v konteste bili klassnie zada4i!! Respect! :D
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Соревнований уже давно нет. Кто-нибудь знает почему?
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I'm confused that some test case(just like #85) in problem E take over 20s to get result in my own computer, but it still got AC(with 600 ms) when I submit. Why ? I have tested some codes of others' and have the same problem. I don't think my computer runs 50 times slower than the server's. 
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    May be you compile your code in the debug mode or in the release mode without -O2 flag.