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

Доброго времени суток)

Совсем скоро стартует Раунд 1 Всероссийского Открытого Чемпионата по программированию "КРОК-2013". Из в Раунда 1 в следующий Раунд 2 проходят участники, набравшие не меньше баллов, чем участник на 400-ом месте (при условии положительного числа набранных баллов).

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

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

Задачи для вас подготовила команда авторов в составе: Павел Холкин (HolkinPV), Геральд Агапов (Gerald) и Михаил Мирзаянов (MikeMirzayanov). Отмечу, что команда в этом же составе провела для вас квалификационный раунд и отвечала на вопросы в течении всего соревнования. Традиционно благодарим Марию Белову (Delinur), которая перевела для вас условия задач.

UPD1: Задачи будут расположены в порядке возрастания предполагаемой сложности. Распределение баллов было решено сделать немного нестандартным: 1000, 1000, 1500, 2000, 2500.

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

Всем участникам желаем удачи и успешного прохождения в следующий раунд соревнования.

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

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

Уважаемые организаторы чемпионатов. Думаю с данным вопросом к Вам обращались неоднократно. В нашей стране 10 часовых поясов, и логично что не всем удобно московское время. У меня к примеру, во Владивостоке, все турниры начинаются в 2-30. На начало можно попасть, а дальше даже 2-ух часовой контест очень сложно выдержать. Возможно ли как нибудь перенести начало соревнований на более удобное для всех время?

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

    Вы назовите удобно для всех время. Его вроде бы просто не существует.

    Вообще на мой взгляд выбрать понедельник под контест не очень удачно для студенческого(в основном) чемпионата.

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

Будет ли раунд рейтинговым?

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

А что с внеконкурсным участием? Будет раунд рейтинговым див1/див2/просто возможность принять участие?

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

Seems like really tough competition.. Did you mean under 400 amongst all Red,orange and purple coders ?

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

Will the round be rated?

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

    "UPD2: due to the large number of participants, it is decided that it will not be able to participate out the competition. For official contest participants the round will be rated."

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

      So what does a official contest participant mean?

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

        it's rated for both Divisions.

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

          I guess it means all eligible registered participants.

          When a Div2 contestant participates in a Div1 contest, he is considered unofficial, because although he registered for the contest, he is non-eligible to participate in a Div1 contest, and vice versa.

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

          In my view, all the participant who read the problem will be rated, as normal CF contests.

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

            You need to submit something to be rated, be it normal CF round or competition one

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

How would the rating be calculated for both division 1 & division 2 participants ?

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

how many rounds will this series of contests have,is there any T-shirts to give the winners ?

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

The problems will be more suited for div1, div2 or half way? :)

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

How to register when registration is private? It seems too private for somebody to enter :)

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

    I have the same problem. I have to register now because I will not have internet acces until the start of the competition

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

DELETED

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

I receive an Email tell me that I need to register on Codeforces for Round 1, but it seems that I cannot register because the registration is private. Did I really need to register or it will be done automatically?

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

"Registration is private", does it mean that all participants who passed qualification round will get registered automatically?

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

    Well, when I click "register now", a message box "The contest does not allow self registration" pops up. So I suppose that the registration will be automatically done.

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

      I hope

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

      I hope so because our dorm cut the wired internet access at 23:00(UTC+8), 30min before the round start, every workdays and it will be very crowded at the public WIFI, which cause it crash frequently.

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

How am i supposed to register for the contest???

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

"For official contest participants the round will be rated" ... for only the contestants the round is rated ??? am I misunderstanding ???

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

    it is decided that it will not be able to participate out the competition.

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

      if there is no participant out of the competition then all the participants are official so now whats the need of the "For official contest participants the round will be rated" statement ? they can simply say "this round is rated"

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

      haha you quoted that sentence as if it were in correct English :D

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

If there is problems with the registration I suggest to open the registration durig the contest. Because not all of us can register. I am going to miss school for the competition. I will be home at the 4-5 min from the start. I will mis the competition if i don't register now.

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

Registration is fixed now.

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

Сколько будет задач с тегами "кот тапок количество"?

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

Edit

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

    Why some of you cares so much about the ratings calculations and the score distribution? Every round about ten such messages appear.

    What will change if your rating changes will depend on only Div-2 or both Div-1 and Div-2 coders? Won't you participate in one of these cases?

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

Ну сделайте внеконкурсное участие.

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

    Лень было А на квале написать? :)

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

      Типо 18 нет. Думал будет хоть нерейтинговое внеконкурсное участие.

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

      Ты имеешь ввиду В не более, чем с одним багом?

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

        А где вообще можно было набажить там?

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

          Использовать gets() и не учитывать символ 13 в конце в конце строки, который появляется из-за виндового перевода строки, что я и сделал >:[

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

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

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

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

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

      Сделайте пожалуйста Уайлд-кард раунд в выходные для тех, кто не смог по участвовать.

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

"Всем участникам желаем удачи и успешного прохождения в следующий раунд соревнования" Жаль, что все не пройдут :( Все равно Всем УДАЧИ!!!

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

А почему перенесли начало? заранее спасибо!

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

    Единственная причина — чтобы все зарегаться точно успели.

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

      Серьезно или шутка? А то так можно бесконечно переносить, пока все не зарегаются :)

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

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

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

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

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

        Я поискал все HTTP-запросы с вашего хэндла и не нашел запрос от браузера на регистрацию.

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

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

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

put off 5 minutes?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  1. Что делать когда у меня при попытке взлома вывело "неизвестный вердикт Generator crashed"?
  2. Почему у меня когда я отправляю ручной тест, он мне говорит невозможно обработать взлом отправьте позже?
»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Lots of hacks specially Problem 4.

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

Контест окончен... И главная интрига — должен ли проходить квадрат в D?)

Если да — на чем ломают? Если нет — что там можно написать быстро и правильно?

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

    На джаве нет. На плюсах через раз.

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

    Сломали квадратный DSU

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

      Что значит квадратный dsu? Расскажите подробнее, пожалуйста. Может и у меня упадет

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

    Нужно оставить 2н ребер.

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

    ИМХО, конечно, но авторы очень неправы — ставить такие ограничения. Вместо нормальной задачи получилось непонятно что, которое вместо +100 даёт -50 нормальным участникам, челенджащим людей с лажей на С++.

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

      Если в итоге эта лажа не пройдет систесты — значит, надо было старательнее челленджить.

      Если пройдет — тогда мой вопрос адресован так же и авторам задач. Как было задумано? Это должно было проходить?

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

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

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

    Я писал корневую эвристику для запросов, но думаю на плюсах квадрат зайдёт, если без всяких логарифмов — видел у себя в комнате такое, но оставалось секунд 30.

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

    Я подумал-подумал, решил, что не должен, и все же написал . Был потом очень разочарован, увидев, что все квадраты посылали.

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

      Квадарты упадут скорее всего. Ну или рандомная половина квадратов упадет. Там есть нормальное за nk.

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

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

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

    Смотри, давай посмотрим, что мы будем делать, когда будем проходить [0,l): мы какие-то рёбра будем добавлять в дсу, а какие-то ничего делать не будут. Давай такие рёбра сразу выкинем: пройдем от 0 до m-1, если рёбро объединило две компоненты -- хорошее, оставляем, иначе выкидываем. Аналогично от m-1 до 0. При запросе будем итерироваться только по хорошим рёбрам, их максимум 2*N.

    Итого O(n+m+k*n), исходник: http://codeforces.net/contest/292/submission/3544049

    Обидно, что заходила всякая фигня, потому что очень клёвая задача же :)

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

    По идее, тут можно разбить список ребер на k кусочков и для каждого a и b предпросчитать dsu, в котором уже есть первые ak ребер и последние bk ребер. И потом на каждом запросе выбирать нужный dsu, копировать и за O(n/k) достраивать до нужного состояния.

    Немного похимичить с выбором k и должно пройти (идеально k = , но боюсь памяти не хватит).

    Это я придумал за 10 минут до конца после того, как у меня взломали квадрат. Написать не успел.

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

      А если сначала посчитать дсу на префиксе и на суффиксе. Для каждого запроса нужно слить только два дсу и дать ответ. Похоже на правду?

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

        Да, похоже.

        Но я догадался как это быстро делать только сейчас... =_=

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

    У меня в запуске работает 1375 мс. Должно зайти. Тоже не понимаю, зачем такие ограничения поставили.

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

      Сходил за попкорном в ожидании системных тестов...

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

        Попкорн кончился(

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

          Ну все, наверное, расходимся, Burunduk1 получил TLE.

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

            На дорешивании вгоню) У меня в D совсем не оптимально написано. Просто во время контеста была мысль "2*10^8, 2 секунды, все кэшируется... да конечно зайдет!". Забавно, я даже не сомневался в этом.

            UPD: O(km) зашло за 1734 мс.

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

              А как же мысль "это же D, авторы должны были позаботиться о том, чтобы тупняк не заходил"? :)

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

                Е должна отметать такое предположение)

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

                  Ну так в E ведь O(nm) не заходит, надеюсь? Или я что-то пропустил? :)

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

                  Ну, я тоже надеюсь. Просто если Е простая, то почему бы D должна быть сложнее

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

                  Ну в E надо было сделать по крайней мере одно логическое умозаключение, чтобы её решить; и оно могло быть сложным по мнению авторов, всякое бывает. Это не повышает вероятности того, что D — "переведите что написано с английского на C++".

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

                  Я попросил Gerald-а ответить, но как я понимаю не предполагалось, что решения за такую асимптотику могут проходить. Это авторский фейл, но в самом деле — почти все не проходят. Т.е. в этой задаче предполагалось решение поумнее и проблема не в неправильной оценки, а в неудачных ограничениях.

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

                :) мысль "да конечно зайдет!" была последней. После этого мозг отключился, а руки кодили.

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

                  А у меня в комнате нашёлся добрый человек, который захачил моё квадратичное решение. Пришлось писать что-то разумное. Спасибо тебе, KADR =)

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

    Ого, а у меня внезапно зашло O(m ^ 2 + k * n) за 1 секунду на Java.

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

    Инлайн в ДСУ творит чудеса, не верьте e-maxx, разница очень даже заметная: рекурсивный дсу: 3548782, тоже самое с волшебным словом inline 3549312 и нерекурсивный 3548909

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

      Кстати, по поводу DSU. Полезно помнить, что есть 2 разных решения. Первое -- стандартное, а второе -- со списками. Работает решение со списками за O(m + nlogn), где m -- число запросов, n -- число вершин. В нашем случае это 104 + 500*10 с маленькой константой, что должно быть быстрее. Решение со списками: храним color[v] и list[color], когда нужно сделать join, перекрашиваем меньший список и добавляем его к бОльшему.

      P.S. Я немного упростил твою реализацию: 3551436.

      UPD: Решение со списками работает 0.265 3551644

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

        265 это, конечно, круто. Учитывая, что находим ответы для всех подотрезков.

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

Could anyone tell me what's wrong with this generating code for problem E? I kept hacking and got "invalid input". Making the right input specification is so tough :(

int main() {
  int n = 1e5,Q = 1e5;
  printf("%d %d\n", n, Q);
  for (int i = 0; i < n; i++) {
    printf("%d", 100);
    if (i == n - 1) printf("\n"); else printf(" ");
  }
  for (int i = 0; i < n; i++) {
    printf("%d", 100);
    if (i == n - 1) printf("\n"); else printf(" ");
  }
  for (int i = 0; i < Q; i++) printf("%d %d %d\n", 1, 1, n);
}
»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Слишком поздно обратил внимание на задачу C, посмотрел что больше сдают D и думал над ней. Вопрос по задаче C. Зайдёт ли такое решение: обозначим числа в адресе следующим образом: a.b.c.d Переберём всевозможные варианты a и b, следя за тем чтобы не было ведущих нулей, потом аккуратно отразим => получим c и d. Запомним ответ куда-нибудь, например в set, затем возьмём каждый ip из предварительного ответа и первернём его так, чтобы получился валидный ip и положим в тот же set.

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

    Допустим n=3, числа 0,1,2:

    0.1.21.0 получится таким образом?

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

    0.1.222.210 такое, как я понимаю, не сгенрится.

    Но можно перебрать a,b,c

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

    Не должно — как ваше решение будет обрабатывать варианты типа "1.2.233.221", например?

    Правильнее честно перебирать первую половину цифр (длина до 6), затем отражать (2 варианта — одиночная цифра в центре и парная), и потом отдельным перебором пробовать бить это на 4 числа.

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

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

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

        У меня все претесты прошли за 15 мс, так что, видимо, реализация подвела. P.S. Возможно, забыли про хак "если n > 6, то ответ — 0".

        UPD: Все тесты тоже прошли за 15 мс

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

    Нет. Зная только a и b нельзя «аккуратно отразив, получить c и d». Например, в адресе: 8.9.121.98

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

    Не совсем так. c и d могут содержать много цифр, a и b — мало, тогда нам не хватит перебора a и b. Например 1.3.2.231.

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

Авторам большое Φ за ограничения в задаче D. Либо уж ставьте так чтобы квадрат явно не заходил, либо чтобы явно заходил. А то куча челенджей работающих за 1.9+ это какой-то бред.

P.S. спасибо мише.

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

Just one second to click submit button for problem E. :|

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

Ну D, это вообще подстава. Зачем так дразнить ограничениями, на которых обычно заходит квадрат?

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

    Каким образом квадрат все-таки не заходит? Вроде как 2 * 108 легко должно заходить, тем более массив размера 500 помещается в кэш, а по массиву ребер бегаем последовательно.

    Может объяснить какой-нибудь мастер оптимизаций, в чем тут дело?

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

      Может дело в том, что каждая операция с дсу — вызов функции?

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

What is the solution for D? Or is it just a DFS per query?

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

    I use disjoint set, with total complexity O(K * (N + UnionSet cost)).

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

      How do you achieve that complexity? Don't you need to traverse the edges that are not taken? I mean, isn't it O(K * (N + M))?

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

        oh yes, sorry I miss calculation :). N that I wrote first, I mean is M, total edge not total vertex.

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

        Given M = 10000, K = 20000, will 2*10^8 survive?

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

        You can make it faster by pre-computing spanning forests for all edge prefixes [0..i] and all edge suffixes [i..N]. Then you only need to merge two disjoint-set forests for each query.

        That brings the total cost down to roughly O(N * (M + K)).

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

    DFS per query:

    void dfs(int v){
          used[v]=true;
          for (int j=0;j<g[v].size();j++)
              if (!used[g[v][j].v] && (g[v][j].ind<l || g[v][j].ind>r))
                 dfs(g[v][j].v);
     };
    
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      It fails on half of hacks. Probably systest will fail most of them.

      I solved in such way. Let's have to sets of edges. First is edges, which connect vertexes, which is not connected by edges with less numbers. Second is edges, which connect vertexes, which is not connected by edges with greater numbers. There sizes is O(n) and other edges is not need. So we can answer query in O(n) time.

      It's easy to implement this solution with dsu.

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

        thanks for your response,I am interested why this solution get TLE,I only changed positions and get ac:

        TLE41:

        if (!used[g[v][j].v] && (g[v][j].ind<l || g[v][j].ind>r))
        

        ACCEPTED:

        if ((g[v][j].ind<l || g[v][j].ind>r) && !used[g[v][j].v])
        

        why system test is so strictly what is difference ? :(

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

          Consider "if ( A && B ) {}" code. If A is false, then B isn't checked. B is checked only when A is true. So if we know that A is false more often than B is false, it's better to write "if ( A && B) {}", otherwise "if ( B && A ). In our case (g[v][j].ind<l || g[v][j].ind>r) statement is false more often than !used[g[v][j].v] is. Therefore, if ((g[v][j].ind<l || g[v][j].ind>r) && !used[g[v][j].v]) is the best way.

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

CROC's English is very very difficult and long... I took hard to read even using translation machine.

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

Very nice problem D. I knew my solution in wrong, but I've locked my code and hacked 7 people!!

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

В E вместо легкой и быстрой корнячки жуткое решение с сетом, которое дебагать полчаса. В D вместо честного решения (или даже не совсем честного квадрата) какая-то хрень с DSU, которая почти наверняка не зайдет по времени. В C вместо трех циклов и одной проверки — перебор с отсечениями (тоже повезет, если зайдет).

День офигительных решений просто.

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

    В E ж дерево отрезков с покраской на отрезке просто, зачем там корневая?

    А в С перебор должен заходить. С моими отсечениями на тесте 1 2 3 4 5 6 работает 0.2. Казалось бы, это самый сложный тест.

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

      А как же 0 1 2 3 4 5?

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

      Дерево отрезков — тоже вариант, не требующий применения мозга для написания.

      Ну, хорошо, если зайдет. Но почему бы не подумать, перед тем, как начать писать. >_<

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

      Вот и я судорожно перечитывал задачу E, но так и не смог понять, почему же она E! Зато задачу C сделали всего-то на 500 баллов дороже, чем дебильную задачу B, которая вообще больше тянет на задачу A второго дивизиона.

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

      Ну а особенно порадовали слабые претесты в задаче E. Получилась такая забавная игра — "у кого больше дебилов в комнате, тот и победил". У меня вот в комнате зеленые не стали дерзить и посылать ТЛьное решение. Зато многие мои друзья поналомали туеву хучу таких ТЛьных решений.

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

        Может не стоит называть участников, которые посылали квадрат "дебилами"? Это не очень корректно и не к лицу участнику считающему себя не "дебилом". Если себя так вести, то после каждого раунда Petr должен всех называть дебилами (в том числе и тебя).

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

          Вы наверное квадрат послали? :)

          P.S. Я квадрат послал :(

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

            Немного не в тему — но выше речь идет о задаче Е. В которой претесты, как я понял, можно было спокойно пройти с решением за О(N*M).

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

              Упс, я думал D...

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

              Если верить yeputons то иногда еще и вломы макстестом тоже. Если делать memcpy(). Правда у меня взлом на этом успешный.

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

        По поводу сложностей задач — а в чем проблема-то, религия не позволяет решать задачи в порядке, отличном от А-В-С-D-Е?

        Если серо-зеленые сдают с плюса за 20 минут, то и желтым, вероятно, это под силу.

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

      Впилюсь-ка я в ветку первого дива.

      дерево отрезков с покраской на отрезке просто

      Объясните, пожалуйста, как это туда лепится =_=

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

        Для каждого запроса i, красим отрезок l[i], r[i], В цвет i, а потом при запросе значения элемента мы сможем за O (logN) найти последний запрос, на котором этот элемент копировали из А, и за O (1) просто вывести.

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

        Для кадог запроса вида "копировать" покрасим в ДО отрезок, [y, y+k) в цвет — номер запроса, и щапомни delta = y -x;

        На запрос отвечать так: Смотрим последнее перекрашивание. сдвигаемся на delta Если не было перекрасок — понятно

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

        Заметим, что числа меняются только в массиве B. Каждое число в массиве B на момент запроса второго типа может быть либо исходным, либо "покрашенным" каким-то запросом. Нас интересует последний такой запрос.

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

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

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

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

Приношу извинения, если вопрос уже неактуален (давно не участвовал) — а системное тестирование скоро будет? Ждать или с работы домой ехать уже? :)

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

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

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

    А как их ломать-то? Чем отличается случайный тест, в котором на каждом запросе удаляется 1 ребро от любого другого теста?

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

      Начнем с базового вопроса — что будет работать дольше:

      дфс с одной вершины, который веером обходит весь граф

      дфс с одной вершины, который цепочкой обходит весь граф

      серия дфс, каждый из которых обходит только 1 вершину

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

      Например, какой-нибудь тест против СНМ с только одной из двух эвристик.

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

        Мы тут на досуге с ifsmirnov пытались делать тесты, на которых СНМ с одной эвристикой работает дольше, чем СНМ с двумя. Получалось плохо. Есть какие-нибудь известные способы?

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

          Получалось плохо, потому что ничего принципиально лучше рандома мы в итоге так и не сделали, разве нет? ;)

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

            Ну, там был рандом с претензией на интеллект вроде бы. =)

            Ну и вообще, интересно, что люди посоветуют.

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

            Вот тут Burunduk1 утверждает, что на его тесте есть аимптотическая разница

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

              Извините за оффтоп, но Ваша превьюшка напоминает фото Гены Букина :) Или это мне одному так кажется?)

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

          Я помню была какая-то конструкция от Burunduk1 против только сжатия путей. В два-три раза дольше видимо будет на ней.

          Собственно вот. Только я не помню что тут происходит. http://pastebin.com/hzeSxBXt

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

          Выложил задачку об этом. Там есть условие, решение, чекер. Решение генерит тест, на котором "СНМ только со сжатием путей" делаем операций на m запросах.

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

    А кстати, добавляются ли тесты от участников со взломов? Если да, в этом нет необходимости вроде, и так на'challeng'или...

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

      Добавляются, но не все, а вручную по выбору.

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

What's the solution to C and E? Thanks.

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

    for C the most important thing you should consider is that you can obtain the hole string by determining the length of each of 4 number O(3^4) and the material of the first half of the string O(n^(half of the length <=6)) and then you should check whether it is legal or no for more info see my C++ code : 355108 for E you should use segment tree data structure (read about it here )segmnet tree and keep for each node of the tree that what is the last copy that contains this node and then easily find the answer for each query if you need more info see my C++ code : 3550844 I hope it will be useful for you.

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

Too strange, why I can't see the system testing? Are they really testing now?

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

посоны, расходимся, систестов сегодня не будет

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

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

Why testing won't start?

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

please tell me when i can submit my solution for problem 5??? and where i can do that???
my brain is exploding, because i submitted my code 5 seconds before the end, and because of the stress i had, i made a little mistake and 10 seconds after i noticed that!! if i submitted that my score was about 1400 and i would advance to the Round 2.
my brain is exploding now! help please :(

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

    well my story is more tragic. Cause of Iran’s f*** network I wasn’t able to submit my E code in 1:10 when I have already submitted A,B,D. My network re-concocted after the contest. what should I have to do ???

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

    excuse me! i mean 4500(not 1400)! it's because of my brain!

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

Hey guys, Is there any one to start system test? Mike? Gerald? Pavel?

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

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

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

    Скоро все будет, чуток терпения!

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

      спасибо

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

      Спасибо за информацию! А можно поинтересоваться, почему не используется системное тестирование во время контеста? Есть ли какие-то ограничения, не позволяющие это делать, чтобы после соревнования за минут 5 дотестировать остаток, и просто сделать доступными имеющиеся у администрации результаты?

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

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

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

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

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

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

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

          А почему не очень? Это же не перекрывающиеся задачи.

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

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

            Ну да, в принципе, тоже не вижу особых причин.

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

          Ну, всё равно, это гораздо меньше работы после контеста. Большой вопрос в том, достаточно ли ресурсов, чтобы о чём-то подобном даже начинать думать.

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

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

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

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

          Конечно, это всё работает только тогда, когда детализация заданий на тестирование больше, чем просто «протестируй посылку №1234».

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

One hour of pending system test should be something unusual. In that case, we contestants all expect some announcements/explanations from admins :(

Edit: ok, just saw Mike's comment :)

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

Meanwhile in CodeForces HQ:

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

Plus this comment to see how many people are waiting for the system test. :D

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

Ого, системное началось!

Спасибо за оперативность!

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

I'm staying up for the system test! Please get this done ASAP, I want to sleep!!

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

Чуваки, отбой тривоги, в D тупизна заходит!

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

    а у меня O(m2) не зашло :(

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

      Ну, тут ожидается лотерея, по-моему. Кому-то повезёт, кому-то нет. Ограничения надо было другие, чтобы O(K*N) качественно отличать от O(K*M).

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

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

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

          Ждём ответа от авторов, их уже в комментах раз 5 спросили. Есть гипотеза, что это была такая разновидность троллинга :)

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

            Что тут сказать?

            Мы тщательно старались подгонять ограничения под асимптотику. У нас были наивные решения, которые давали TL на наших тестах. Все (кроме одного, совсем не оптимально написанного) правильные решения проходили с 3х кратным запасом. Отсюда мы сделали вывод, что ограничения отличные.

            Здесь надо сказать, что вообще polygon показывает warning, что TL решение укладывается в 2х TL. Я не заметил, что это происходит на всех TL-тестах. В этом моя большая ошибка.

            Я искренне прошу прощения за эту недоработку, будем стараться не попадать в такие ситуации впредь.

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

              А, ну тогда ОК, я уж боялся, что оно было осознанно.

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

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

              Какова сложность авторского решения? Я решал за (N + M) * sqrt(M). Несмотря на то что так и напрашивался бфс, я предпочел написать нормальное решение.

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

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

              В любом случае, надеемся, придуманные нами задачи вам понравились

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

          В авторском решении из разбора, которое они хотели, чтобы проходило — O(nm) памяти. Видимо, поэтому.

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

        Есть ещё решение за O(N*M+N*K).

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

    Тупизна тупизне рознь)

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

      Заходит)

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

        Да, у тебя читерская функция

        int getParent(int x)
        {
                if(parent[x] != parent[parent[x]])
                        parent[x] = getParent(parent[x]);
                return parent[x];
        }
        

        залазит на одну глубину меньше, чем копипаста с емакса. Вот в чем фишка!

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

          И это еще не все, такой код получает TL 58, решающая оптимизация — в порядке ветвей if-a:

          if (r[x] == r[y]) {
          	p[y] = x;
          	r[x]++;
          } else if (r[x] < r[y]) {
          	p[x] = y;
          } else {
          	p[y] = x;
          }
          
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        А у меня в комнате посыпались все M*K, в том числе у двух красных. Так что действительно рознь.

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

      Вот, O(m*k) зашло. Куда уж тупее..

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

Well,I have to thanks all Codeforces team. They taught me what does error 502,504 and server busy means :D . I was kidding but I really expect codeforces to be more faster in this contest :D.

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

no wonder tourist completed the contest in just 35 minutes.

3000+ on the cards.

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

haha, in my B i had "unknown toplogy" instead of "unknown topology" in one minor case, WA on 38 :-))

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

А заблокированная и взломанная задача будет проходить полное тестирование ?

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

    Нет, она же взломана, значит решение неправильное.

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

in problem D: Why was K limit so low?? some people got AC with O(mk), but some people didn't.

the problems were are implementation and coding and non-algorithmic. and very slow system testing I did not like this contest

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

    More than 1200 contestants, it isn't slow system testing!

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

      it is really slow. just remember last 3 contests, this contest had less contestants than them.

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

      yes it is! most div 2 contests more than 2000 people participate and it takes less than 30 min and i'm not just talking about system testing, it took about an hour for the system testing to start

      i think this round should be unrated for these reasons:

      1. the contest was uneven : i see a lot of RED contestants which their ranks is more than 300.

      2. the problem difficulty's were close to a div-2 contest

      3. Problem D is very unfair and they could have set limit of k to 10^5 so people know that the MK soloution would not get AC

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

        I don't see how it's unfair. All had same chances

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

          Because there are participants who got Ac on O(mk) soloution And if the k limit was higher, people would think on another soloution

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

            If the k limit was higher, then many coders would have discarded the O(mk) solution.

            But it isn't. The problem statement clearly said k <= 10^4, so, if a coder doesn't realize that the O(mk) solution will work, it's his fault. I don't see how it can be unfair. The constraints were very clear.

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

        agree with your reasons, specially with third one.

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

        Anyway it's too late! The ratings have been updated

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

    I have the same problem, One of my friend's code got acc although his code had to be very slower than mine.

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

    I got back to division 2 and didn't make to the next round because of this So I am completely in agreement with you.

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

Что значит вердикт "ошибка тестирования" в задаче B? 3542656

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

А можно будет после тестирования посмотреть решения участников?

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

ikar выбрал правильный ник)

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

Эх, буду надеяться, что среди первых 485 участников случайно окажутся 86 читеров.

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

Ну что, где мои шикарные женщины?

Если вдруг кто забыл...

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

This is translation of my russian answer.

We carefully try to make constraints more fair. Our naive solution get TL on our tests. All (except one, that isn't written optimally) our correct solutions passed with 3times reserve. So we decide that our constraints is very good.

Here I should say that polygon shows that all TL solutions fits into 2TL. Buy I didn't notice that thing. That's my great fault.

I truly apologize for this fault. We will try not to make such faults.

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

Would it be possible to hold the CROC rounds on Sunday instead of Monday? For US competitors who work or are students it's difficult to compete in a round that takes place at 11:30 AM EST on a weekday. I was able to participate in round 1 (and qualify for the next round), but I don't think I will be able to participate in the 2nd round.

I don't think this will conflict with the TopCoder Open, or make competing more difficult for participants in Asia or Europe, so maybe it's possible?

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

    People may already have plans based on published schedule. Also Codechef Cookoff is scheduled for Sunday

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

My solution to problem D was bfs for each query having a total time complexity of O(Q * (E + N)), why didn't it pass the time limit? M = 10000 N = 500 Q = 20000 Total number of calculations would be around 2*10^8, I have accepted many problems here in codeforces with the same number of calculations? I had the idea of using DSU but it was a little bit harder to implement and to prove, For further contests how can I be sure if the solution will pass or not whit this number of calculations?

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

    I do the same too :(

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

    When you're that near the limit, there's no guarantee it will work in time. It's just your decision if you want to take the risk and go the easy way, or spend some time thinking a faster solution.

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

      You can always use "Custom test" to approximate the running time in worst case. I first submitted a naive solution. Then I used this and figured out it was too slow and resubmitted it later. (Tips: there's a limit for input size in "Custom test", however we only need to measure the running time, so simply assign some random numbers directly in the code itself)

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

Прошли квалификацию — 2018 человек. Зарегистрировались на Раунд 1 — 1558. Сделали хотя бы один сабмит — 1376. Т.е. реальных участников 68% от прошедших. Рассматриваете ли вы уменьшение проходного бала в Раунд 2, к примеру, до 500 человек? :)

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

In question D: Can somebody tell me why this submission using dfs worked. 3545286 and mine using bfs is giving TLE. 3551854 Thanks in advance..:) KrK

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

    R_R_ You hacked in during contest. Comments please.

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

    The constant factor in your solution seems to be a little higher. You're using two arrays (color and marks), when you only need one (one that states whether the node has been assigned a component). Try using only the color array and see if you get it AC.

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

задача D 292D - Компоненты связности

TLE #41 3551866

ACCEPTED 3551867

я всего лишь написал это :

if ((c[now][o]>r || c[now][o]<l) && !fix[g[now][o]])

вместо этого :

if (!fix[g[now][o]] && (c[now][o]>r || c[now][o]<l))

и решение прошло :(

из за этого , во время контеста мне взломали это решение :( .

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

    Вот уж какая разница? Ну неверный это способ. Согласен, некоторым повезло. Но если в следующий раз ограничения будут подобраны удачнее, то все подобные решения не зайдут. Чего плакаться теперь? Прочитайте лучше разбор и научитесь делать эту задачу правильно. Это «идея». Чем больше вы будете знать «идей», тем лучше будете писать контесты. А причитания, подобные вашим, результата не принесут никакого.

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

      Если решение задачи проходит за 1.3 секунды из отведенных двух — здесь и не пахнет везением... Да, тем, у кого 1.984 или 2.000 — немного "повезло". А тем, у кого на 1-2 тика времени больше — немного "не повезло". Но они знали, на что идут. И то, что они не написали тот же квадрат более оптимально — их проблема, при желании он пишется так, чтоб заходить без проблем. А я считаю, что все, что заходит с вероятностью 1-eps — в случае АСМ является "правильным". Будь то хэш, рэндомизация, или же вот такие "неверные способы".

      Более того, если на любом будущем соревновании у меня будет выбор между сдачей "неверного способа" и обдумыванием "правильного" решения, то я выберу первое и абсолютно не буду напрягать себя обдумыванием того, хорошо я поступаю или нет.

      Например, если у меня есть граф на 1000 вершин, и надо найти кратчайшие пути от одной из вершин до всех остальных, то я буду писать Флойда. И мне абсолютно плевать, что у него куб, мне плевать, что правильные парни пишут Дейкстру или еще что-то в этом роде. Я пишу решение, которое проходит в пределах ТЛ/МЛ, и при этом требует минимума усилий на написание и содержит минимум мест, опасных в плане возможных багов.

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

        Я согласен, что я неверно расставил акценты в своем сообщении и плохо выразил свою мысль. Что я подразумевал, так это не то, что не надо пытаться сдавать задачу «не лучшим способом», а то, что не надо ныть после того, как это задача не сдалась

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

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

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

можно как-то посмотреть весь 8-ой тест нзадачи E?

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

    Можно написать генерацию случайных данных, брутфорсное решение, и гонять до первого "!=" :)

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

    У меня падало на 8 тесте из-за того, что я в дереве отрезков при обновлении отрезка, когда заходил в вершину, скидывал текущее значение на потомков, не проверяя, что оно не null и обнулял текущее значение.

    Вот посылка с багом: 3545669.

    Вот посылка без бага: 3546795.

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

292D - Connected Components

can anyone tall me why is [ if(!fix[v[i][j].fi] && (v[i][j].se<x || v[i][j].se>y)) ] this wrong and this [ if((v[i][j].se<x || v[i][j].se>y) && !fix[v[i][j].fi]) ] true?????

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

such a long questions . it was hard to translating specially for persons that their english are not too good .

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

    I made a mistake . It is the participants' duty that have a good English .You can give the questions somehow you want . at last thanks for the contest .

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

Прошу простить за глупый вопрос, с результатами всё в порядке. Спасибо за хороший контест :-)

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

Round 2 will be rated for people who did not get in the first 400 in round 1 ? Thanks.

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

я в кроке 1 раунде занял 386 то бишь прошел.Но при попытке регнуться на крок раунд два мне пишут что рейтинг мой ниже 1700 и посему зарегаться мне нельзя.Как мне быть? P S темы про крок р2 нету решил спросить тут.

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

    Это потому что контест создан с дефолтными див-1 настройками. Думаю, админы увидят твое сообщение и поменяют.

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

    Зарегистрировал вручную. Удачного раунда!

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

      А почему вручную-то?

      Тех, кто в показывается в Top 400 по Раунду 1, но сейчас в Div2, как минимум шесть: ultizet, Jace_Beleren, avoit, Wahahalyq, volfram, htkek. Из них сейчас зарегистрирован только Jace_Beleren (что логично). На этот момент остальные должны тоже написать сообщение, чтобы им удалось зарегистрироваться?

      И это я посмотрел только тех, кто был в Div2 на момент раунда. А ведь можно было ещё туда свалиться.

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

        Пройти в Раунд 2, и тем не менее, свалиться в div 2? Маловероятно. Вышеупомянутый, например, получил аж +200 к рейтингу, при этом оказавшись почти на границе прохода.

        Хотя это не отменяет твоего вопроса, конечно.

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

          Можно было занять примерно 400-е место в КРОК Раунде 1 и затем одно из последних мест в Codeforces Round 180. Этого могло хватить.

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

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

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

      Похоже, что проблема ещё не устранена.