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

Привет, Codeforces!

22 августа, в субботу, в 19:30 MSK состоится 317 раунд Codeforces.

Раунд подготовили для вас сотрудники компании AimFund: Kostroma, riadwaw, yarrr, gchebanov, ArtDitel, SirShokoladina и zeliboba.

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

Благодарим Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Polygon и Codeforces, координатора задач Codeforces Макса Ахмедова (Zlobober) и Марию Белову (Delinur) за перевод условий на английский.

В первом дивизионе будет разыграно 200 футболок c символикой нашей компании. Прочитать подробнее про нас и наши вакансии можно на сайте aimfund.ru и в анонсе этого раунда.

Этот раунд подготовлен в рамках программы "5 лет CodeForces", как часть нашего подарка сообществу. С этого раунда на CF начинается серия thanks-раундов, которые посвящаются людям и компаниям, пожертвовавшим значительные средства.

Всем удачи и высокого рейтинга!

P.S. Для участников петрозаводских сборов в четверг в 8 вечера будет организован фуршет в Пауланер Бройхаус.

P.P.S. Разбалловка: 1 дивизион 750-1250-1500-2000-2750, 2 дивизион 500-1000-1750-2250-2500

P.P.P.S. Топ-20 участников второго дивизиона также получат футболки.

Разбор

P.P.P.P.S. Друзья, с большим удовольствием сообщаем вам, что мы начинаем отправку наших фирменных футболок их счастливым обладателям по всему миру. Надеемся, что они вам понравятся, и вы будете носить их с удовольствием :)

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

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

Непонятно про дивизионы, скажите я могу выграть футболку или нет???? http://codeforces.me/blog/entry/19327

Я не разбираюсь в дивизионах подскажите пожалуста!!

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

    Если ты до начала раунда перейдёшь в div1, то да, у тебя все шансы.

    Если что, ты во 2 дивизионе.

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

      А как перейти??? Если это ьесплатно то я не против

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

        Возможно, ты сможешь найти человека, который за ночь сделает контест, договориться с Майком и поставит его на 21.08. Так что всё в твоих руках. Дерзай!!

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

    Тут был неудачный сарказм.

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

Почему нету футболок для второго дивизиона? Если подумать у участников первого дивизиона есть футболки по сравнению второго дивизиона. Если не дадите футболок тогда вообще не делайте раунд для второго дивизиона

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

    А ты решаешь из-за футболок?

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

      Нет конечно. Сколько человек участвует на втором дивизионе? Примерно 2500 — в топ 200 войти не очень легкая работа. И надо убрать фейк аккаунты — например участие минимум в 10 раунде

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

        Что за бред? В div2 слабые участники,которые "не заработали" такой трофей(футболку).

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

    И помимо тебя 2 дивизион будут решать около 4000 человек, которым не важно, дадут футболку или нет

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

      Думаю получит футболку им не помешает

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

        Это лишь обесценит моральную цену футболки.

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

          Будешь ли ты рад если получишь футболку?

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

            Нет, т.к. я недостаточно силён, что бы получать футболки на контестах

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

            Мне кажется что любой будет рад награде за свои умения(и не имеет значение уровень этих умений)

            Я например получив свою первую футболку был сильно рад(ВКОШП 2014), по правде говоря не одну, а сразу две =)

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

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

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

      Так почти на всех div2 раундах в топе 5 "ребята, которые ни разу не участвовали в соревнованиях".

      Сначала хотел написать: почти на всех div2 раундах в топе 5 чёрные, но понял, что меня могут неправильно понять. :)

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

        Черные... А ведь те кто не правильно понял твой коммент по сути являлись бы расистами, а значит ты бы получил от них респек(в виде +)

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

      А если добавить условия -- участие минимум 10 раунде

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

        Это глупо, меня до сих пор бесит что надо принять участие в 30 контестах, что бы получить тренерский доступ =(

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

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

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

    В чем фишка футболок? Они что-то в итоге дают?

    Простите меня, если это глупый вопрос, и я не вижу чего-то очевидного, просто я не очень глубоко погружался в спортивное программирование :)

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

      Если выиграешь 20 футболок, то тебя пригласят в тайное мировое правительство.

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

      Просто для вознаграждения и нечего больше

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

      Футболка для того, чтобы надеть ее лет через 7-10 и все знали какой ты старый :-)

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

If you in div2 and you want win T-shirt upvote this comment

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

    You know if they do that nothing changes...

    Cause all of div.1 programmers will join in div.2 by another account and not only you won't get any t-shirt but also you may have worse rank and rating...

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

      Would be interesting with 10 extra T-shirts. For the first to solve each question.

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

        Hmmmmm... :/

        It's a good idea at all but again nothing changes for div.2 users i guess...(at least for problem C,D,E div.2)

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

          Be careful. When someone says 10 extra T-shirts, It means first accept for each question and each division.

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

            I knew that...

            But the div.1 participants again will join div.2 and they have better chance to get t-shirts(also they can use 2 accounts and if they didn't success to get t-shirts in div.2 they will fight for top200)

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

    Really? Why do you think all the people are like you? Contests are for challenges and learning more.

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

this round is not combined. so "Top 200 participants" means?

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

Is it rated round?!

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

I think it should be combined division round :)

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

    Sorry, but we haven't got appropriate problems for combined round.

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

      Then, Top 200?

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

      Okay, but it's a bit sad. Combined rounds are great :P If you want, and if you have time for it, you can think about change it to combined round, for example taking some problems from div2, other from div1 and maybe add one additional problem? I think cf community would really enjoy it, am I right? :D

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

        "Combined rounds are great" — no, they are not. Actually I'm very happy that this round will not be combined.

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

          Why? I'm actually unsure on the matter and I think it'd be interesting to hear opinions from both sides.

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

            Basically because there are huge rating rises and problems tend to end up unbalanced with too many easy ones for a red (that's a thing with normal rounds as well, but a gap between C and D out of 5 isn't as bad as a gap between F and G out of 8).

            The authors of the round probably realised it.

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

      yes,separate round gives more learning opp. to the newbies .

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

    Am I the only one around here,

    who feels that combined division round causes worse rating inflation.

    My friend increases rating very heavily, even skips a color (blue to orange, skipping purple) on a combined division round.

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

      I think the reason is that many who have been away from competitive programming for a while comes back for the combined rounds. Their rating will be at the level when they were at their top, but now they are rusty so they will lose points on average meaning that everyone else will gain points on average.

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

        But because of rating inflation, those who comes back after a long time doesn't have very high rating.

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

          Rating inflation only effect div 1 since the flow between div 1 and div 2 is so slow. That's another thing, rating can only enter div 1, rating never leaves div 1 except for combined contests. I wonder how TC handles this, they don't have combined contests right and the rating have been pumped from div 1 to div 2 for like over 10 years right?

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

          I checked some old accounts now, most have rating curves roughly like this:

          http://codeforces.me/profile/hos.lyric

          You can't really see the rating inflation on them since most of them haven't gained anything the past 2 years even though they played continuously. If they had stopped for 2 years instead and then came back they would definitely have too much rating!

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

There were old legends about some company planning to run their round within the next month... :D

Looking forward for your round guys!

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

Div 1 users : "It's time to register for Div.2" :((

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

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

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

Oh Yes,I think this contest is like Goodbye contest and All user Receive high rating

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

Футболки — забавно. Среди всех раундов Codeforces в в которых разыгрывались футболки я не получил обещаного приза ни с Rocket Fuel, ни с MemSQL, ни с Croc. Вы все просто по привычке обещаете футболки, или правда они есть?

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

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

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

Помнится 5 месяцев назад вы писали В течение месяца мы планируем провести свой раунд =)

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

    Возможно, это значить — как в Италии: ответ на "когда будет раунд" всегда остаеться "в течение месяца".

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

      Упершыню бачу, каб ты размаулял па-руску. А так зразумеешь?=)

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

        Упершыню бачу, каб ты размаўляў па-руску. А так зразумеешь?=)

        Видимо в Корее не очень хорошо с белорусским языком.

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

Hello, what do you mean by "Scoring system will be static" ? what's the difference with the last round ?

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

    "Scoring system will be static" it is mean, that scoring system won't be dinamyc (max scores for problems you will know before round)

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

Though its very obvious only Div — 1 will get t-shirt and they should get but it will more exciting for all Div — 2 coders like me if we get a chance to complete with Div — 1 coders . A collaborate Div 1 & 2 round will be more interesting for everyone and Div — 2 coders get a chance to win t-shirt also .

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

    If it's combined, ((we will fight to win a t-shirt but nothing will happen as usual)) :D

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

      I didn't perform well any of previous collaborate contest but i like these contest most because one can get the proper picture of his/her current state . So just the opportunity to participate with Div 1 coders is enough for me :D

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

when you want to give t-shirts. you must prepare one both division contest.(like round Codeforces Round 300)

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

thanks for preparing this codeforces round.

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

Come on! you gotta give Div2 participants something. Even a "Random x from top y" would be fair.

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

Where can we see the t-shirt's.

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

ВcемУдачИЗавТРА!!

Пысы чото я не нашел в правилах что жедать удачи плохо http://codeforces.me/help#q6
не трогайте больше мои коменты если сами правила не знаете!!!

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

That's sad for div 2. Even "random x from top y" method would be great. But thanks for the contest anyway.

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

This would be a good time to get red + T-shirt!

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

I guess if they had 400 t-shirts they would give 1 each to both division's 200 toppers. But they only have 200 t-shirts.

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

how about allowing div 2 users to submit div 1 D and E if they solve upto div 1 C ? ( no extra time )

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

    Yeah, surely, imagine how exactly that should look like and how big changes this will demand in whole system of Codeforces ( ͡° ͜ʖ ͡°)

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

if a div1 user makes a fake account for div2 contests it shows that he/she is more programmer than human!

i think being human is more important than being programmer!!!!

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

Will it be possible for you to provide T-shirts to some(your limit) top div2 rated contestants?

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

    i'll buy an account gg easy

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

    I don't know he got -30 by just proposing something. Seriously, what's wrong with these people? I honestly think that there can be very few people who can still perform in div1 top 200. And if you offer a very few T-shirts in div2 as he suggested, many coders in div2 can be challenged to perform well. It will be an inspiration for those who can win in div2.

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

      There will be a lot of fake accounts from div 1, because it's easy to win div 2 than being in div1 top 200.

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

        Yeah possible. But if one can win in div2 and solved same quality problems as in top 200 in Div1, Why not give a T-shirt? ( Since div1 and div2 doesn't have same problems, it is troublesome I guess).

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

            In Codeforces Round 300, there are two div2 participants though :P. Imagine if you were one of those guys, and you don't receive T-shirt.

            But I see what you're saying. It is not gonna happen 99% sure.

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

              If you are good enough to get top 200 in div 1 then it takes just a single contest to become div 1 so they can only blame themselves for not doing the contest held a week ago.

              If it is the unlikely case that the person have only memorized solutions and thus can't reliably get into div 1 then you could argue that they aren't worth a T-shirt even if they did well in this specific contest.

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

        I mentioned that.

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

    I did not find too many points.

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

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

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

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

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

I speek Croatian and Croatian is similar to Russian, can I also apply?

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

Good luck :)

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

Bless All!

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

I think I will solve 2 questions today

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

А где находится Пауланер Бройхаус? И как туда попасть :-)

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

    отель Park Inn у ЖД вокзала, вход со стороны перекрестка)

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

Good luck everyone! :)

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

Is scoring the same for both divisions?

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

Last one isn't usualy 2750, right?

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

сложно

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

Tough set. I guess those t-shirts are really special.

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

div0 contest :))

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

    I think that's a great idea. One more division for the Gods :)

    But it'd require to prepare 2 more problems for a contest...

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

Ребята из Aim Fund, вы вообще слышали что-нибудь о простых задачах?

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

    Когда несколько красных собираются — то получается такое

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

Did anyone else get WA on problem B test 10?

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

    So many times. And I think I figured out why: you are supposed to take the least cost sell orders, and print them descending. I think :P

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

      I coded A and B very fast but I faild at the same point, Damn my luck.

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

      From what I see in statement ,in the order book for sells they are sorted descending.Even if you want to take first s lowest agg sells. Tricky statement.

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

    Yes. Then I found that I hadn't noticed this : "A buy order is better if it has higher price and a sell order is better if it has lower price". After considering it, passed.

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

    Along with 4 failed attempts, yes (

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

По ходу много народу забило на контест, увидев задачу А :-)

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

    А как решить?

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

      Например, перебрать одну сторону, а для остальных посчитать число вариантов за O(1). Понятно, что если одна сторона зафиксирована — в геометрическом смысле надо найти количество точек в прямоугольнике, от которого что-то отсекли прямыми вида x + y = C. Это можно посчитать, поразбирав случаи.

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

      Если ты хочешь увеличить ровно на l см, то ты это можешь сделать (l+1)(l+2)/2 способами.
      Далее смотришь, сколько способов тебе не подходят. a+la<b+c+lb+lc
      b+lb<a+c+la+lc
      c+lc<a+b+la+lb
      Я не уверен, но мое предположение было, что может не выполняться максимум одно неравенство. Рассмотрим первое например:
      a+la >= b+c+lb+lc
      a+2la >= b+c+l la >= (b+c+l-a)/2 То есть (b+c+l-a)/2 = x — минимальное кол-во см, которое надо добавить к a, чтоб получить вырожденный треугольник

      Отсюда, кол-во способов, чтобы нарушить первое неравенство (l+1-x)(l+2-x)/2.

      Аналогично рассматриваются последние 2 неравенства.

      P.S. Сильно сбивчива мысль, ибо сам не понимаю, как это работает да и работает ли.

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

    Я почти забил, но потом что-то сказало: "Ты что, тупой что ли, не можешь A решить???"
    В результате, я заслал A за две минуты до конца... Фиг знает зачем:D

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

      А я заслал ТЛьное решение за 10 минут до конца и потом сделал 11 неудачных взломов... Фиг знает зачем :D

      P.S. Послал бы ты своё решение пораньше — и тебя бы попробовал взломать =)

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

    Неожиданный поворот, div2 всё-таки получит футболки... =)

    Не, ошибся, решило больше 200 человек.

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

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

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

I am impressed. Thank you for round anyway.

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

So light pretests for div2 C( My solution with O(n^2) complexity passed them, but I know there will not be such luck on final test. So I interested how to solve it faster?

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

    How would be a n^2 solution for it? Couldn't even think about it!

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

    Just calculate the inverse instead. The total amount of ways you can increase is (l + 1)*(l + 2)*(l + 3)/6, then you just remove all cases that don't work.

    You can't form a triangle with a set of numbers if one is larger or equal than the sum of the other two, so just iterate over all increases (O(n)) of a, b, and c and for each increase reduce the answer by the amount of ways to increase the other two such that their sum is less than the largest one.

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

      Like this:

        ll f(ll a, ll b, ll c, ll l) {
          if (a < b + c)
            return 0;
          ll d = min(l, a - b - c);
          return (d + 1) * (d + 2) / 2;
        } 
        
        int solve(ll a, ll b, ll c, ll l) {
          ll ans = (l + 1) * (l + 2) * (l + 3) / 6;
          for (int i = 0; i <= l; ++i) {
            ans -= f(a + i, b, c, l - i);
            ans -= f(b + i, a, c, l - i);
            ans -= f(c + i, b, a, l - i);
          }
          cout<<ans;
        }
      
      
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It is probably a stupid question, but why ~~~~~ ll d = min(l, a — b — c); ~~~~~

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

          Its the amount of increases that you can distribute between b and c. Of course you can't distribute more than l and if you distribute more than a - b - c then the triangle becomes valid.

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

        nice and simple solution thanks :)

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

        How is it intuitive that there are no overlaps? When you're increasing 'a', you also increase 'b' and 'c' On a closer look, when you increase 'a', and hence increase 'b' and 'c', for those values always 'b'<'a'+'c' and 'c'<'a'+'b' But this wasn't really intuitive :|

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

      Why the total amount is (l + 1)*(l + 2)*(l + 3)/6 . I am a little bad in maths.

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

      It's probably stupid, but could you explain how did you get formula for calculating total amount? Thanks in advance.

      UPD: Same comment as above, sorry for duplicate.

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

    suppose we increase a,b,c by x,y,z

    fix z then the triangle ineq conditions reduces to let v1 = x+y,v2 = x-y

    1. x+y >= max(0,(c+z)-a-b+1)

    2. x+y <= l-z

    3. x-y >= b-(c+z)-a+1

    4. x-y <= b+(c+z)-a-1

    subject to above contrainsts,we hvave to find all such pairs such that v1%2==v2%2 and v2<=|v1|

    to do the rest, you need to analyse each interval properly.

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

the hardest contest i have ever seen.

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

Div1 — A today is so mind-blowing (harder than Div1-B IMO). Is there a simple way to solve it?

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

    I tried iterating through all ways of adding an amount to a and then binary searching for the min and max values for b, therefore fixing c but could not get it to work. Is this a valid solution?

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

... And how to solve problem A (div. 1)?

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

How div1 B is solved by a lot of contestants it's very hard!! maybe a lot of them are going to fail system test?

div1 C is far easier than div1 B but they both have almost the same points!! I didn't submit my solution because of this reason

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

    I can prove my solution at div1B and it's not that hard

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

    div1 B is dynamic programming + some greedy approaces. Actually if you can notice, that elements, which absolute difference is taken are located in non-intersecting sequences. Also it is obvious, that elements in such sequences are neighbours in sorted array. So you should find the optimal way of splitting the sorted array in "blocks", minimizing the target function. In fact there is no more, then 2 different length of blocks are possible, so you can do DP in k^2.

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

      Yes, this is the only observation required to solve this problem that there wont be more than 2 different lengths. Thanks for the explanation dude :)

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

    Not exactly. C demanded a lot of stupid code, while code for B was pretty easy. C was not idealogically complicated, but not fun to code and multiedges stopped me for half an hour.

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

      I have implemented it in simple way:

      handle cases for variables appearing only once and variables appearing twice but in same sign and check which nodes are satisfied.

      put all unsatisfied nodes in priority_queue such that the top is the node with least degree, each time pop a node from queue and select arbitrary edge connected with that node to make that node satisfied , then delete that edge(the other node degree is reduced by 1) , if in some moment degree of a node which is not yet satisfied is 0 then "NO" otherwise "YES"

      didn't even have to check for trees or search for cycles

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

    You wont solve 1 C if you haven't seen the problem before since it is a huge research topic.

    Also you wont improve if you care about points, better to fail and learn than to not try at all.

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

      This particular case it's not a huge research topic and I think I solved it(or at list I have a good and proved idea, maybe some bugs but I have a good idea) without meeting it before

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

        Oh, I read the problem wrong >.<.

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

          Aparently, me too=)))I thought that you can have just -2 and 2 ore just one of them but you can have two of -2 or two of 2 which is very easy tot treat.I don't really understant why did they do that :(

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

    Div1 — B is just DP: imagine we will build each subsequence {a(i), a(i+k), a(i+2*k), ..} seperately, and to make the result minimum, each subsequence must be sorted. We will have to build cnt1 = n%k subsequence of length n/k+1 and cnt0 = (n-cnt1*l1)/l0 subsequence of length n/k. Sort array a in ascending order. In order to minimize the result, there must be no pair of two subsequence that intersect with each other. So, this problem could be reduced to: finding a way to split array a (after sorted) into cnt0 continous subsequence of length l0 and cnt1 continous subsequnce of length l1. Notice that cnt0*cnt1 <= n, so a DP with complexity O(cnt0*cnt1) would work.

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

      You wanted to say cnt0*cnt1<=(k*k), no?

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

      Wow, that's actually a solution I was trying to code during the contest! Can you please describe your DP a bit more detaled?

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

    B was very nice and much easier than A, at least in my oppinion. I needed about 10 minutes to figure out the dp after I read it but I still have no clue about A :(

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

That CNF-2 (Div1-C) is easy but hard to implement (many corner cases)

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

    If you compute the number of degenerate triangles and substract this number from the total one is very easy but it's hard to think.I guess this was the slution without corner cases

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

      Did you mean Div1-A?

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

        Yes I saw it later when I already had -30 contributin :)) but it didn't make sense to refer at div1C.There were 3 cases in my solution and I treated each of them in one line.Any way sorry for misunderstanding

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

    It may be implemented without corner cases:)

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

У меня одного Диниц не работал в C и пришлось прибегнуть к бурундуковой магии?

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

    Судя по результатам на претестах — у очень-очень многих Диниц не работал) У меня тоже, между магией и Хопкрофтом-Карпом я выбрал Хопкрофта-Карпа.

    Хорошо хоть в претесты включили такой тест, а то было бы вообще трололо.

    Upd. В следующий раз сделаю выбор в пользу магии :)

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

    А зачем Диниц? Нужно же просто проверить, что в каждой компоненте связности есть цикл.

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

    C/Div 1: Без потоков: Выкидываем все дизъюнкты из одной переменной. Дальше определяем любую переменную. Не более 1 дизъюнкта снова имеет одну переменную.

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

    Диниц легко завалился =) С паросочетаниями сложнее, Куна и Куна с жадником завалили, а реализация от бурундука на таких графах работает за =)

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

2E/1C was quite interesting I know what I was supost to do but I didn't have time to implement it, stil I liked that problem. Can't wait to see the editorial :)

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

    Yeah basically the problem is equivalent to "Given a graph can you direct it's edges so that each node has an in degree at least one".

    You can always do that as long as the graph is not a tree. And if it isn't finding a cycle and then directing all edges outward from that cycle does the trick.

    But yeah I also ran out of time to implement this.

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

number_of_contests_with_only_D++ :(

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

НИКОГДА не стоит писать контест, находясь на отдыхе на море. Сначала под окнами закатили концерт, пришлось уходить в коридор. Там, разумеется, никаких условий типа стола, но фиг бы с ним. А под конец еще и свет вырубили, разумеется с вайфаем вместе.

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

    таже фигня. Лежа на кровати в духоте. За окном играет местная музыка, и кошка орет.

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

So Cool. Congratulations to the winners.

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

And is this be standard from now on. New round every Saturday?

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

I got TL on the 6th pretest (Div. 2 C), and that in 2 minutes before closing... I... I could solve it... Arghh!

Anyway, it was a great round!

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

    Me too, but it seems that there's a O(n) aproach, so we couldn't solve it actually hahahaha

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

Why is system testing stuck at 75%?

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

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

Ну и привет фиолетовый, мда.

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

    "Тупая математика для дебилов!":DDD

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

      я сюда кодить прихожу, математики мне на матане хватает

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

    Компания занимается алготрейдингом, в нашей работе много математики.

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

      Ума не приложу, как задача А могла возникнуть в разработке какого-то из алгоритмов (сейчас прочитал Е и недоумеваю еще больше). Кстати, не включать в претесты лонг лонг довольно-таки некрасиво.

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

        Межнар по математике недоволен тем, что в контесте много математики. So confusing :(

        В A были претесты на long long, например 6-й.

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

          Прощу прощения, если задел чувства кого-то из авторов, просто неприятно в очередной раз заканчивать контест с 0 - 1 задачами из-за переполнения int.

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

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

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

Идея по E:

Факторизуем все числа. Если ответ существует, то для каждого простого в нём выполняется или привычнее: , где gi — степень, с которой простое входит в ответ, ai — степень, с которой входит в i-ое a и bi — в i-ое b соответственно. Таким образом для каждого простого имеем набор остатков по различным модулям из чего по КТО можно восстановить (модули не взаимнопростые, это решается тем, что рассматриваются дополнительно остатки по всем числам вида pk, где p простые, на которые делятся bi) остаток от деления на их НОК, он же минимальная возможная степень, с которой данное простое войдёт в ответ. Возможно, к этой степени прийдется добавить НОК несколько раз, чтобы он был  ≥  наименьшего из ai. Если для какого-то из чисел bi равно нулю, тогда ответ получается однозначно и его нужно просто проверить отдельно.

Ок или не очень?

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

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

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

      А что насчёт такого решения:

      Факторизуем все числа. Заметим, что в каждой геометрической прогрессии участвует немного простых(около 20 вроде бы), а так же что если множества простых для 2 прогрессий не совпадают, то решения нет. Теперь превратим каждую геометрическую прогрессию в набор арифметических. Отбросим более-менее очевидный случай 1 простого(правильно ли я понимаю, что большинство решений на нём падало?:)). Рассмотрим каждую прогрессию, как прямую в не более чем 20-мерном пространстве, если среди них есть 2 не параллельных, то пересечём их(или скажем, что решения нет) и проверим, что точка их пересечения принадлежит всем прогрессиям. Случай всех параллельных по сути эквивалентен случаю 1 простого — там нужно проверить, что сколько-то арифметических прогрессий имеют общую точку.

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

        Похоже на правду, правда там будет пара нюансов в реализации

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

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

      Где теперь fail? :)

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

Is it possible to change something in code after the contest has finished if it is only 1 operator , I mean switch = and <= ?

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

    No.

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

    yep change it and also you can submit it in practice :D

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

    Why not? Every one can. But really do you think it will be judged again?

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

    You can submit in practice after the grading finishes, but it will not affect how you performed during the competition.

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

    Sure, why not? You are allowed to change up to 10 letters in your solution after the contest, so remember that your variable names should be short, because that way you will be able to do more changes.

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

      haha :P

      Some contest allow minor changes like that , that's why I asked

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

        "Some contest allow minor changes like that" — yyyy o_0. Can you give me an example of at least one :P?

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

Мир сейчас тежол... Нафига такие сложные преколы придумывать...

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

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

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

Thanks for preaparing this great round, also thanks for t-shirt :D

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

Я одна поняла, что в задаче Div1 C все переменные должны быть использованы? Хорошо было бы уточнить это в условии.

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

from 25 to 1300, such is life in codeforces.

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

Как поднять свой уровень математики? =)

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

Such a sadness that nice Egor solution for problem D had minor bug :(

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

Двое первых из div2 решили лучше, чем двухсотый из div1. И один из них явно не фейк. Может футболку?

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

    .. и может ну нафиг эти разделения, если победитель из DIV2 рвет половину участников DIV1? ))

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

The contest was great !
Really hope that Round 318 will also give 200 T-shirts.

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

typically how long does it take before the rating changes? it was a great (hard) contest! :P

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

could any body please say me what is the calculating way for first contesters?

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

А фуршет сегодня? Там чет никого нет :-(

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

I think the problem statement for Div 1 C is unclear. In the problem statement it is written

We know that each variable occurs in at most two clauses (with negation and without negation in total)

Therefore, I thought that when a variable appears twice, the variable and its negation will both appear. Fortunately, there is test case 3 that shows that this is not true, but I did not have enough time to update my solution when I realized that.

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

    two in total means 0+2 and 1+1 and 2+0 , no ambiguity in that

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

    I don't see how that can be understood like this. Moreover you have "at most" which suggests that sometimes it can be one (or maybe even zero?), so there will be no place for variable and its negation at one time.

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

      Yes I know that there can be zero or one of the variable. What I meant is that the addition (with negation and without negation in total) sounded to me like we can get any subset of the set

      {negation, without negation}

      and thus in this case {negation, negation} is not possible.

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

Just a wrong character on code of A, and using 109 as inf on code of B but answer can be 2 * 109. Why I can't learn anything? :(

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

Late for the contest for 30 minutes, still got the T-shirt

image host

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

what about editorial??

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

Screencast

If you wouldn't shed tear when I type long[] allCumulUpds = new long[n + 1]; instead of m + 1 you have no soul

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

    Authors have soul, I am sure. I remember Bambi’s Mother Dies, Mufasa Dies, and so on when we watched this bug realtime in your submission.

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

      What does it mean to watch a submission realtime if you are author of a contest?

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

        Authors can open any solution during the contest. Also avaliable results at final testset.

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

    I noted that in this problem n denotes number of edges and m number of vertices, what will lead to inevitable errors, so I declared them as "cl" and "var" what makes it much harder to misuse them. Second technique I use is to always declare arrays of sizes of sufficient constants, here 3e5+5. Any of those two things will prevent you from making this bug :).

    EDIT: Heh, it seems that I messed up problems ^^. First remark is no longer relevant, however I guess second still stays.

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

      But 2nd technique may lead to other bugs, like Petr described in one of his recent weekly reports

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

        Hmmm, yeah, I guess you're sufficiently experienced to be acknowledged with both technique of making array of a 'just right size' and technique of making it big beforehand : D. Hence, my comment was probably anything new to you :P. However I use it like this for almost all my coding life and I don't remember any case when it caused a bug. Orrr maybe, concluding from what Petr has written it may prevent us from noting some bugs rather than cause them — I guess there is some tradeoff (pretty much like always). However I am a guy really prone to mistakes you did this time, so I will stick to my method.

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

    What tool do you use to parse contest problems ? Is there any github repo ?

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

Aha ..T-shirt! It's my first time to receive gift from Codeforces.. Here is my question. When will the T-shirt be sent? I can't wait to wear the lovely T-shirt!

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

Can someone provide an editorial? Thanks

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

    As always you may ask specific questions in comments. Now part of tutorial is published

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

    With respect to C I would be very interested in a discussion of how to implement the problem well specifically the part of finding the cycle in the component of the graph and then directing all the edges.

    If one attempts to find the cycle with a DFS one processes nodes until an edge is found between the node we are currently processing and a node we visited earlier.

    It is very unclear to me how to write the recursive function so that once we find such a cycle we can exit the recursion and along the way store the cycle in some sensible way.

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

      What I do for this is maintain a DSU while adding edges, and then when an edge is found connecting two vertices in the same set, we know there exists a cycle from one vertex on this edge.

      Then, we can run findcyc() from such a vertex, keeping the current dfs stack, until it reaches the starting vertex again — which it must due to the earlier argument. Thus, our cycle is isolated. Another nice thing here is that we can direct the edges along the cycle in findcyc() itself.

      Next we dfs() from every node on the cycle to direct the edges. 12656691

      Any other approaches?

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

        Come to think of it with the approach you describe (which I think is the nicest one) you don't need to find the cycle and then separately perform DFSs at all.

        If you start the DFS from the node on the cycle you can simply direct all the edges (that haven't been directed yet) away from the current vertex. This way every vertex has an edge pointing to it (the one that caused them to be thrown on the "stack") and eventually some node also has an edge to the starting node.

        So you only need one DFS per component assuming you can start with a node on the cycle.

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

      Not really proud of that code, but maybe you can get an idea how to do that by dfs: http://codeforces.me/contest/571/submission/12659401

      Condition on finding cycle is

      if (vis2[nei] && e != wh_var) {
      

      that means, I have visited that neighbour earlier and I'm not looking at the edge I used to be in current vertex.

      My dfs returns int. "If dfs returns nonzero value than cycle exists and returned vertex lies on a cycle and I have already assigned logical value to it". Whenever recursive call returns nonzero I stop executing and pass that value higher.

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

      You may also appreciate version with exceptions http://codeforces.me/contest/571/submission/12667656 :P. Finding a cycle can hardly be called 'exception', but exceptions can help you unwind stack of function calls without passing intermediate values.

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

      This is my solution: (I use outgoing edge instead of incoming edge) 1.Keep removing vertices with degree 1, and assign its only edge to it.

      2.Now there are only vertices with degree>=2. Find a vertex which has no outgoing edge. Starting from this vertex, find an unused edge and pass through this edge. Now we find an outgoing edge for this vertex. Keep doing this to the vertex on the other side of previous edge until a vertex which already has an outgoing edge is reached. It is guarenteed that we can always "go out" from a vertex with no outgoing edge because there are at least two edges connected to it.

      3.If there are still vertices which has no outgoing edge, do step2 again. Otherwise, orient all unused edges arbitrarily.

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

P.P.S. Top-20 div2 participants will be awarded t-shirts.

So genius that say this after contest :D

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

    Guys looked at the results and understood that participants from div2 earned T-shirts too, cause solved many problems. Why not?

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

    And now in next contest we'll see div1 guys playing with fakes in div2, hoping for such P.P.S. once again :)

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

      Add simple rule that he/she participated minimum 10 contest

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

        O_o

        So new users can't join the contests???

        Bad idea at all...

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

          Usually who win div2 — are div1 users. New user can't win contest or get top-20 in one contest.

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

            They can if they have done competitive programming in other places like icpc or tc.

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

            Ermm, having reached 3rd place in div 2 on my first contest, I beg to differ. And if you look at the standings, there are 4 more unrated people in the top 20.

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

First codeforces Tshirt :)

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

always getting wrong answer on 10th test case.iam unable to figure out .can anyone please help me :) .the link for the submission (http://codeforces.me/contest/572/submission/12670760)

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

    10th test was about wrong S and B priorities. You should write out B with bigger price and C with lower price.

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

That P.P.S made my day... :3 :D !!! Thanks all... !!!!

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

Было бы хорошо, если бы всегда нерейтинговые топ20 див2 получали по футболке от организаторов.

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

"С этого раунда на CF начинается серия thanks-раундов". Такой вопросик: а сколько их будет?

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

    Если предположить что 10000$ = 1 thanks round -> 27498$ / 10000$ = 2 rounds

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

    Вроде бы было 5-6 донатов на 1000$, то есть примерно столько. Но когда я прочитал "В вашу честь будет проведён раунд", я думал, что готовить его будет CF, а не компания-спонсор.

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

Just asking out of curiosity, did you consider using the new dynamic scoring system with 250 points gaps?

If you did, what was the reason behind choosing the standard scoring system instead?

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

    In short, all of us do not like the dynamic system, so we have not even considered it =)

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

      Why? So far, according to my contest experience, there were situations that dynamic scoring would have given more appropriate scores rather than standard but have not seen the same thing for the opposite. The only problem that dynamic scoring might cause was certain formulas that can lead to different points just because of 1 submission, but now it's only 250 points which is fairly good I think. For instance, it could have fixed the point distribution in this contest too, esspecialy for A-B and C-D.

      I've no doubt that all scoring systems common feature is fairness as far as it's same for all the contestants. But it would not hurt to make things better, right?

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

        Contests are supposed to be fun and dynamic scoring makes them less fun for me since its stressful not knowing how much the problems are worth.

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

          Well for me, it's more stressful when you do not know if the problem you are working on worth it's points.

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

            Then why do you gamble by skipping problem A, B and C? Usually A gives the most score per effort, then B, then C, then D and lastly E, so doing them in any other order is a risky gamble.

            Edit: While on the other hand with dynamic scoring the effort per problem ratio can be all over the place, usually A gives the least score per effort in those contests meaning that you must try to game the system instead of just focusing on solving problems.

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

              Because solving just A and B is boring and I want to give more time to harder and more interesting ones. If I would have started from A and B, there would be no time for D at all. The question is if you have the power to lead all of the contestants(by setting scores) would you encourage harder problems or not?

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

                Since they can set the scores however they want they obviously want the easier problems to be worth it, if they wanted the harder problems to be worth more they wouldn't set A and B to be 750 and 1250.

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

    Oh, you're the first person I see which doesn't hate dynamic score :P. I like to know what is the value of a problem beforehand. Dynamic scoring often can lead to weird strategies like skipping A and B, because they will be worth 250 and 500 pts or sth like that. What matters is also strategy, not only problem solving skill and you have to admit that choosing D as only problem to solve was not best choice =). I guess that probably it was twice that hard to solve D than ABC combined, so what you did was probably harder than what I did, but my place was significantly better :P.

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

      I like dynamic scoring too, and I believe it would be more fair if it was applied for this contest , because how can a problem which is solved the most(problem B) have almost the same points as the problem solved by few people(problem C)!!

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

        Haha, that said just after stating that C was far easier than B http://codeforces.me/blog/entry/19863?#comment-247365 XDDD

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

          first problem I tried during the contest was B , but I couldn't solve it ,I thought it's harder than usual div1 B problems, so I moved to C , the idea came to me very quickly but it took me some time to code it, after finishing I saw that B was solved by a lot of contestants even more than A , and C is solved by low number of contestants so I decided to give up.

          I posted that comment immediately after the contest finished I was trying to express my surprise of number of people who solved B , I didn't know that I'm only missing an observation to solve B , it wasn't that hard as I thought.

          in the end, a lot people solved B and that's what matters so it should not have that much of points

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

            Just 329 people solved B, it was way harder than your average B problem. Also I really dislike contests where the easiest problem is too hard since then lots of people chickens out and it gets hard to gain rating.

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

Разбор будет?

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

    Зачем? Задачи вроде простые.

    P.S. В самом низу анонса разбор.

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

      Возможная причина №1: Для человека это не такие простые задачи
      Возможная причина №2: Человеку интересно сравнить подходы решений

      P.S. Всегда ваш Капитан

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

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

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

just a friendly reminder, it's analysis not analisys (last link of the blog)

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

Is it normal that I got no message, e-mail or anything regarding the T-shirt? (I got 3rd in div 2.) I added my address details to my profile the day after the contest. This was my first time competing so I'm not really sure how things work around here..

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

    Only for Top 200 Div.1 users.

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

      At the end of the post, added after the contest ended: "P.P.S. Top-20 div2 participants will be awarded t-shirts."

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

When will the T-shirts be sent?

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

Will the t-shirts be sent to other countries like China?

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

I still haven't received my T-shirt. Is there any information on when they will arrive (in the Netherlands)?

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

I still haven't received my T-shirt. Will it still be send?

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

Finally, just received my T-shirt today! Thank you Aim Fund, Thank you MikeMirzayanov :D