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

Совсем скоро стартует Квалификационный раунд Всероссийского Открытого Чемпионата по программированию "КРОК-2013". Раунд будет идти двое суток, мы надеемся каждый сможет найти удобное себе время для участия. Этап начнется 13 апреля в 00:00. Общий список зарегистрированных на Чемпионат доступен по ссылке.

Чтобы пройти в Раунд 1 вам надо принять участие в квалификации. Из квалификационного раунда в Раунд 1 проходят все участники, набравшие не меньше баллов, чем участник на 2000-ом месте (при условии положительного числа набранных баллов). В раунде вас ждут несколько задач, примерно расположенных по возрастанию сложности. Во время квалификации задачи тестируются системой только на претестах, а системное тестирование состоится после окончания квалификации (т.е. всех 48-и часов мероприятия). Претесты не покрывают все возможные случаи входных данных, так что тщательно тестируйте свои программы! Взломов, падения стоимости задач во время квалификации нет.

Раунд продлится 48 часов, но это не значит, что мы призываем вас все это время провести за решением задач. Мы надеемся, что большинство участников справятся с задачами (или с большинством задач) за более короткий срок. Такая длительность раунда выбрана для того, чтобы каждый нашел удобное время для участия.

До окончания раунда категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них. Запрещено общаться на тему задач, обсуждать условия и проч. Будьте честными и пусть в Раунд 1 пройдут достойные. Как только квалификация будет завершена, можно будет обсуждать задачи и решения.

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

P.S. В этом раунде допускаются к участию только зарегистрированные участники Чемпионата. Зарегистрироваться для участия в Чемпионате можно здесь. Особо расторопные участники успели зарегистрироваться до внедрения такой проверки, поэтому некоторые регистрации придется аннулировать. Кажется, это не принесет вам сложности — так как впереди еще двое суток.

UPD: Тестирование завершено. По предварительным данным все участники с не менее чем 950 баллами проходят в Раунд 1. Граница может быть немного изменена из-за удаления читеров.

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

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

Внеконкурсное участие не предполагается?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Прочитай PS

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

      Ну вроде бы для CF совсем не проблема удержать на несколько десятков пользователей больше... Тем более что по первой ссылке:

      Мы постараемся максимально допустить внеконкурсных участников, тех кто не может участвовать в Чемпионате официально.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -6 Проголосовать: не нравится

        на несколько десятков пользователей больше

        Правильнее было бы: "в 2-3 раза больше". Одна из проблем: раунд квалификационный -> будет много халявных задач -> будет много посылок по этим халявным задачам -> серьезно затянутся систесты. Вероятно, MikeMirzayanov руководствовался и другими аргументами.

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

          Можно сделать систест для официальных участников, а только затем для всех остальных. Также, тестируются только окончательные посылки, а их будет не так уж и много.

          Правильнее было бы: "в 2-3 раза больше"

          Интересно, какой средний возраст пользователя CF? Я думал, что здесь абсолютное большинство студентов >18.

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

I don't know Russian and the registration form is Russian , how can I fill this form while don't understanding it ?

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

What's ВУЗ mean in registration,should I write in with school name?school code?or any other thing?

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

Good luck! I can't participate because of my age. I wish you have fun.

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

Как узнать, не аннулирована ли регистрация? (Я зарегистрировался ещё 20 марта.)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Не-не, с регистрациями на чемпионат ничего не делали. Речь о регистрациях на раунд. Первые несколько часов туда могли зарегистрироваться все, кто хотел, независимо от регистрации на чемпионат. Вот список зарегистрированных на чемпионат — http://codeforces.me/userlist/croc2013 , а вот список на раунд — http://codeforces.me/contestRegistrants/291

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

what a pity!!!I want to participate this game,but I don't know Russion...

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

Does "duration=2:00:00" mean that the contest will last for 2 days?

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

I love long contest and ACM-ICPC rules.thank you :D

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

    Well, there aren't ACM-ICPC rules because final tests will be after 2 days.

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

В раунде вас ждут несколько задач, примерно расположенных по возрастанию сложности. Что это значит? =)

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

    Это значит, что, чем больше порядковый номер задачи, тем сложнее сама задача.)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Не знаю, чего здесь не ясно. Значит, в раунде будет >=1 задач, и сложность будет возрастать.

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

Since it lasts 24 hours, does that mean score is independent of when you submit? I notice that there's still score depreciation on the contest page.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Падение стоимости задач? Но говорили же "падения стоимости задач во время квалификации нет."

UPD. Всё починилось.

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

Регистрация требует: «Укажите код окончания ВУЗа». Я ВУЗ не заканчивал и не собираюсь. Что мне писать?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Если поле обязательное — укажи предполагаемый год окончания, если бы ты оканчивал вуз. Хотя на месте разработчиков формы, я бы не стал делать поле обязательным.

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

What file do I submit? Source file or exe file?

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

The score is independent of submission time, but you still get -50 for pretests failed / resubmissions.

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

Как можно зарегистрироваться в идущий раунд?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    Если Вам нет 18-ти — то никак, а иначе сначала надо зарегистрироватся здесь.

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

I have registered for the contest.. i am not able to submit solutions...

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

    There is registration for competition and reg for contest(elimination round). Maybe you mixed up them.

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

Уважаемые организаторы, юзабилити сайта, на мой взгляд, очень низкое: — переход "назад" происходит только с 5го раза (первые 4 раза браузер переходит на ту же страницу на которой находится сейчас) — очень глубоко запрятаны "нужные" ссылки, затруднительна навигация по сайту (пол часа искал где зарегистрироваться на раунд)

P.S. пишу не для того что бы ткнуть пальцем, а для того что бы система улучшалась и развивалась.

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

    если ты про кодефорс то у тебя смесь привычного тебе с общеиспользуемым здесь

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    Всё вроде бы совсем не так плохо. Переход назад — проблема видимо у вас, т.к. у меня всё работает.

    Про навигацию — бывают некоторые моменты. Например, лично мне не нравится, что от задачи из архива к раунду переходить приходится, правя URL в адресной строке. Непонятно, зачем нужна ссылка problemset/problem/ вместо contest/***/problem/

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Ссылка нужна — у них разное меню второго уровня и сайдбар. А вот сделать быстрый переход в контест, скажем, по клику в его название в контесте — мне нравится.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Благодарю. Как раз такие различия вообще то и раздражали. Ссылка в контест вполне неплохое решение.

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

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится
    • проблема с "назад" это 99% проблема с вашим браузером/интернетом/кривыми руками/чем-то еще
    • а ссылки найти как раз очень просто, достаточно сравнить с Facebook. мне лично минут 5 потребовалось, чтобы на главной(!) странице Facebook Hucker Cup`a найти ссылки на, например, результаты предыдущих раундов
    • а если вы не можете понять что для регистрации на "Крок" надо на главной странице справа увидеть немного "незаметное" "Обратите внимание. Соревнование идет. Чемпионат КРОК 2013. — Квалификационный раунд", то это тоже ваши проблемы
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I just came to the Codeforces site and found about this competition. I have registered on the Croc's site, but the contest is already running on Codeforces, so I am not able to register in the system and participate. Is there a workaround for this, or am I just too late?

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

Эм.. а задания где? Я понимаю что я не совсем все читаю, но про нахождение задания я ничерта не нашел. На мыло ничего не пришло даже в спаме. P.S. Я нашел задания, но не могу отправить пишет "вы не зарегистрированы" в списке я есть.

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

Хм.. Еще один вопрос: Я пишу на C# в Visual Studio, отправлять файл как для C# mono? Project.cs или качать mono и писать на нем?

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

    Можно писать в VS, но выберите при этом уровень .Net framework 3.5, т.к. эта версия Mono не поддерживает новые функции .Net

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

Где можно узнать более подробные характеристики компьютера на котором будет тестироваться присланная программа? Хотелось бы знать характеристики процессора.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    BTW, если вы хотите просто узнать за сколько работает ваш код на конкретном тесте, можете использовать вкладку "запуск" на странице контеста.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -21 Проголосовать: не нравится

      Спасибо! Есть 2 варианта решения, пока что в голове, реализовывать оба просто что бы проверить какой быстрее — не хочется делать лишнюю работу, информация о процессоре расставит все точки над Ы.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        А как информация о процессоре поможет определить какой алгоритм быстрее?

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

          Кэш, не?

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

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

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

              Блочное решето, например, очень сильно зависит.
              Правда, я не знаю способа предугадать влияние кэша :)

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится -10 Проголосовать: не нравится

                Кэш не причем.А вот одну и туже задачу можно решить на разных языках, с использованием разных компиляторов, естественно время выполнения разное будет.

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

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится -8 Проголосовать: не нравится

                  Вы ограничения на время выполнения видели в условиях задач?!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится +10 Проголосовать: не нравится

                  Вы слишком мудрите. Все эти задачи спокойно решаются стандартными средствами, стандартными методами, да ещё и наверняка с хорошим запасом по времени и памяти. Без многопоточности, без глубоких оптимизаций... Вон люди за час все 5 задач сдали.

                  Тут решает идея, алгоритм. Акцентируйте своё внимание на них)

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

                  Запрещено общаться на тему задач

                  Хорош уже

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Тестирование осуществляется на компьютерах Core 2 Duo E6750, 2.66 Ghz, 3Gb памяти.

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

      Спасибо. Ограничений на количество потоков в одном приложении, я так понимаю, не существует?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

        Смысла использование потоков все равно не имеет, т.к считается процессорное время и в случае многопоточности просто будет считаться каждый проц.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Ребят, что такое? В списках зарегистрированных я есть, но ни на одну задачу квалификационного раунда нельзя отослать решение. При нажатии на кнопку "отослать" пишет, что я должен быть зарегистрирован. При попытке повторной регистрации выдаёт, что я уже зарегистрирован. Так что делать? До конца всего сутки остались, а тут ещё и планы на выходные... Помогите =(

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    http://codeforces.me/contests

    здесь зарегистрируйся) как я понял, нужно региться одновременно и на контест, и по ссылке на КРОК.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      О, спасибо!) Как-то смутила большая красная кнопка "Войти", не заметил, что нужно 2 раза регистрироваться =)

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

А по какому принципу периодически перестраивается таблица? Место, конечно, не меняется, но очередность в таблице не постоянная. Понимаю, что вопрос идиотский, но мне интересно :-)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Полагаю, там порядок неопределен в случае одинакового числа баллов.

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

Quite a pity that there's no T-shirt as rewards. T-shirt is honor for programmers!

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

Вверху страницы ссылка на КРОК прошлого года

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

Скажите пожалуйста, а если задача прошла сейчас ПРЕтесты, это значит, что решение правильное? я просто первый раз тут участвую.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +49 Проголосовать: не нравится

    Я первый раз участвую, и поэтому ещё не научился читать?

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -50 Проголосовать: не нравится

      можно подумать ты как только зарегистрировался сразу сел изучать нормативно-правовую базу кодефорсес.

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +47 Проголосовать: не нравится

        Во-первых, не как только зарегистрировался, но перед первым контестом — да, разумеется, я нашёл и внимательно изучил правила.

        А во-вторых, процитированная фраза — из поста с объявлением о квалификационном раунде чемпионата КРОК-2013. Да-да, именно из того поста, который мы с Вами комментируем.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится -51 Проголосовать: не нравится

Ребят, ну вот зачем так делать? Почему у вас программа падает, если main возвращает отрицательное значение, но нигде этого не написано? 6 раз отправлял решение на простецкую первую задачу, 6 раз получал ошибку времени исполнения. Я привык писать так, что в случае какой-то ошибки main возвращает отрицательное значение (имеет тип int, почему бы и нет?). У вас почему-то это считается за ошибку. Столько раз перелопачивал решение, уже чуть ли не всю программу заново написал, кучу времени потратил, а оказалось, что просто достаточно было return -1 заменить на return 0. На правильной задаче из-за вас потерял 300 баллов. Ну почему так?! >.<

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -32 Проголосовать: не нравится

    Ну вообще и правда кстати не мешало бы поинформативней вердикты давать(в моём случае -200 т.к. показывался RE вместо ML, но это уже отдельная тема).

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Если давать код возврата, то можно заниматься реверс инжинирингом тестов на сервере. Это, конечно, и так можно делать, но сейчас количество информации более-менее ограничено числом вердиктов

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        Как выяснилось на первооапрельском контесте количество информации не ограничено количеством вердиктов. Умельцы ТЛли свои решения на определенное время и получали достаточно много информации.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    Потому, что если программа не вернула операционной системе 0 (а если мы хотим кроссплатформенности, то EXIT_SUCCESS), то она упала. И да, нет никакой возможности кроме анализа вывода определить, это она упала по какому-то исключению или просто решила вернуть не 0. Учите матчасть

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -27 Проголосовать: не нравится

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

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

        Пройдите по вкладке запуск и протестируйте своё решение. Станет вполне очевидно. Можете сразу попробовать запустить

        int main(){
        return -1;
        }
        
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится -16 Проголосовать: не нравится

          Теперь понятно уже, но опять-таки: почему я должен таким образом гадать, если на самом деле это не является ошибкой?

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +17 Проголосовать: не нравится

            Как это не является? Вы правда считаете, что возвращать ненулевой код при успешном выполнении — это нормально?

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

              Я считаю, что если это допускается стандартом, то система проверки должна действовать соответствующим образом.

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

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

                Вообще-то все системы проверки считают ненулевой код возврата за ошибку. Собственно, так и определяется Runtime Error.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится

                  Не все. Например, acm.timus.ru за ошибку считает только возникшее в процессе работы системное исключение (любое, в том числе внутри блока try-catch в Visual C++). А программа может завершиться с любым кодом возврата.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится
        • Я привык писать так, что в случае какой-то ошибки main возвращает отрицательное значение
        • У вас почему-то это считается за ошибку
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        В условии задачи странно писать, что надо выводить правильный ответ, что тесты удовлетворяют условиям задачи, что нельзя превышать ограничения времени и памяти, что код возврата должен быть 0, нельзя создавать файлы на сервере, нельзя запускать дочерние процессы, в Delphi 7 бажная функция SeekEoln... Это все by def верно для системы.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +15 Проголосовать: не нравится

          Спасибо, не знал про бажную SeekEoln

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +4 Проголосовать: не нравится

            Это верно только для Delphi 7. Если текущая позиция делится на 128, возвращаемое значение SeekEoln непредсказуемо и точно false при наличии перевода строки.

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

      Вообще-то возможность есть: WIFEXITED(), WIFSIGNALED(). Уверен, в Windows есть аналогичные средства.

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

Will round 1 affect rating ? Thanks.

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

ну и условия

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

У администрации есть предположение — сколько займёт системное тестирование? :-)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Оно, скорее всего, нисколько не займёт, так как все решения уже протестированы, но результаты скрыты до конца соревнования.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      надежда не оправдалась((

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Да, удивительно. Возможно, системное тестирование включается вручную: оно пока ещё "ожидается".

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Действительно не понятно что мешает на котесте на котором нет взломов тестировать сразу на всем наборе тестов, а участнику показывать результат по претестам, а потом уже приотркывать занавес.

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

            Подозреваю, что тестировать по ходу контеста можно и когда есть взломы :)

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

Ещё +1 день и даже у меня бы вышло зафиксить дурацкую ошибку в Е, из-за которой всё бездумно считалось по n-1 раз )

Спасибо за отличный контест! Никогда не удавалось добраться до последних 2 задач за предполагаемые 2 часа, а за 2 дня удалось :)

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

What's up with system testing?

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

Подскажите пожалуйста, что означает "Попытка игнорирована "

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

    значит, что ты делал перепосылку

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

      Нет, это у меня финальные попытки игнорированы.

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

        Аналогичная ситуация, но в списке "Мои посылки" — они все в очереди...

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +67 Проголосовать: не нравится

    Это значит, что вы читер. Притом крайне наглый, раз спрашиваете об этом здесь.

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

Вы случаем для тестирования ничей кластер "покататься не взяли"? :-)

Уж больно много параллельных тестирований :-)

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

спасибо за интересную задачу E.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Кто, кстати, как ее решал? Знаю несколько решений, лично я спускался вниз по дереву, храня следующую строку: шаблон#точтонабралврезультатеспуска. На этой строке высчитывал префикс-функцию, если результат равен длине шаблона — апдейчу ответ. Знаю несколько человек решивших с помощью суф.автомата. Чисто теоретически знаю решение на хешах.

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

      Я тоже префикс-функцией решал.

      А вот про суфиксный автомат на дереве, а не на строке, было б интересно поподробнее узнать)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Я делал тоже самое, только не хранил явную строку, а просто передавал в дфс (вершина, текущее состояние), потом по каждой букве исходящих строк делал переход за O (1), предподсчитав все автоматом по шаблону.

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

      Я по суф автомату строю префиксный автомат, а дальше очевидно

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

      Хм, а как вы обновляли префикс-функцию, если не секрет? Непонятно, как за разумное время без автомата такое делать. Если втупую (как в КМП) — то оно упадёт на тесте: "root->v1 со строкой aa..aa (99999 символов)", "v1->vi со строкой z", i = 2..100000, образец aa..aa (100000 символов). Тогда вы при каждом переходе в vi будете делать 99999 скачков по префикс-функции назад.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -11 Проголосовать: не нравится

        Если я правильно понял ваш тест(99999 строк по 99999 символов 'a') то он некорректен, т.к. в условии суммарная длина по всем строкам не превосходит 300000. Или Вы что-то другое имели ввиду?

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

          Там одна такая строка из корня, а из нее потом торчит много букв z по одной

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

          Нет, там 1 строка 99999 символов, ещё 99999 строк — все 'z'. Но каждая из них заставляет пропрыгать по всему массиву префикс-функций строки 'a....a'.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +2 Проголосовать: не нравится

            Вы правы, этого я не учел. Вопрос к организаторам, почему же мое решение зашло.

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

            Я вот зло негодую из-за того, что такого теста не было. И даже подозреваю, что у авторов решение было просто с КМП. Авторы, опровергните мое предположение.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится

              Нет, у нас строился автомат по префикс функции. Но теста такого не было, это правда. За что приносим свои извинения.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        Можно сохранять уже вычисленные значения префикс-функции в стеке. Вот мой код с аналогичным решением: http://pastebin.com/J4RQ6wUf

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

        Таких тестов, как ни странно, не было

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

        А если сохранить для каждой вершины результат этих прыжков для каждого символа?

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

          Такое тоже убивается, только сложнее. Надо строку из корня сделать чуть короче, а в торчащие дальше рёбра добавить leading 'a'.

          В общем, не стоит пытаться переизобрести построение автомата по префикс-функции :) Получится ровно оно, если вы будете пользоваться сохранёнными значениями в процессе прыжков в КМП, а не только во время dfs'а.

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

            Предпросчитать всё до дфса, конечно. Меня немного сбило, что все говорят об автоматах и борах, хотя в задаче из вершины могут быть разные переходы по одному символу.

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

        Можно подробнее, почему не будет работать? Я делал втупую через КМП, но ваш тест и тест из комментария ниже у меня будет обрабатываться за O(sum_len). И с ходу пример теста, когда будет много переходов назад по префикс-функции, приводящих к TL, придумать не получается.

        PS: Вот код

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      В процессе считывания из файла развернул сжатый бор в обычный.

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

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

      Вычислил префикс-функцию строки, тривиально превратил её в автомат, прошёлся ним по всем веткам дерева, передавая в dfs текущую вершину и состояние в автомате.

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

      Похоже, что валится хорошими тестами

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Решал хэшированием. Модуль хэш функции: 0x7FFFFFFF. Из-за простоты модуля можно получать точный хэш подстроки, а не выполнять сравнение умножением. Сравнение строк: если совпали хэши, то сравниваем хэши половинок строк, если совпали и они, то сравниваем хэши 1/3-ых... и так до 1/6 строки. Например, для строки длиной 120 сравниваем хэши следующих частей: 1..120, 1..60, 61..120, 1..40, ..., 1..20, 21..40, ..., 101..120. Почти нулевая вероятность, что удастся подобрать две разные строки: известно, что среди x = 2^16 строк и хэш-функцией в 2^32 различных значений вероятность хотя бы одной коллизии равна p = 0.5. Если эту оценку скомбинировать с необходимостью совпадения хэшей подстрок, то соотношение x/p будет астрономически большим. 3526533

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        Из-за простоты модуля можно получать точный хэш подстроки

        может я не понял о чём ты но, для справки: это можно сделать при любом модуле.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится -18 Проголосовать: не нравится

          Имелось ввиду получение хэша любой подстроки, зная хэши ее префиксов. Пусть множитель многочлена P, а модуль хэша M. Пусть нужен хэш от s.substr(i, len), нам известны h[i] и h[i + len], тогда хэш hs = (h[i + len] — h[i]) / P^i. Нужно делить на P^i, т.е. умножить на обратный элемент к p^i по модулю M. При составном M необходимого обратного элемента может не оказаться.

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

            Такой способ портит ассимптотику. Умножением сравнивать быстрее

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

              Портит где именно? Все прямые и обратные степени можно заранее посчитать.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Пусть степени с сумме хеша всегда идут по возрастанию, и нам известны хеши суффиксов нашей строки, тогда hash(l,r) = h[l]-h[r+1]*p[r-l+1], где p[i] = P^i (предпосчитано). И ничего делить не надо.

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

              Вы предложили те же яйца, только в профиль. Но проблема при составном модуле хэша от этого не исчезает: (x * p) % M при различных x = (0..M-1) может попасть в одну точку. Я утверждал, что при составном модуле вероятность коллизии больше, чем при простом.

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

                а я думал, что Вы утверждали, что для получения хеша подстроки нужен простой модуль.

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

Why it is not possible to open other's solutions?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

что за беспредел?) отправил в дорешивание код, по которому был таймлимит — проканало (задача В) http://codeforces.me/contest/291/submission/3539066 — полное решение http://codeforces.me/contest/291/submission/3527235 — тл

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    Компиляторы разные. Ничего удивительного, что время работы отличается.

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

      точно, не увидел. Кстати MS быстрее оказался как ни странно

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

Can anyone briefly describe how to solve problem E efficiently? I tried to construct a suffix array for all strings but get TLE for large tests. Thanks.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

    You can use simple string matching algorithm such as KMP. At every node, we store a number k where t[0..k] is the maximum prefix of t that match with the suffix of the string we obtain on the path from root. So k of each node can be quickly computed based on k of its parent in O(no. letters on the edge). In addition, hashing is another solution.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      I'm surprised that there is no test case in system test as below.

      6

      1 aaaaaaa

      2 ab

      2 ab

      2 ab

      2 ab

      aaaaaaaa

      Using kmp without optimization will result in O(n^2) running time in case like this. To overcome case like this, for every node we keep the longest string below the node and cut the computation below the node when the length of the prefix that ends at the node plus the length of the longest string below it is less than the length of the string we want to find.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +22 Проголосовать: не нравится

        It's easier to precompute state transitions for all (state, char) pairs. This solution works in O(kn), where k is the alphabet size.

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

        There really is no test case like this?

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

        Yes, that's correct. However I just need to modify 1 line in the KMP code to pass this kind of test. You can check my submission: 3539931. This is asymptotically good enough if you don't want do precalculate all the states like what rng_58 said.

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

    I solve it using segmentree and polynomial string hashing . suppose there is a string chain , sometimes we delete some characters ,and sometimes insert some characters,and another operation is qeury for a substring's hash value,we can do these operations by segmentree and hash. so this problem is like this,when we come to a node,we add a string to the end of the chain,when backtrack ,we delete the last characters ,and also judge whether the last "cnt" characters is the target string or not.the overall complexity is nlogn , n is the number of total characters my code is here

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

Помогите, пожалуйста, memory limit пофиксить: http://www.codeforces.ru/contest/291/submission/3523737

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

Hi,

I've solved E with hashing, just for fun, I don't think this solution 3540056 should be passed, or am I wrong? Last week read this very good article, so now I would like to understand how Hash working and this is the reason why I want to solve this problem with hashing:) So while I implementing I have the problem how should I choose the modulo, and the multiplicator (I don't know how it should call) which I denote with q. Could you suggest some rule how should these choose?

I read hashing on the wikipedia, but I couldn't find any article about hashing for competitive programming, could you recommend some other article?

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

When the solution come out?

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

How Can you find out who cheated?

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

    As far as I know, some automatic heuristics is used. Then all suspicious pairs are checked for the similarity by human.

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

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

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

В задаче С не было простого теста:

2 2

0.0.0.0

0.0.0.1

Первое мое решение давало ответ 255.255.255.255, но данная маска не является корректной по условию, т.к. в ней нет нулей.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Я еще уточнял у членов жюри, является ли маска 255.255.255.255 корректной по условию, ответили, что нет. я был уверен, что есть тест на этот случай