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

Codeforces Beta Round #14 (Див. 2)
Автор MikeMirzayanov, 15 лет назад, По-русски
Сегодняшний раунд будет не совсем обычным. Дело в том, что участники из первого дивизиона могут зарегистрироваться на него и принять участие вне конкурса. Этот раунд будем считать некоторым alpha-тестированием для этой функциональности, но к следующему див. 2 раунду можно ожидать стабильной версии.

Это раунд подготовили для вас: homo_sapiens, Julia, Nerevar, KudryashovIA и я.

Желаю высокого рейтинга,
MikeMirzayanov
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Заметил небольшой баг. Зарегистрированным вне конкурса вместо надписи Зарегистрирован показывают кнопку зарегистрироваться. 
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Too bad... I am so sleepy before the contest actually begins.
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
When are your contests gonna get rid of "Beta" status?
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В контесте участвовать можно, но результаты на рейтинге не отобразятся. Я верно понимаю?
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Золотой ник внеконкурсного участника на сером фоне это ужасно..)
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Удачи всем участникам!
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
"Для серии рисунков с изображением t-горбых верблюдов Вася хочет купить блокнот, но не знает сколько страниц ему понадобиться."

Должно быть:

"Для серии рисунков с изображением t-горбых верблюдов Вася хочет купить блокнот, но не знает, сколько страниц ему понадобится."

→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо, но обычно подобные комментарии лучше отправлять в личку.
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      На будущее, классный функционал - отправка опечатки автору по ctrl+enter
      → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можешь кто-нибудь рассказать, как нормально решать задачу D? :)
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Перебираем все ребра, соответсвенно мы разделим наше дерево по перебираемому ребру. Далее в каждом поддереве нам нужно найти путь, состоящий из последовательных вершин, максимальной длины(хотя лично мне понимание что есть путь стоило одной попытки). Это можно сделать одним дфс ом из корня. 
    → Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    еще как вариант перебрать 1 путь. Он разобьет дерево на несколько в каждом из которых надо найти 1 длиннейший. Если аккуратно написать то это 200^3.
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      я что то подобное и пытался писать. TLE 31))
      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        У меня тоже были TLE, пока я не перешёл с матрицы связности на списки соседей.
        → Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Кстати задача D имеет и  O(N)  решение... Для любителей дорешивать можно добавить тестик на 100000 вершин.
    → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а когда ждать пересчета рейтинга?
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Thanks for a good contest! The problems were interesting, and even connected logically. And the level of the problems was quite perfect for div II. Keep on doing well!
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
"образуют ли эти отрезки прямоугольник положительной площади"

это как? 
а еще отрезки могут выходить за прямоугольник? или они точно должны образовывать прямоугольник?
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    это означет что объединение отрезков является связной фигурой, четырех-угольником. каждая из сторон параллельна одной из осей координат, все углы 90 градусов и площадь строго больше 0.
    → Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Должны образовывать точно. Второй пример - это как раз случай, когда прямоугольник есть, но отрезок, образующий одну сторону, продолжается за пределы прямоугольника.
    → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Контест очень хороший, спасибо авторам. Особенно понравилась задача Е, с первого взгляда начинает думаться в сторону дп по маске, только затем приходит правильная идея. Жалко я в прошлый раз не вылетел в див 2 (не хватило 3 очков рейтинга), сейчас бы уже был желтеньким.
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо! мне понравилось как я во второй задаче додумался увеличивать отрезки, на массиве=)
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Эээ. А зачем, если не секрет? Уменьшать - это ещё можно понять. А вот увеличивать...
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Посчитаем для каждой целочисленной точки сколько отрезков ее покрывают. делается это простым циклом. Дальше находим ближайшую точку на которой все отрезки.
      → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      дан массив изначально все в 0ях. потом считываем отрезки, и увеличиваем на 1 в массиве этот интервал и так же с остальными отрезками -- это для того чтоб потом найти место где все отрезки пересекаются что-ли.

      ps хотя я щас код других участников посмотрел, оказывается гораздо проще сделать по другому, ну я рад что хоть так додумался=)
      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Спасибо за комментарии, мне идея такого решения как-то в голову и не пришла даже :) 
        → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Nice round. Indeed problems were nicely connected in a way, and were of moderate difficulty for Div II.

A suggestion; It will be really awesome if you guys could provide the test data, used by the system, once the competition is over and problems are put up for practice. It will greatly help those of use who just aren't able to find why our solution is failing on a certain test. :)

Thanks
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
For those participating out-of-competition there was no quick submit form during the contest. Was that intended? Also, submissions I made during the contest don't appear on the corresponding page (http://codeforces.net/contest/14/my)
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

we need a weekly contest like this one.
I know it is very hard, but please try.

→ Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I don't know if this is the correct place to ask it : somebody know where is the search toolbar?

→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hi am new here, i am not seeing any practice option now, and there is no forum also. how this contest runs, do i have to upload the file or it is like codejam? wot should be the class, method names?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Open any contest, there will be a 'register for practice' button there. After that you'll be able to submit your code for any problem. And if you click on a link that looks like this:  x517 you can view other contestants' solutions.


    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can anybody tell me what is the main problem in problem 14A - Letter, i very bad in English, thank you.

→ Ответить