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

Автор lydrainbowcat, 11 лет назад, перевод, По-русски

Всем привет!

Раунд Codeforces Round #185 состоится в Воскресенье, 26 Мая, в 19:30 по московскому времени (23:30 по ЦПВ).

Организатор раунда — zanoes, а задачи готовили:

  • Div.1E и Div.2B —— zanoes (Жанг Гаощанг),
  • Div.1D и Div.1A —— liouzhou_101 (Ванг Квишенг),
  • Div.1C, Div.1B, Div.2A —— lydrainbowcat (Ли Юдонг)

Тестеры — roosephu(Луо Юпинг), FredaShi (Ши Хаойе), sjynoi(Сун Джяю), sevenkplus(Гу Южу), MinakoKojima(Танг Фейху) и Riatre.

Выражаем особую благодарность Gerald за помощь в подготовке раунда, MikeMirzayanov за классную платформу и Delinur за перевод.

Распределение баллов будет стандартное, 500-1000-1500-2000-2500 в обоих дивизионах. Наверное, эти задачи проще задач из предыдущих китайских раундов :)

Это наш первый раунд на Codeforces, надеюсь, он вам понравится. Высоких вам рейтингов и удачи!

UPD: Мы очень сожалеем о нашей ошибке. Следующие слова были сказаны автором задачи div1A (div2C) liouzhou_101. http://codeforces.me/blog/entry/7773#comment-134702 .

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

UPD2: Раунд считается не рейтинговым.

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

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

Надеюсь, не будет как в тот раз: 3 автора, 6 тестеров и 20 кларов.

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

    И одна решенная задача

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

    Действительно, кларов почти не было. Всего лишь сделали нерейтинговым

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

      И сказали об этом под конец контеста, изрядно помучив всех!

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

        Если бы сказали сразу же, то писавших стало бы резко меньше

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

        Та там такая формулировка клевая что не ясно сделают ли не рейтинговым

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

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

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

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

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

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

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

              Скажем так это больше проблемы тех кто составлял этот клар чем тех кто так подумал.

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

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

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

          Вы лучше скажите будет ли раунд то рейтинговым?

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

      Контест "Made in China" оправдал свою марку.

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

This is my first time to be a tester :). lydrainbowcat considered me as a good tester XD I'm sure all of the competitors will enjoy the problems! GL & HF!

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

It seems Chinese authors always posts announcements early.

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

hope to have a great round

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

I hope that this round will be easier! Thank you!

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

Why the real name of Riatre is hidden?

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

it seems to be a great contest because there are many people that direct the contest.

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

UPD: только сейчас дошло, что вообще не в тот пост. :(

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

    Я слышал байку, что арена написана черт знает когда давно уволенными людьми так, что не способна передавать вектора размера более 50. Поэтому такие игры. Впрочем, челленжи "10 1","1 12" мне тоже кажутся странными.

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

      Так почему бы ее не переписать все-таки? Например, можно устроить контест в разделе Development — там и не такие штуки писали.

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

        И, спустя два месяца, победитель в разделе Development становится таргетом в разделе Algorithm. :)

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

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

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

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

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

          Пропих — бывает не так уж и редко. Структуры данных тоже бывают.

          А стандартные алгоритмы — это политика админов. Типа как "у нас здесь кодят, а не делают копипаст".

          Да и то с большим "но" — довольно много алгоритмов светились в задачах ТС, а по поводу потока и всего, что с ним связано, вообще отдельная шутка: "_если не знаешь, как делать 500 — считай динамику, если не знаешь, как делать 1000 — лей поток_".

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

          Впихнуть на какую-то дп N^5, когда авторское N^4 — чем не пропих? :)

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

Guys, If anyone of you know some good source to learn and practice all types of dynamic programming problems, it would be really helpful for me..!! and yup, I am not sure if this is not the right place to ask such questions or there is some separate forum.

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

    I think this is helpful

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

    In www.jutge.org you can find several collections, and an special one for dynamic programming.

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

    unfortunately, when you enter in www.jutge.org appears a message asking for accept a certificate. But it is not dangerous, you can accept, register, and use the judge without any problem.

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

Меня чуть-чуть смутило, что при перечислении задач, составленных каким-либо автором, между ними ставится "&", а не "v" или "|", потому что, вроде бы, логичнее объединять, но это мелочи

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

rp+=your vote; wish all of you can get a good result :)

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

A lot of maths is observed in the every past Chinese contest. And every time when they said contest is gonna be easy, it was tougher than usual.

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

Comma separated contest IDs in a link ?? :O Really nice idea :)

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

I thought I had registered for the contest, but apparently I hadn't...

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

Is anybody but me see six problems for Div2?

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

Thanks for this EASY contest!!

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

It seems that the problems are really very easy.

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

In the div2 contest, I can see 6 problems. But I can't see the Problem F. Is it a platform bug?

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

Is there any change about the problem:"Cats Transport"?

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

Believe me, I was pulling my hairs when I was reading problems D and E, The lines does not make sense to me despite of how many times I read those again. It is not so good to introduce too much mathematics in problem statements. The language seemed like some kind of cryptic language. I was very much frustrated while reading it. I can't imagine what would be the situation of person who is not so good in English.

Moreover there was no correlation of lines in the paragraph with each other. I am so frustrated with these problems. This is not at all a good translation work. Btw I am thinking that do the authors even try to read the problem to make sure that it is understandable in some definite amount of time ?.

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

easier than the past several rounds prepared by Chinese :) :| easier ?

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

1) Сходил пи-пи в начале контеста — слился в див 2
2) Задержал дыхание при написании А — стал красным.
Вот такой вот контест :)

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

Contest by Contest, Chinese writers are making it hard for me to believe their claims. :P

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

Об этом раунде, с учетом состава авторов и тестеров, а так же с учетом общей картины раунда и ситуации с задачей А — можно уверенно сказать Made in China

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

Contest is made in China.

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

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

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

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

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

    Например потому, что ситуация со взломами непонятная.

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

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

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

        Я вот что имел в виду.

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

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

      В некоторых раундах также имела место непонятная ситуация со взломами, но это не было поводом для unrated.

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

        Вопрос в том, насколько это влияет на тактику на контесте. Информация "у тебя не прошли претесты" и "твое решение взломали", меняет ее очень сильно, согласитесь.

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

so pity to see the unrated round. :(

hope that the next china round will be well-prepared.

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

CodeforcesReputation--; :|

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

    Code forces will stay my favorite website forever

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

      Codeforces is great and this has raised our expectation!

      But this doesn't mean that this mistakes are not important.

      We expect codeforces to be the best, not just good!

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

When everyone has worked hard in solving problems for nearly 2 hours , they say that contest will be unrated !! :(

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

contest unrated

this is very bad and intolerable

only that question should be out of rating

the desicion is condemned

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

Думаю ошибка в задаче C(div.2) большая чтобы раунд был рейтинговым...!!!

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

Coincidence? The last two contests that I participated in became unrated (182, 185) :( Couldn't participate in the others as they were held at a different time slot.

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

    Same here! It's been over a month since I've been able to participate in a rated Codeforces round. In the meantime, I've participated in 6 TopCoder contests!

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

    same here !!

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

I have hacked a lot of solutions in Div1A (Div2C) and I didn't have any problems with that. I suppose not a lot of people are affected. It would be a wonderful idea to unrate this round only for affected people.

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

2 unsuccessful contests within 4 successive rounds, from 182 to 185......This is very very bad..

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

Problem D is very similar to problem E from NEERC Northern Subregional 2009

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

Если бы мне каждый раз платили 10 рублей за каждое падение codeforces, то я бы был миллионером.

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

It's my fault that I've made an awful mistake on the checker of div1A&&div2C. Sorry to every participant and I feel most guilty. If I have a chance to prepare a round once more, I promise that I won't make such a mistake next time and we will make a successful round.

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

    Good luck) Thanks for the tasks

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

    Now why unrated contest? The hacks just can be retested..... 2 hours and a hard contest and now unrated....

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

    everybody makes mistakes, next time you'll do better :)

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

    As one of the authors could you tell please how many people were affected? Are there no chances to make this round rated?

    UPD: and don't get upset)

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

    Would you mind sharing old version of the checker? It will be interesting to "hack" checker and it can help future authors avoid making similar mistake.

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

      i think it's good enough if some problem setter check each other task, after all problem setters usually is consisted of some high rate people, right ?

      if there is still error, then, can't help it

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

    It seems, that it was impossible to make a bug in such a simple checker, but it was done.. If I were an admin, I would decrease your rating by 1000, because you should practice in DIV2A/DIV2B problems solving. P.S. Thanks for interesting problems! :)

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

      Your words are naive and irresponsible. You have no rights to blame others' faults in this weird way unless you have tried making checkers or something else before.

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

      Thank you for your feedback. It's necessary that my rating should be decreased by 1000 or more. To tell you the truth, my rating have been decreased by nearly 300 these days and now for every problem I always get AC after some WAs. So now you may be aware of my awful and sad situation then.

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

    =w=...liouzhou is so cool!.and we will support U as always

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

Интересно можно ли обжаловать CE на memset?  Cдал Е за 10 сек до конца и забыл его включить получил CE :( (мой g++ никогда на такое не ругается)

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

    Вы не подключили cstring (или string.h) что требуется стандартом.

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

      Да просто обидно, так на дорешивании все тесты прошло

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

    Он находится в "cstring". Если его не подключить будет ругатся.

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

    И как Вы предлагаете проверять решения в таких случаях? (не только в Вашем, но похожих) Отправлять в течение минуты на электронную почту, как это делается в Snarknews Summer/Winter Series раундах иногда?

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

Why not to make contest unrated for only those got pretest passed and they should get Wrong Answer?

and for those got unsuccessful hacking ,simply give them their points

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

    Yes, It is a good idea...Someone make successful hacking attempts or have accepted their codes, this problem does not affect them!

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

    As rating is a relative scoring, partially-rated contest is not fair.

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

      I remember a past contest in code forces happened the same problem , the checker has bug. the contest was partially-rated for only not affected contestants

      I don't remember exactly what was the contest

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

      There is no absolute fair thing in the world.

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

пусть будет рейтинговым.

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

Как решать B (div 1) и D (div 1)?

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

    Решение D (div 1)

    Если любое число X возвести в куб 48 раз по модулю P (то, которое в условии), то получится снова X. Нужно реализовать дерево отрезков и в каждой вершине хранить 48 чисел: сумму на отрезке, сумму кубов, сумму 9-х степеней и т.д. Тогда возведение в куб — это просто циклический сдвиг этого массива.

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

      А из чего следует первое утверждение?

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

        UPD. 3^48 = 1 (mod P-1)

        Тогда это следует из малой теоремы Ферма.

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

        .

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

          Как без брутфорса получается это магическое число 48?

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

            А зачем без брутфорса? P-1 и 3 взаимно просты, значит 3 в какой-то степени дает единицу. Эту степень можно найти в лоб, потому что она не больше P. Если бы P было большим, можно было бы за O(P^0.5 log P), пользуясь малой теоремой Ферма, повозводить 3 в степень делителей P-1.

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

              Более того, тупейший брутфорс, который каждое число от 0 до P-1 возводит в куб, пока не получит себя же, и кидает количество итераций в сет, работает ну МАКСИМУМ несколько минут. (Мне как раз хватило, чтобы написать решение по B, к сожалению, при неправильном понимании условия.)

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

Предлагаю все китайские раунды сразу анонсировать как non-rated и прямо в посте анонса отговаривать от участия в них.

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

    Я это сообразил на один раунд раньше :D

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

str[4294967293] didn't get a runtime error :(

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

Так что за фигня была в задаче С див.2 ?? Вроде, все норм было.

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

Хороший контест

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

It seems to be the second or third consecutive Chinese round that is unrated >"<. It's really a pity that these rounds become unrated in the end, since as far as I can remember, there are enjoyable great problems in these rounds. Some of the participants are frustrated for yet another unrated contest after 2 hours of hard work, but I believe the problem-setters are even more regretful. I wish all the best that the next round you hold will be successful and flawless.

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

Do you think it's a funny joke to say "In our opinion, problems are easier than the past several rounds prepared by Chinese :)" if problems are very hard in fact? I think many people are very frustrated because of unbalanced problemset, not because of mistake in checker.

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

Ah ok, got it, it's a Chinese to English translation. LOL

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

So, div1 B reduces to the following:

Having n descending sorted numbers a[i], find p (<= 100) numbers i[0] = 0 <= i[1] <= .. <= i[p] s.t. the following is maximized:

sum_{j = 1:p-1} a[i[j]] * (i[j] — i[j-1])

How to do this ? A dp solution in n^2*p works, but we need smthg better.

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

    You can improve it with this: http://wcipeg.com/wiki/Convex_hull_trick

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

    You can note that the recurrence takes the form, dp[p][m] = min_{m' < m} (m — m') * a[m] — (psum_a[m] — psum_a[m']) + dp[p — 1][m'] = m * a[m] — psum_a[m] — m' * a[m] + psum_a[m'] + dp[p — 1][m'].

    The -m' * a[m] + psum_a[m'] + dp[p — 1][m'] part takes the form of a line with slope -m' and y intercept psum_a[m'] + dp[p — 1][m'], so you can optimize this with convex hull trick. Since x coordinates in the queries and slopes in the added lines are monotonic we don't need the full convex hull trick, leading to a short O(m p) solution.

    My solution (http://codeforces.me/contest/311/submission/3778498) is O(m p) but failed because it uses integer division, which leads to a high constant factor, T_T. There is a nice solution by RAD at http://codeforces.me/contest/311/submission/3776732.

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

Верх таблицы через 35 минут

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

I'm curious about what chinese coders consider easy, a problem very similar to B was the hardest one in the latinoamerican regional last year.

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

Is this good that first rank contestant nickname similar to testers nick name?

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

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

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

can someone explain me this test case?

it says 10 lines but I see only 6

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

    Full input is not provided.

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

    UPD. sorry, my mistake

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

    There are blank lines in that test. In my opinion, this was stupid.

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

      stupid !! in real life you code should solve the problem regardless of the cases .

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

      well the problem clearly states that a sentence can have spaces so your solution should solve the case of having one space as a sentence. Mine unfortunately didn't because I wasn't paying enough attention when reading the problem! Better luck next time! :)

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

        Sentences containing spaces are fine. I'm talking about sentences which consist of a single newline character.

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

    Yes, full input not provided. So u might be getting WA on this TC, because u haven’t used cin.ignore() after inputting the integer "number of lines". Another way could be taking input of each line character by character, avoids this problem.

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

With 110 minutes' hard working and I saw it's unrated.

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

just don't accept the hack of codes which doesn't pass pretest and then rejudge the whole contest!!! it's not hard, is it?

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

То, что контест нерейтинговый это окончательное решение?

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

The fact that in all tests except first for div1B M is greater than 100 is very nice. Please, do that in every your problem, providing any info is unnecessary.

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

Run an output of the programm on the code, given in statement. Where can be a mistake in checker?

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

    Probably run 2000*2000/2 iterations for checker is not so fast — so they probably have optimized it somehow.

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

      You are strongly mistaken, 2*10^6 iterations will be executed very fast in the modern computers. Now there is year 2013, not 1980 :) Anyway checker has enough big TL (about 10 seconds).

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

    Just mistype in distance function as I know.

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

Some test cases are long and incomplete when showing on screen. Is there a way to allow for downloading of the complete test cases after the contest is over?

Thanks.

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

I have second absolute place in Div 2 first time in my life and round is unrated.

I'm the happiest man in the world :D

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

Эх. После большого перерыва решил снова поучаствовать в Codeforces и вот такая незадача :) Но как разминка перед последним отборочным RCC — более чем подойдет

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

Наверное, все-таки будет нерейтинговым, так как эта задача есть той, по которой определились места, особенно в div 1

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

Is there any reason for the trend toward extremely high constraints recently (eg, Div1-B today with M*P <= 10,000,000)? It's quite annoying to see an idiomatic solution fail simply because it wasn't 'optimised' enough.

In the case of B, it seems very difficult to use things like std::deque to keep track of the convex hull without timing out; to succeed I had to hand-code a replacement, ie. 37781213780175.

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

-Вопрос решен.

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

    В псевдокоде, условие на больше или равно. Т.е. нужно строго меньше, а в Вашем варианте — выпадает равенство, так как разница всегда n + 10

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

And how about ymxlkAc? It's not usual to see such "new user" in a normal(not Div.2 only) round.

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

Жаль, впервые попал в первую сотню, а он не рейтинговый

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

Well, now I can see that rounds wrote by Chinese people are unusual. There are many writers, so the problems turns out to be new and interesting, that's a nice thing. :)

Problem A is something new, but I think it looks like a riddle instead of a algorithm contest problem. It contains lots of details and looks very artificial. The core is this line: "if (p[j].x-p[i].x>=d) then break", I first misunderstand it into "dist(p[j], p[i]) >= d" and it becomes very hard to solve.

Problem B is too hard in my opinion. And I don't know if some of the writer/tester has read this problem: http://poj.openjudge.cn/campus2013/A/. It was a problem used in this month, nearly the same with this problem but with lower constraints. I know the key of this problem is DP optimizing, but it's not so good to use it if you know that problem was used in PKU's contest. And the DP optimizing part looks too hard for a 1000p, it required some detailed calculation.

And as for problem D, I find this sentence: "He tells you that because the answer may be too huge, you should only output it modulo 95542721.", it is somewhat misleading, "the answer may be too huge". is not the only reason we have to "modulo 95542721", one another reason is: (3**48)%(95542721-1)=1. Anyway it's an interesting idea to do some hack in the module number.

I haven't read problem C. And for problem E, it's good, but I think the statement can be better: "He will think SmallR succeeds if and only if on some day", it looks like we can satisfy this folk and then do some operation and satisfy another. Yes, then you know why it says "a kind of medicine which can be valid for only one day.", am I taking an English reading exam?

Overall, I would say it's an interesting contest, but it could be better (and rated) if they were well tested.

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

На 4 контеста — 2 нерейтинговых. Отлично, codeforces.

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

I saw a code(Your text to link here...) to make negative indexing ....

But this negative indexing didn't cause Runtime Error not even in my compiler ...

I wonder why ???

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

Что??? Нерейтинговый??? А знаете почему я такой злой? Потому что на 45-й минуте я был четвертым в списке. Первый раз занял 60-е место в DIV1 и облом..

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

    "на 45-й минуте я был четвертым в списке"

    Одного этого достаточно, чтобы раунд был не рейтинговым :)

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

      Старые знакомые? Я тебя еще порву!.. официально, а не как в этот раз :)

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

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

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

Раньше у codeforces была одна большая проблема: возможность почитать задачи, ничего не сабмитить и остаться без "наказания". Другими словами — очевидная необъективность рейтинга. Но с некоторых пор добавилась еще одна: нерейтинговые раунды через раз. Товарищи, это уже перебор.

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

    ... а кто минусует — тот читер!

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

      В том что раунд не рейтинговый никто не виноват, нельзя быть на 100% уверенным что раунд без ошибок.

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

      Интересно, по какой логике?

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

        Поясню. Допустим, в некотором раунде гробовые задачи. Пусть участник X, проявил невероятную силу мысли и духа, решил одну задачу к концу раунда с десяти попыток и получил за нее 150 очков. Пусть участник Y не придумал решение и ничего не отправил (подобно большей части участников, прочитавших условия сложного раунда). По здравому смыслу, участник Х заслуживает заведомо большую дельту к своему рейтингу, чем участник Y. Но на деле получается иначе: участник X занимает одно из последних мест и -100 к рейтингу, а участник Y — никакое место не занимает и +0 к рейтингу. В комменте выше я назвал это большой проблемой codeforces. И предположил, что несогласен с этим может быть только тот кому текущее положение нравится, т.е. тот, кто участвует в раундах по методике "участника Y".

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

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

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

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

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

              Ну все равно суть кодфорсеса не в рейтинге

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

              А в чем принципиальная проблема? За рейтинг что, деньги платят? Он ведь ничего не решает и ни на что не влияет.

              Зависть к тому, у кого более высокий рейтинг из-за таких манипуляций (_если вообще о каком-то пользователе точно известно, что он так поступил в определенном матче_)? Так к чему переживания, он ведь нечестно получил рейтинг, все ок... На реальных соревнованиях будет видно реальную картину.

              Ощущение вселенской несправедливости? Не смешите)

              Еще, как вариант, нормальное решение проблемы — тренироваться, поднимать скил, и все равно обгонять этого нехорошего человека в рейтинге))

              Кстати, чем выше уровень, тем меньше смысла в таких манипуляциях. Здесь не ТопКодер, где красный цвет — это всего лишь умение стабильно решать одну задачу. Поэтому если человек будет в начале матча весь набор пересматривать и думать, решать ему или нет — у него ничего хорошего из этого не получится) Разве что перед матчем заранее решить, писать его или нет (с учетом того, кто автор).

              Короче говоря, проблема есть, но я не вижу смысла так много о ней говорить. Если в чьем-то случае рейтинг что-то решает (формирование команд в университете, наличие финансирования, еще что-то в этом духе) — тогда еще куда не шло. Но ведь в 99% случаев он не влияет вообще ни на что.

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

                Замечу, что ты не прав про топкодер, я стабильно решаю одну задачу, и выше 2000 так не подняться

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

                  Твой никнейм там такой же, как и здесь? Если да, то не соглашусь) Когда стабильно решал одну задачу — получал неплохой плюс и двигался в сторону красного. Сейчас немного не складывается (весьма стабильное решание одной задачи — за 3 матча ТСО нарешать задач на 97 баллов), но я там никакого упирания в потолок не вижу.

                  Отфильтровал свою статистику, выбрал последние 7 матчей, в которых у меня систесты проходила ровно одна задача.

                  Из них 1 раз это была вторая задача, 6 раз — первая.

                  Изменения рейтинга для второй: 1979 -> 2028

                  Для первой: 2073 -> 2127, 2028 -> 2082, 2082 -> 2110, 2216 -> 2251, 2251 -> 2232, 2232 -> 2239.

                  Один раз из шести минус, 5 раз — плюс. Что я делаю не так?

                  Ну как бы да, иногда получается решить две и получить +100) И иногда вторая бывает очень уж халявной, ее сдают 250-300 людей, и тогда одной задачи мало.

                  Но в целом — вполне хватает. Есть какой-то сайт, на котором можно посчитать для заданного контеста и заданного места, какому рейтингу оно соответствует, можно поискать его (у меня в закладках нету), так я когда-то там для 10 матчей подряд просчитывал, какому рейтингу соответствует попадание в топ-10 по первой задаче, и у меня для 8 из 10 получилось больше 2300.

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

can't unrated contests be added to the contests list of a contestant? thanks

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

I think we cannot complain them too much,after all this is their first CF round.The reason you all angry maybe is that you binding them together with last several Chinese rounds.But It is unfair to them.

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

Я тоже потерял 300 очков за эти ошибки.

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

On codeforces contest will be held only Sundays? I saw last contests and Early in week was many contests. what happen now?

»
11 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
I do not have time to participate in a number of competitions, this one I think I can get a better grade, yes I do , with good grade. But no rating changed.
I may not to blame the one who hold the round, but I do not want this happen again.
»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Why my problem A is skipped??? After the contest, I submit again and it Accept! So why my solve in problem A is skipped? someone can help me?