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

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

Всем привет!

2-го декабря (в пятницу) в 19:00 (московское время) будет проведен неофициальный нерейтинговый контест Codeforces Testing Round #3. Во время него мы проверим на практике, что последние нововведения Codeforces не влияют на ход соревнований, а если это не так, то быстренько все исправим :) Так что этот раунд будет проходить as is, никаких гарантий на ход его проведения я не даю.

Задачи на раунде кому-то могут оказаться известными, но я постараюсь сделать так, чтобы это было верно не для всех. Будет 3-4 довольно простых задач. Продолжительность соревнования — 1 час.

Говорю заранее спасибо всем тем, кто придет и протестирует систему. Спасибо!

Все изменения в системе будут сугубо внутренние, видимых нововведений почти не будет.

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

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

Thank you for your hard work to prepare such a contest ,I will take it .

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I hope I can solve all problems in an hour:)
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Thx for testing round... I hope it will be beneficial who will join to contest.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Thanks a lot for your hard work .. 
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
А почему в тегах написано java?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    Codeforces пишется на java, видимо в этом соль.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Когда я недавно редактировал пост про футболки, тег java добавлялся сам по себе, так что думаю, что это баг
      • 13 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится
        Codeforces пишется студентами, видимо в этом соль.
        • 13 лет назад, # ^ |
            Проголосовать: нравится -13 Проголосовать: не нравится
          Лолшто?
          Михаил Мирзаянов уже давно закончил вроде бы, а основная работа ведется им.

          Присутствие в команде разработчиков студентов != все делается студентами.

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Толсто, толсто.
            • 13 лет назад, # ^ |
                Проголосовать: нравится +4 Проголосовать: не нравится
              Что значит толсто?
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                • 13 лет назад, # ^ |
                    Проголосовать: нравится -13 Проголосовать: не нравится
                  C чего Вы взяли, что я троллю?
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится +18 Проголосовать: не нравится
                    Тебе самому не надоело? Какую тему за последнее время ни открой — в каждой есть ветка обсуждений, выходящая за край экрана, содержащая твои комменты. Причём их полезность бесконечно сомнительна. Ты тролля 90 левела качаешь что ли?
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится -19 Проголосовать: не нравится
                      Я до сих пор не понимаю, почему любое мое высказывание считается троллингом. Я до комментария выше вообще не знал, что такое троллинг.
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится +13 Проголосовать: не нравится
                        ==========================
                        Пруф, что ссылка на данную статью была дана тебе минимум 4 недели назад. И ты её видел, так как в той ветке есть более поздние твои комментарии.
                        • 13 лет назад, # ^ |
                            Проголосовать: нравится -13 Проголосовать: не нравится
                          Ссылки там не было. Один сказал, что троллить - это одно, другой  - что другое. И вообще. мало ли что в интернете пишут. Кому верить-то?
                          • 13 лет назад, # ^ |
                              Проголосовать: нравится +9 Проголосовать: не нравится
                            ================
                            Там была ссылка. Ту дискуссию я видела не только в нынешнем виде, но и по ходу развития. Так что прекращай хотя бы так явно врать, противореча очевидному для всех пользователей. Больше сюда писать не буду, продолжай убеждать себя в своей нетролльности, если хочешь.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I will be here, thanks for your contest.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
А он только для Div2?
13 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Сейчас все участники с рейтингом  >  = 1700 отмечаются, как участники "Вне конкурса". Вроде, контест нерейтинговый. Так и должно быть, или это ошибка?

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

    А какая разница, вне конкурса или нет. Всё равно раунд не рейтинговый !

  • 13 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится
    Так и должно, тестируем, в частности, участие вне конкурса.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

А задумано ли то, что "пробное оповещение" пришло в качестве мессаджбокса всем, даже тем кто не регистрировался на соревнование?

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это и раньше так было. Если во время соревнования находишься на сайте — получаешь все оповещения наравне с участниками контеста.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Даже если было раньше, вопрос всё равно встал :)
      Просто сейчас появляются какие-то невидимые изменения, так может и это по ходу поправят ;)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Странно, я участвовал и мне оно не пришло
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

В окне с условием рядом с кнопкой "Выберите файл" пишет "Файл н...ыбран". Chrome, Windows 7

А если отсылать во вкладке, то все пишется нормально.

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
А разбор будет? xD охота узнать как третью решать, и на чем так много взломов сделали...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Взломы по первой - отсутствие проверки ((s - a[i]) % (n - 1) == 0)
    Взломы по второй - на числах фибоначчи
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      я поймал троих, кто не смог вместить 2*10^5 =)
      • 13 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
        Я во второй написал перебор на претесты и ради развлечения (никогда не занимался взломами) пробовал валить всех подряд тестом 1000000. Двое внезапно даже упали.
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          :D на такой шляпе только что одного взломал :D

          уже не одного, а четырех, спасибо, поднялся в таблице турнирной на 70 мест почти xD

    • 13 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится
      как-то нечестно давать такую информацию во время контеста...
      • 13 лет назад, # ^ |
          Проголосовать: нравится -13 Проголосовать: не нравится
        1) контест нерейтинговый
        2) те, кто ломает, те уже знают это
        3) виноват, извините
      • 13 лет назад, # ^ |
          Проголосовать: нравится -12 Проголосовать: не нравится
        Надо учитывать, что контест нерейтинговый, так что большее количество взломов -> лучшее тестирование системы
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Если масштаб в браузере увеличен, то окошко взломов видно лишь частично (кнопка "Взломать" находится за краем экрана) и при прокрутке все равно остается на месте, а не ведет себя так, как, например, окошко с кодом участника.
Google Chrome 14, Ubuntu 10.10
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Как решать B?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я решал BFS'ом.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И C, сразу если можно.
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Ответом является количество шагов алгоритма Эвклида для какого-то числа, взаимно простого с n.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А не именно это решение взламывали числами Фибоначчи?
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Не знаю, сейчас увидим, правильно ли это.

        UPD: правильно же.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а как это доказать?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Допустим, что мы получили какую-то пару. Тогда все действия, взятые наоборот, по определению повторяют алгоритм Эвклида.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А за какую сложность это работает? 
          • 13 лет назад, # ^ |
            Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

            Легко заметить, что нет смысла рассматривать такие числа, которые больше n. Тогда для каждого числа меньше n просто находим это количество с помощью алгоритма Эвклида (быстрого). Значит, сложность — .

            • 13 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится
              На самом деле, можне не все n чисел расматривать, а только половину.
            • 13 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится
              А если воспользоваться алгоритмом Евклида с вычитанием (gcd(a,b) = gcd(b-a,a))? Непонятно сколько это работает, хотя, очевидно что быстро.
              • 13 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

                За O(max(a,b)) работает, так что вроде квадрат миллиона получается в общем.

                upd: ложь.

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

                  Квадрат миллиона - что-то как-то многовато:)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  разве? за O(log(max(a,b)))
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Ну балин за сколько будет найден гцд 1000000 и 1, если использовать лишь вычитания?
              • 13 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Это решение сдалось.

                Да, там не квадрат, а O(n*log(n)).

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

    я писал так:

    n -четное? если да, то на вывод n-1 иначе на вывод n-2

    ах, да чуть не забыл, если n=1 частный случай, то на вывод 0

    как ни странно, но претесты пройдены! но все равно сломали потом меня :-(

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У кого хакали А проверьте тест 5 7 6 6 6 6. Тут ответ 0.
13 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

It was really funny contest with "hard" pretests :) 

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Жду - не дождусь, когда у меня упадут обе задачи.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня первая уже упала. Жаль, взломщики не выловили всех моих багов :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А у меня первая все-таки прошла. Вторая не пройдет - свалится на тесте n == 11
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    ОптимИстично:)

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В первой я по недосмотру сравнивал число со средним арифметическим ВСЕЙ последовательности, что оказалось тоже верно. Насчет второй - смотрите комментарий про n == 11.
      • 13 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Ну и я сравнивал число со средним арифметическим. Что этом может быть неправильно?

    • 13 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      ОптимИстично
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
please, can anyone describe the idea behind problem B?
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    you should always increase minimum from (a,b) by maximum (a,b); if (a>b) b+=a;else a+=b;

    and if (a >=n || b>=n) then print number of steps.that was my solution.

  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Notice, that you won't have (m, m + k) in the optimal way, where k is a positive integer, because (m, k) would have less moves. So you will have (m; n), n <= m. Backtrack all n.
    When you need to calculate moves for position (m; n), you can get only (n; m - n) from it. For fast calculations use an algorithm similar to gcd :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Thanks for the explanation. Why BFS doesn't work here?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        well, I guess that it takes too much memory. If you take (n; m) as a state, I think that you have O(n^2) memory and time complexities. n can be a million.
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
19:50 и позже - вываливалась 503 Service Temporarily Unavailable, в виду чего терял время при попытке сдать решение.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I am confused about problem C. For sample 3, initially the fifth person has all the 5 cards with all 5 colors while other four people have nothing? But the statement said each people should have only one  color in the beginning, so it seems like a conflict for me. 

I must miss/misunderstand some important info, would anyone give me a hint? Thanks.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, так быстро протестировалось, это новое улучшение?
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите, пожалуйста, как посмотреть на каком тесте взломали мое решение? я чего-то найти не могу..
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
We cannot see the details of hacks now? This useful feature is available before.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Уважаемые админы пожалуйста увеличивайте размер ввод теста для взлома
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Чето взломы по-прежнему недоступны.
13 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
Контест понравился гораздо больше, чем CFBR 95. Спасибо огромное!
13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Есть и заметные нововведения: ссылка "Комментарии" в профиле, которая меня очень порадовала. Спасибо администрации! =)
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Писать контест одной рукой (причем левой) начиная со второй задачи было весело :)
13 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится
Задача B такая же как на TCO 2010 Round 1 - 500 :). Помнится эта была чуть ли не первая 500-ка Div-1, которую я решил на Топкодере :)
Задача C эквивалентна такой : построить граф с заданными степенями вершин, причем между каждой парой вершин - максимум 1 ребро. Была на каком-то KBTU Open.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    То есть в С его можно было строить жадно или не так все просто?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да жадно. Загоняем вершины (карты) в set. Достаем вершину с наибольшей степенью. Пусть она равна v. Если размер сета меньше v, то сразу ответ No. Далее достаем еще v вершин с наибольшими степенями. Проводим ребра, уменьшаем степени. Вершины, у которых степень еще больше нуля - загоняем обратно в set. Такие действия выполняем, пока set не опустеет.
      Сложность около O (s * logN)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Как реализовать понятно, я просто почему-то не был уверен, что жадник здесь зайдет. Спасибо.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Обе задачи с очень древнего саратовского четвертьфинала ACM-ICPC (примерно 2000 год).
13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Обалдеть у меня 2 слетело. 1 раз такое