Блог пользователя e-maxx

Автор e-maxx, 14 лет назад, По-русски

Приглашаем всех на очередной раунд Codeforces Format!


На этом раунде я буду заменять Артема Рахова в его ставшей уже привычной роли администратора контеста. Дело в том, что Артём отправился участвовать в онсайте соревнования TopCoder Open (Algorithm). Удачи, Артём! :)


Я со своей стороны постараюсь провести раунд без заминок.


Раунд окончен, результаты.

Выиграл участник с ником a4461497, а среди участников первого дивизиона - kuniavski.


Все тесты к задачам:

C, D, E


Готовить раунд помогали Михаил Мирзаянов и Юлия Сатушина.

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Жалко что div2 only. Наверное сегодня будут алгоритмические задачки :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Будет и возможность взламывать в комнате для участников вне конкурса или это пока еще не реализовано?

Кстати не совсем в тему, но хочу написать о мелкой баге(заметил давно, но как-то лень было писать). При регистрации все конкурса вместо надписи "Зарегистрирован" остается "Зарегистрироваться", что несколько путает.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Это уже с момента как появилась возможность решать вне конкурса. Походу люди привыкли... Можно себя успокоить тем, что в списке ник все же висит.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно ли участвовать участникам 1-го дива без регистрации?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как же задалбывает, что за 13 минут до начала нельзя регаться... =(
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    абсолютно согласен.причем такое случается не в первый раз.
14 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится
Good luck to Artem!
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Actually,I like acm/icpc rules more...
14 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Лучше бы все соревнования проходили в одно и то же время, например в 7 вечера. А ещё лучше в определённые дни, например в пятницу или субботу.
Так будет удобнее - всегда знаешь когда и во сколько, а сейчас очень легко запутаться во времени и датах - уже два контеста пропустил.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    И ещё предложение, если человек уже опоздал, то почему бы ему не разрешить сдавать задачи, считая это дорешиванием?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
    Ну проводить в одно время - вряд ли хорошо - не забывайте, что все живут в разных часовых поясах, поэтому разное время раундов - шанс написать для людей из далеких от нас поясов.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Варьируя время проведения конкурса на пару часов вперед-назад не очень-то поможет людям из далеких поясов. Было бы неплохо зафиксировать несколько времен, например, в 14.00, в 18.00 и 1.00. Иначе люди забывают и пропускают.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Если я из первого дива, я могу взламывать решения?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ну косяк в задаче C был очень неприятным. Я бы тут орал и брызгал слюной, если бы я был в конкурсе. Когда я увидел то, что было изначально написано на месте Ri + 1 < Li + 1. То подумал, что речь идет о том, что "1,2" -> "1,2", а не "1,2" -> "1-2". Оказалось, что не так. Не знаю, есть ли еще такие же "умные" как я. Но если такие есть среди тех, кто в конкурсе, то отбирать у них эту задачу неправильно. Кривое условие располагало к тому, что эту задачу можно решить и так.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Интересно, как работает в таких случаях начисление очков за взломы.

    Типовая ситуация, была бага в условии, я написал решение соответствующее баге в условии, то есть выводившее "1,2", а не "1-2". Мое решение взломали, подозреваю, что именно на этом. Позже увидел пояснение по условию, исправил, прошел претесты, а потом и финальные тесты.

    Вопрос в том, засчитают ли взломавшему взлом, засчитают ли мне лишнюю штрафную посылку, как это будет зависеть от того, насколько мое время посылки отличается от времени пояснения по условию (в отличие от различных онсайт соревнований, где пояснения произносятся непосредственно голосом, и других систем тестирования, здесь у меня было такое ощущение, что, чтобы увидеть пояснение, нужно посмотреть на страницу со списком задач, если это так, то это очень неудобно и вообще говоря, легко можно не заметить).

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Prob. A,B,C,D are easier than the previous Round 2 contest problem set. However E seems very interesting. Thanks.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    Yeah, I finished the set in 45 minutes this time, while I still haven't figured out the last problem from the previous set!

    Problem E in this contest was almost identical to the easy problem in TopCoder SRM 458 (the problem here has a more complicated collision formula, but that doesn't really change the problem, as the exact formula is given in the problem statement anyway). edit: actually, it looks like this problem was a little different after all. Still, it looked very familiar at the time. Maybe my mind was playing tricks.

    On the whole, I thought the previous set was a lot more inspired.  But I hope this was just an outlier and that future rounds will be more interesting again.

    To RAD.: best of luck in Las Vegas!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за контест!
Не могли бы дать претест 4 на E?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вот это да! Решал Е до последнего момента, остаётся 40 секунд, не могу найти баг. Вдруг вижу — лишний i++. Удаляю, не тестируя посылаю — "Претесты пройдены"! :D кайф
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
BR: В начале контеста меня автоматически перебросило в комнату 1 (а должно было в 100). И еще если по задаче были неудачные попытки (взломанные или не прошедшие претесты), то во время тестирования она отображается как "Не пройдено"
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
I think it's easy . Why don't it have dynamic programing ?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
hi. could you tell my what's  Artem Rakhov's username at Topcoder?
14 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится
Контест был слишком простым. Я даже поизвращался и сдал задачу E бипоиском + хэшами. Казалось бы что за чушь, но и такое возможно... Мне кажется, что на задачу Е тесты слабоваты. Задача С - неприятный момент. Непонятно, почему неправильная трактовка условия по вине авторов все равно прошла претесты. Аж бесит, что смотрюсь как недоумок с 900 баллами на ней :)
Все равно авторам спасибо. Сегодня второй дивизион порешал побольше и побыстрее. Надеюсь, что все они получили удовольствие и азарт.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Контест не расчитан на участников с рейтингом 1500+

    Думаю, что всем участникам с рейтингом до 1500 было интересно. Пятую задачу сдали не более 10 участников из див2 (те, что не новенькие). Вы считаете правильная сложность - чтобы таких было 0?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Смотря на положение, их больше 20... Я считаю чтобы их  должно быть 5-10... А задачу D решили ~150 из 400. Тоже много по моему...
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится
      Да кто ее только не решил. Даже если угробить на первые четыре задачи 50 минут. То остается 70 минут на то, чтобы сдать Е. Там уже фантазию не остановить. Судя по тому, что там заходило, только грубая ошибка могла помочь не сдать эту задачу. Там с десяток различных решений, которые были приняты.
      Коли уж Михаил обратил внимание на этот комментарий, хотелось бы спросить его мнения.
      Если я не ошибаюсь, 12 тест в задаче С это как раз тест вида "1,2". Люди сдавали задачу читая одно условие, а получали WA согласно другому. Некоторые успели переотправить, некоторых повалили, и часть из них угадала с причиной такого провала. Да, те, кто вне конкурса могут пережить. Но почему люди из див2, которые участвовали в конкурсе получают незаслуженно низкие места. Неужели не будет перепроверки на втором наборе тестов?
      Чтобы пояснить, почему люди выводили 2 последовательных числа через запятую, скажу следующее. Изначально было написано что-то вроде Li + 1 < Li+1 (или Ri+1). Вот как это еще понять, если не вывод двух последовательных чисел через запятую? И, кстати, как участник вне конкурса, я не нашел где можно задать вопрос (у меня не было такой возможности или это просто не сразу можно найти?).
      А по поводу задачи Е... Ну пусть она отделяет победителей от хорошо выступивших. А тут она выделила топ30, если не больше.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А я почему-то сразу понял, что это опечатка. Я заметил опечатку в первой задаче, и понял, что опечатки - это нормально и надо думать, какой смысл автор хотел вложить в задачу. Хотя подобное - это все-равно неправильно.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
спасибо хороший был раунд) *правильно решил 4 задачи, жаль не успел отправить 4-ую не хватило секунд 15 =) 
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Нужно отметить, что тестирование сегодня летало и сервер почти не вис, лишь в начале тестирования чуть-чуть.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can You please tell me what is stack size  here?
Or where is the rule page about this at all?
My recursive program in D gets Runtime error in test 19.And very same iterative program get accepted.I guess It is due to stack overflow.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anybody explain the solution to Problem D ?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Once the graph is a tree, you can construct it just by the information of the parents of the nodes, and then do a bfs from r2 to get the parents when that is the root.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за тесты!
Кстати, моё Е на соревновании свалилось на 16-ом тесте (как показывает система), однако ответ на 16-ый тест на моём компьютере совпадает с правильным. Проблема в тестировании или я не тот тест смотрю?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    надо прибавить кол-во претестов.
    т.е. если в претестах 6 тестов, то тебе нужен 22 тест.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Нет, в архиве все окончательные тесты начинаются с 1, да и первые тесты совпадают со всеми претестами. Ну и даже если бы так было, 22 тест тоже правильно обрабатывается.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What are test 12, test 22 and test 26 of problem C?
14 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
I also want to know what are test14 of problemC.Anyone can help?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1000,1000,1000,1000,1000,998,998,1000,1000,1000,1000,999,999,1000,1000,1000,999,1000,997,999,997,1000,999,998,1000,999,1000,1000,1000,999,1000,999,999,1000,1000,999,1000,999,1000,1000,998,1000,1000,1000,998,998,1000,1000,999,1000,1000,1000,1000,1000,1000,1000,998,1000,1000,1000,999,1000,1000,999,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,998,1000,1000,1000,998,1000,1000,998,1000,999,1000,1000,1000,1000
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe your array is too small,and that's my problem
    Actually  ,you can download the tests in the part for round #34 in home page

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think #34 is easier than #32 or #31.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anyone tell me the idea for the problem E?

Thanks.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I just read the problem, and I think we can just simulate it. We keep finding the time at which the next collision occurs ( minimum of next collision time of all pairs ) and update the positions of all the balls after that. I guess this should be fine with the given constraints. Are there going to be so many collisions that this might lead to TLE ? If not, can some one give a rough proof. Thanks.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Насколько я понял, в задаче D предполагается, что карта дорог - дерево общего вида, для которого нужно сделать простейший поворот?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну я бы сказал - требуется это дерево подвесить за другую вершину. Что такое "поворот" в теории графов, я не знаю
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
можно узнать 3 тест задачи D?
почему-то на нём по времени не проходит.