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

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

Всем привет!

Совсем скоро, 5 мая в 19:30 MSK состоится Codeforces Round #182, автором которого являюсь я. Это мой шестой раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald) и Диме Соболеву(sdya) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

По техническим причинам начало соревнования было сорвано. Приносим извинения, контест будет НЕРЕЙТИНГОВЫМ.

Разбор.

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

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

Долгожданный контест от Sereja. Надеюсь задачи будут как всегда интересными.

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

Очень ждал раунд КФ и обрадовался когда увидел, что дает его Сергей)

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

    Так сильно ждал, что аж не принял в нём участие...

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

Даешь регулярные Sereja-раунды каждый месяц на Codeforces!

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

Не могу не отметить "удачный" выбор дня для контеста.

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

    Чем же он неудачный?

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

      Если бы это решал я, то сделал бы завтра в 10-12 дня. В СНГ у всех выходной, и азиаты смогут писать. На Америку можно забить, оттуда участников очень мало. Ну и как уже отметили, немалая часть людей из того же СНГ может быть занята сегодня.

      Какие минусы у моего варианта?

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

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

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

求轻虐!!!!!!

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

А какая разбалловка?

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

Any info. about the score calculating rules? As usual?

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

I believe this will be a very level of the game!

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

all your round announcement posts look like the same :D

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

Can you tell me what about the score ? dynamic or 500-1500-1500-2000-2500 ?

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

Кто-нибудь знает какая будет разбалловка?

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

Good look to everyone! :)

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

hope my friends and i can reach blue= =

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

It is easter in the ortodoxal world. I hope a wonder happen and everything with the contest will be OK.

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

жаль что на 10 минут позже начнется (

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

а почему перенесли начало на 10 минут?

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

Мне кажется, пора вносить информацию о разбалловке при создании поста. Например, "динамическая". Или "будет объявлено в момент начала раунда". Или "мы объявим за минуту до начала". Или "придумаем на втором часу контеста". Полагаю, многих достали повторяющиеся комментарии, а некоторым участникам действительно интересно.

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

looks like the contest is delayed 10 minutes

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

hope today's sever will be stable

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

Удачи всем кто лайкнит меня.

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

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

    Думаю, стоит сделать раунд нерейтинговым. 2 минуты назад у меня в одной вкладке контест шел, а в другой шел отсчет (2 минуты) -> есть вероятность того, что кто-то успел прочитать условия за этот промежуток времени.

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

      Когда-то администрация(Gerald) говорила, что может смотреть логи и узнать, кто видел условия.

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

Yestody, GCJ, Have your score arrived 22.

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

Сервер воскрес!

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

Hope Codeforces can fixt it .. the server cant breathe right nw :O

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

WTF IS THAT?!

The contest opened while the server was down and some people managed to get the problem statements!

THIS IS COMPLETELY UNFAIR!!

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

    How you know that ?

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

      One of my friends already sent me the statement for problem A

      Problem A. Eugeny and Array

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

      , Problem A. Eugeny and Array Input le: stdin Output le: stdout Time limit: 2 seconds Memory limit: 256 megabytes Eugeny has array a = a1; a2; : : : ; an, consisting of n integers. Each integer ai equals to -1, or to 1. Also, he has m queries:

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

    What the....

    If this is true, the contest need to be cancelled definitely. Please announce about the situation and stop wasting competitor's time.

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

Will the contest be rated? At some moment, contest once started.

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

Поставь лайк если ты красный.

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

Are you sure, you want to continue this contest ?

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

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

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

Sereja strongly recommends you to read ALL the problems. I strongly recommend you to open ALL the problems :))

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

its getting late 35 min wasted time yet.

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

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

it's really unbearable !!!!!!!1

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

Why 502 Bad Gateway ???

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

Contest gonna start today???

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

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

UPD: выше уже написали, опоздал

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

    Ну вот зачем это было делать? Спойлерить таким образом условия — это просто идиотский поступок.

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

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

      Ну, можно считать, что с таким скриншотом все в более равных условиях...

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

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

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

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

          Какое решение можно принять, если такой участник ровно один? Сделать контест рейтинговым для всех, кроме него? Это нечестно по отношению к нему. К тому же он мог распространить условия по частным каналам, и опять же это не повод его банить.

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

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

        Да ты что? Этот скриншот наоборот заведомо делает ставит всех в неравные условия — далеко не все, ожидая, пока сервер взлетит, читают пост с анонсом. А вот если бы его не было, то у раунда ещё есть шансы на рейтинговость. Можно почитать логи, посмотреть, кто успел прочитать условие, оценить время доступности и из этого сделать выводы о рейтинговости.

        А этот скриншот никакого равноправия не добавляет — это одна проспойлеренная первая задача из Div2. Абсолютно бессмысленной поступок.

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

          Лол. Абсолютно бессмысленно ругать чувака, который не сделал ничего плохого. Разве он виноват в том, что ему досталось условие до начала контеста? Ни разу. Рейтинговым будет следующий контест, будьте спокойнее)

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

            Он мог не сливать его и не участвовать в контесте. Или участвовать, но потом его бы отсеяли по логам, как уже заметили выше.

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

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

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

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

          Может быть, в какой-то конкретной ситуации «посмотреть, кто успел прочитать условие» и сделать вывод — это и хороший метод, но в общем случае он ставит участников в ещё более неравные условия.

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

          К тому же, опять же, условия могли растечься по приватным каналам.

          Ещё аргументы за скриншот — выше.

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

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

            растечься по приватным каналам.

            А это было бы прямое нарушение правил ресурса, разве нет?

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

              Не уверен, скорее нет. Какого именно правила? Мне кажется, передать условие в неприкосновенном виде и без комментариев тем, у кого сервер недоступен — примерно то же самое, что поделиться доступом в интернет в месте, где с ним туго. Второе — явно не нарушение правил, я несколько раз в таком участвовал с обеих сторон.

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

              А как считает администрация?

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

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

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

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

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

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

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

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

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

              В этом подходе мне не нравится ловушка для участников, которая из «повезло» делает «не повезло». Вот я обновляю страницу, и мне доступны условия. Теперь, если я не заметил, что начало контеста перенесли, то автоматически не пишу контест в рейтинг. А если заметил — я могу что-то сделать, чтобы остаться рейтинговым участником? Закрыть вкладку, написать письмо администрации, предъявить скриншот?..

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

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

                Ну был ещё один, наверно технически сложный вариант — рассчитывать время сдачи для этих участников отдельно.

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

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

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

              Задача А див2 — обычно очень простая и служит для того, чтобы ранжировать людей внизу таблицы. Весь прикол в том, что для участников, быстро ее решающих, она практически ни на что не влияет, потому что он борется за места с 2-5 задачами, и чтобы он не решил А — это нонсенс. То есть: возьмем двух человек: для одного задача практически ни на что не влияет, второй итак решает ее порядка 40-120 минут. Контест вполне можно было сделать рейтинговым. Но этого не произошло. И в этом виноват явно не парень, выложивший условие задачи А. Естественно, беря во внимание, что контест среднестатистический, а оный сегодня как раз и был. Я имею в виду сложность, а не интересность.

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

      Я бы адресовала этот вопрос тем, кто проводит контест. В див. 1 тоже несколько сдач задачи A в 0:00.

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

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

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

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

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

If this round will be unrated, please tell us before the contest end.

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

"Oops! This link appears to be broken"

"502 Bad Gateway"

"504 Gateway Time-out"

"Sorry, the server is too busy at the moment. Please try again later."

For 15 minutes these were the only problems I could see!

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

Hope system can be fixed as soon as possible. It's hard to not get the request of "502 bad gateway"...

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

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

If this round will be unrated, please tell us before the contest end.

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

5 минут, 5 минут, а потом еще и еще нельзя, наверное, сегодня работать ...

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

**Server Problem !!!!** **Bad Gateway** Hope it'll be OK soon... :/

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

Already 00:05 ! (East Asia)

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

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

The server problems are getting really annoying!!! at least could someone explain why the server is down lately??

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

Похоже, действительно раунд лучше сделать нерейнтиговым. Люди, сдающие задачу на первой минуте это подозрительно.

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

LOL, they all had the problem statements and the code ready before the contest begins

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

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

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

    Этого никак не определить.

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

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

      да, осознал. ну, будем решать ради удовольствия :)

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

thank you for letting us know that the contest will be unrated.

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

waiting 35 minutes... and... unrated...

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

Sorry about the contest start. It was my fault: the main reason is — it was a non-production copy of Codeforces deployed before the contest (some experimental code + experimantal JVM settings + enabled profiler). Somehow the production copy was unable to start because of many requests :( It was started after some time, but it was passed about 0.5 hour and it was a moment of contests was started (so some users were read the problems).

The contest is unrated. I'm sorry about it. I hope you will like nice problems by Sereja.

===

Приношу свои извинения в связи со срывом старта контеста. Это по моей вине, основная причина — был запущен не-production вариант Codeforces (с некоторым экспериментальным кодом + с экспериментальными опциями в JVM + под профайлером). Почему-то production-сборка не смогла сразу запуститься под написком потока запросов :( Когда она была запущена (примерно через полчаса), был момент когда контест был доступен и некоторые из вас уже прочли задачи.

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

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

Problem C, Do the n elements for which we can change the sign needs to be consecutive ?

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

Something is definitely wrong with new Python 3 interpreter. Sorry for spoiling before the end of the contest, but anyway it's unrated.

So I feel I'm clever enough to make a solution for problem A, but it has TL on test 11. I do some stupid things sometimes so I checked here: http://codeforces.net/contest/302/status and everyone fails on test #11 (no one solved it using python 3). The problem could be in reading input data, but it's not as big (10**5).

Also after direct translating my code to python 2 it was accepted, so I think something has to be repaired here.

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

    It is true (at least for me) that CPython 3 is sometimes slower than CPython 2.

    I wonder if Codeforces could implement support for PyPy?

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

      Python 3 can be slower, but if it fails on this example what will be on examples with bigger inputs? I waited py3 really for a long a time, but in my opinion it's better to disable it in this state.

      It would be good if admins add PyPy but the problem is that it's implemented, again, only for python 2

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

    I tried Div2 A and B with Go language but both solutions got TLE in pretests. (my solutions: 3675888, 3676731) I feel more optimization is needed for those new languages.

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

      It's strange that solution both in python 3 and Go fail exactly on test #11. I hardly believe they are equally slow.

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

      I tried to run it localy. The result is "time consumed: 2.81 sec". Note, my laptop is much faster than judging machines. It seems IO in Go is a bottleneck.

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

        I also ran it locally and it took 8.1 seconds... looks like the judge was correct and I should use faster IO functions if any. Thank you for pointing it out.

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

    Right, Python 3 is slower than Python 2 in many cases. For example, on my laptop (i7, much faster than judging machines) you solutions work (on the test 11):

    • Python 2: 0.65s,
    • Python 3: 2s,

    Also PyPy works not faster than Python 2:

    • PyPy: 1s.

    "... so I think something has to be repaired here ..."

    I believe Python team should "repair" Python 3 to work faster. On the other hand you should know and understand pros and cons of the language.

    Another conclusion that PyPy is not a silver bullet, this problem shows again that it doesn't work faster than CPython 2.

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

no need to complain about unrated contest, just practice in this contest, after all, this contest isn't offering any prize

the important thing is you doing well in that kind of contest, and this codeforces round is one thing to do to achieve that, higher rating doesnt mean always win

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

http://codeforces.net/contest/302/status/A/page/24?order=BY_ARRIVED_DESC за 11 секунд прочитать и закодить даже А это круто)

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

Насчет задачи A под Python 3 — так и есть, оптимизировал все что можно, но 11 тест не проходил по времени. Если бы не увидел комментарий про это, может быть, и не догадался бы адаптировать для Python 2.

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

Очень интересные задачи, особенно С(div 2)/A(div 1), еле добил :) Жаль что контест не рейтинговый, поднялся бы)

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

Div 1 C / Div 2 E Yaroslav and Algorithm is very interesting! Anyway thanks for the great questions by the author!

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

Спасибо за задачу Div1-C, это классно!

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

    Я тоже очень пропёрся. Никогда бы не подумал, что встречу тут алгоритмы Маркова, упражнениями на которые меня гоняли на первом курсе.

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

Отличные задачи. Не понравилось странное ограничение в B, из-за которого людям приходится участвовать в соревновании на внимательность. E — красивая динамика, не успел дописать. D — подумать и свести к стандартному "сколько точек в прямоугольнике". С — быстро придумал, нужно забить на входные данные и активно пользоваться вопросами. A — больше всего думал, даже смешно. Никак общий алгоритм не мог осознать, в результате получилось, что от четности зависит его существование:) Спасибо за контест. Жаль, что система превратила его в нерейтинговый.

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

    А какую роль играли символы '?' в задаче Div1-C/Div2-E?

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

    У меня в Е какая-то жесть с динамикой по вектору, которую я минут 30 пытался упихать в ТЛ и на последней минуте соптимайзил до 2.8 на макстесте. Причем она на студии работала в 2 раза быстрее, чем в GCC. У тебя тоже что-то такое или нормальная идея?

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

      У меня печаль. Я дописал n^8. Я умею превращать это в n^5logn / много. Теперь оно не только получает WA, но еще я не понимаю, как это упихивать. Мой компьютер не может дать мне точного ответа, зайдет ли это в ТЛ.) За сколько у тебя алгоритм асимптотически?

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

        Авторское было за O(n^5). Сейчас его в разбор допишу.

        Сделано.

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

        Теперь я уже понял, что асимптотика у меня O(N6) (может меньше, но тогда я не знаю почему это так). У меня параметры — это количество поставленных чисел, максимальное поставленное число, а также вектор чисел W, в котором для каждого i от 1 до 50 хранится количество способов переставить данный массив таким образом, чтобы у нас было ровно i пар максимальных чисел, стоящих подряд. Переход делается за квадрат, но с кучей отсечений.

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

What a pity! It was a very interesting problem set. Thanks Sereja

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

В С у авторов есть решение, существенно пользующееся input'ом?

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

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

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

      О, а я только сейчас прочитал, что бывают знаки вопроса...

      Знак вопроса равен любому символу или не равен ничему, кроме себя? По условию получается, что это просто отдельный символ, а не wildcard. Но тогда почему не был выбран какой-нибудь другой символ, не имеющий wildcard-смысла?

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

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

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

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

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

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

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

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

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

The problems are so good. Thanks Sereja, sdya and Gerald. What was the 3rd pretest of Problem C!!!???

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

    I think you understood the task of problem incorrect, read again, sorry for poor English.

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

    comment deleted

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

    input:

    3

    1 2 2 2 2

    output:

    7

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

    Did you figure out how the problem works? I'm interpreting the problem as in a single operation you MUST change the sign of n numbers. In pretest 3, however, the solution would require changing the sign of four numbers while n=3, which I thought would be impossible...

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

      It is possible using two operations:

      -959 -542 -669 -513 160
      -959 -542 669 513 -160
      959 542 669 513 160
      
»
12 лет назад, # |
Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

O(m*n) solutions accepted in problem B Div2.
Edit
My apologies, i misread the solutions. Is O(n+m) complexity, because they keep the last position found.

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

    read the constraints again

    (It is guaranteed that vi < vi + 1)

    solutions are O(n+m)

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

      The worst test case is:
      n = 10^5
      m = 10^5
      ci = ti = 1 for 1 <= i <= n
      vi = i for 1 <= i <= m

      Ops! you are right, i misread solutions... they keep the last position found.

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

    you might be dont know two pointers :)

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

Thanks for brilliant contest. It could be a great rated contest if CF didn't crash, but as an unrated contest it was outstanding. GL & HF!

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

Шикарные задачи, очень жаль, что раунд нерейтинговый. Большое спасибо!

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

    Отлично, теперь не так обидно, что пропустил тур!

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

too slow system test :/

I'm waiting to add problems to practice.

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

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

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

Very nice problems!Especially problem C in div1!Thanks to sereja!

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

Weak test cases for problem B in DIV2

O(m*n) solutions pass the system test! m,n <= 10^5 !!


Okay I was wrong (It is guaranteed that vi < vi + 1) solutions are O(n+m)

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

    show me the code. i think it's O(m+n) solution, not O(m*n), because variable j can not decrease:)

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

trying to figure out div1 problem D. i believe the number of divisors of a number n is no greater than 2*sqrt(n), is there a tighter bound?

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

    Look at it as the number of multiples in the range [1,n]. Then you get:

    n/1 + n/2 + n/3 + ... + n/n

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

    Sum of numbers of divisors for numbers not exceeding N is .

    Also, number of divisors of N is o(Nε) for every ε > 0.

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

Задача В, тест:

3 1000
3000
0 0
0 1
0 3

Насколько я понимаю, ответ должен быть 1000. Почему решения, выдающие 0 (например, мое) прошли тесты? О_о

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

    Этот тест некорректен. ai ≤ 1000.

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

      Ок, а так? Суть то та же.

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

        Тоже некорректен:) d ≥ 1000.

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

          Окау, спасибо, тогда вопросов нет. Жестокая обфусикация условия >_<

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

            да, на этом завязано, собственно, решение)

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

              А я подумал, что заслал фигню, расстроился и ушел писать курсач в середине контеста >_<

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

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

Hi there, a quick question.

In Div2 D/Div1 B, what should the output of the following test case be?

3 1000
2000
0 0
0 1
0 2

Should it be 1000? Because my program outputs 0 and passed system test. Thanks! :)

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

Would you mind returning pagination on the 'Contests' page to its normal state (slightly more than 4 contests per page)?

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

So sorry to hear that...:(

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

The third topic what is thinking?

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

In the problem "Yaroslav and Time", I define INF as 20000005, and get "pretest passed". However, "wrong answer on case 51" in rejudging. So Sad that INF shall be 2*20000005 or bigger. PS: If dijkstra algorithm is used in this problem, it's okay. But if dp is used, this test case should be concered: 5 1000 1000 1000 1000 0 0 0 1 1 1 2 1 2 0 What I mean is that we shouldn't just apply dp in just (sx,sy) to (ex, ey), but the whole (-100,-100) to (100,100).

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

Can someone tell me solution of problem C div 2

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

    The problem tag is dp and math. However, I solve it in a more complicated way — bfs and greedy. First, I use bfs to get all the possible number of multiplying -1. For example, for n = 2, all the possible number are {0,2}. That's to say, I can multiply zero or two numbers in the array by -1. Then, sort the sequence and apply greedy algorithm. If I can make all the numbers positive, then do it. Else I make as more as I can. Be careful of occurrences of 0.

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

    Here's another solution:

    If there are any zeros inside the array, then you can ALWAYS make them all positive.

    If you have n is an odd number, then you can ALWAYS make them all positive.

    If you have n is an even number and there is an even number of negatives, then you can ALWAYS make them all positive. Else, you can ALWAYS make all but one of them positive.

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

      Here is a rigorous proof of the "always"es frznlich said.

      First, note that if n is odd, we can change any single number. To see this, take the number x that we want to change, and n more numbers a1, a2, ..., an. We do an operation to each of these: (x, a2, a3, ..., an), (x, a1, a3, a4, ..., an), ..., (x, a1, a2, ..., an - 1) -- basically every combination possible that takes x and n - 1 of the ai's. We can see that x belongs to n (an odd number) operations and hence changes sign, while every ai belongs to n - 1 (an even number) operations so doesn't change sign.

      If n is even, we cannot change a single number: The number of numbers we change is even (some number times n which is even), and two changes equal null, so the parity of number of numbers we change is an invariant. So it will stay even. However, we can change two numbers. If we want to change x, y, take numbers a1, a2, ..., an - 1 and perform the operations (x, a1, a2, ..., an - 1), (y, a1, a2, ..., an - 1).

      This means we can change all negative numbers to positive except probably one, and this "probably one" only occurs when n is even and there are an odd number of negative numbers.

      So what we should do is to determine whether the above condition occurs. Besides, we will also find out the sum of the absolute values of the numbers and to figure out the number with the least absolute value, which we will "sacrifice" as the single negative number if there is any.

      So our approach is this:

      Loop over all numbers. Compute the number of negative numbers in the input and call it neg, the sum of the absolute values of all numbers sum, and the minimum absolute value of all numbers min. If n is even and neg is odd, output sum - 2min, otherwise output sum.

      EDIT: Removed double post (phone acts up at times), useless statement to find the largest number, and useless assumption that zero is negative.

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

    A solution more suitable to a contest, however, is: notice the bound N <= 100 and do BFS on how many negative numbers there could be, since if you change x negative numbers and N-x positive ones in one step, then there will be N-2x more negative numbers (special case: if there's a zero, it's clear that they can all be made non-negative). You don't need to think about all possible cases, just use a simple algorithm to do that for you.

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

Can someone tell me solution of problem C div 1? thanks!

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

Can someone tell me solution of problem C div 1? thanks!

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

    One approach is this (works for any number):

    1. Place ? after the first occurrence of the smallest digit in the number.
    2. Move ? to the end of the number.
    3. If the last digit of the number is 0..8, increase it, remove ? and stop. Otherwise replace ? with ??.
    4. So long as the digit before ?? is 9, replace it with 0 and move ?? one step left.
    5. If there is another digit before ??, increase it, remove ?? and stop.
    6. If there is no digit before ??, replace it with 1 and stop.

    For example, the number 6299:

    6299, 62?99, 629?9, 6299?, 6299??, 629??0, 62??00, 6300

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

    Just output the following:

    ??0>>0??
    ??1>>1??
    ??2>>2??
    ??3>>3??
    ??4>>4??
    ??5>>5??
    ??6>>6??
    ??7>>7??
    ??8>>8??
    ??9>>9??
    ??>>?
    0?<>1
    1?<>2
    2?<>3
    3?<>4
    4?<>5
    5?<>6
    6?<>7
    7?<>8
    8?<>9
    9?>>?0
    ?<>1
    0>>??0
    1>>??1
    2>>??2
    3>>??3
    4>>??4
    5>>??5
    6>>??6
    7>>??7
    8>>??8
    9>>??9
    

    The above is composed of five parts: End marker movers of 10 commands, end marker converter of 1 command, converter processes of 10 commands, converter finalization of 1 command, and end marker initializations of 10 commands.

    At first, the string doesn't contain any question mark, so some of the end marker initialization commands (d>>??d) is encountered. There will be some double question mark, called end marker, inserted in the string.

    Now, some of the end marker mover commands (??d>>d??) will be encountered. This basically moves the end marker one step to the right. As long as this end marker isn't at the end yet, the end marker will be constantly moved, so the end marker will eventually reach the end of the string. At the worst case, the end marker begins in the front of a 25-digit string, taking 25 iterations.

    Next, the end marker converter (??>>?) is found, and the end marker becomes a converter sign (?). This converter sign's job is to add the digit exactly before it.

    Next, some of the converter process commands (d?<>d) will be encountered, which changes the digit in front of the converter sign. If it's not 9, the addition will not cause any carry, so we're done. Otherwise, the special 9?>>?0 command is encountered, which marks that we need to carry and so we need to add 1 to the previous (more significant) digit. At the worst case, the converter processes need to go all the way to the front with the number 1025 - 1 = 9999999999999999999999999, which takes 25 iterations.

    Finally, in the case the converter sign reaches the front of the string, we assume that there is an extra 0 in front of the string, and add 1 to it, hence the special (?<>1) converter finalization command.

    This takes 32 commands and at most 53 iterations at the worst case, no matter what the actual numbers are.


    To arrive at this solution, first you need to realize that 100 numbers is too much to handle by investigating the numbers; there must be some testcase that causes any submission based on handling numbers to fail. Too many numbers for too few commands. So there should be some easy solution independent of the numbers.

    Next you need to figure out that you need to find some way to mark the end of the string (so you can start adding), you need to handle all digits, you need to handle 9s added, and you need to handle 999...9s.

    The above is mostly trial-and-error after the above realizations.

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

Because the contest was unrated, There wouldn't be any editorial for it?

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

Mistakenly posted in russian

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

In problem B div 1, I failed at system test 52. There is some thing special in this testcase I couldn't find out . Can anyone help me? I think every station passed have to be inside the rectangle of point 1 and point n because when going out of the rectangle and returning, it will cost at least 2*d which is larger than any a[i]. However, it is inaccurate in test case 52 when the best route pass through outside points and then come to point n. For some more details
Test 52: 12 1211 1 5 7 1000 1000 1000 1000 1000 1000 1000 1 1 5 5 3 4 4 3 0 1 0 2 0 5 0 7 1 0 3 0 8 0 10 10 The best way: (1,1) -> (0,1) -> (0,2) -> (0,5) -> (0,7) -> (10,10)