Блог пользователя marat.snowbear

Автор marat.snowbear, 10 лет назад, перевод, По-русски

Добрый день Codeforces! Рад пригласить всех к участию в Codeforces Round #269 для второго дивизиона, который состоится в эту пятницу, 26-го сентября. Как обычно программисты первого дивизиона приглашаются поучаствовать неофициально (читай "за респект"), от своего имени очень прошу первый дивизион участвовать.

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

Это мой первый раунд, так что я представлюсь. Мне 27 лет, уже лет 7 работаю программистом, но вещами типа ACM/ICPC не занимался и открыл их для себя относительно недавно. Пару лет назад узнал словосочетание "dynamic programming" с курса на Coursera и чуть позже открыл для себя Codeforces, с тех пор я пропадаю тут. Я родился и вырос в Санкт-Петербурге, прожил там до 24-х лет. А потом женился, и мы переехали в Киев. Киеву и теперь принадлежит наше сердце, когда-нибудь мы туда вернемся.

Надеюсь, что набор задач в этом раунде будет для вас интересным и в меру разнообразным. А я пока хотел бы представить героев задач. Ими будут три животных из Санкт-Петербургского и Киевского зоопарков. Конкретно это Меньшиков и Услада — белые медведи, символы Санкт-Петербургского зоопарка. Это мои любимые животные в Питерском зоопарке, можете поучиться у них лунной походке. Их третьим товарищем будет слоник Хорас из Киевского зоопарка. Я не в курсе, какие танцы он любит, но вообще он показался нам очень милым и дружелюбным слоном. Мне всегда нравились белые медведи и слоны (как и множество других животных), наконец у меня будет свой раунд про них! Рекомендую запомнить, кого как зовут, так как в условиях задач имена и названия животных используются попеременно. Эта троица выступает за дружбу между странами, я надеюсь, что вы им поможете и поддержите их.

Со своей стороны хотел бы поблагодарить:

  • MikeMirzayanov и всю команду Codeforces за этот сайт,

  • Gerald за помощь с задачами,

  • Марию Белову aka Delinur за перевод условий,

  • мою жену Таню за ее бесконечную поддержку во всем, этого раунда бы не было без нее.

Википедия просила напомнить вам, что день, когда состоится этот раунд, будет 269-м днем года (по крайней мере в Московском и множестве соседних часовых поясов) — отличное совпадение с номером раунда. Это Gerald мастерски поставил раунд в расписание.

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

Еще хотел бы добавить: gojira поступил нечестно! В своем объявлении раунда он сказал, что ему от Sammarize переходит титул самого старого автора задач, но он не сказал, каков же был его возраст на тот момент. Так что я не знаю, достанется мне этот титул или нет. В студию вызывается gojira для ответа на этот вопрос!

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

P.S.: Как обычно, разбалловка — дело последних пяти минут перед раундом.

новость раз: разбалловка будет нестандартная — 500, 1000, 2000, 2000, 2500


Всем огромное спасибо за раунд, это было круто! Надеюсь и вам понравилось. Мои поздравления победителям. worse сегодня не участвовал, поэтому борьба была жаркой с обеих сторон таблицы. Меньшиков и Услада уже пошли обновлять рейтинги, а Хорас пишет разбор, сегодня ночью обещает быть.

Я понял и учел допущенные с моей стороны ошибки, но еще раз прошу вас дать знать ваше мнение о раунде/условиях/мутности задач/картинках. Более 5К зарегистрированных — это фантастика, спасибо!

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

Еще раз спасибо,
Увидимся на следующих раундах,
Марат.

Статистика от DmitriyH
Разбор задач

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

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

know the secret every non-red coder wants to know — in order to become red you need to solve at least 1513 problems on this site.

tourist has solved only 590 problems ?!

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

    Oh, come on, leave a space for a joke in this post!

    Otherwise I should probably remove 'on this site', I bet he solved WAY MORE than this number of problems.

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

    I think, marat.snowbear talked about the coder like those, who has just started their competitive programming life. If you tell about tourist, he started his journey in codeforces in 2009. But before it, he achieved gold medal in 2007, 2008 and silver medal in 2006 in IOI.
    One of his famous remarks, made in an interview after the IOI 2009, was "I am no genius. I am simply good at it." (I have known it from wiki). So actually he was simply good even before he started in this site. :)

    But my question to marat.snowbear is, why it is 1513 exactly ?? :P
    What is about 1512 ??? :P

    At first, I thought reading full blog will be boring... :P
    But after reading full blog, it has given me some pleasure. :)
    You have made me known about Saint Petersburg zoo. And nice to see you as a good husband. :)

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

      1513 was the number of problems I solved in CF archive when I became red for a couple of rounds. I remember I saved that number to have an answer to the questions like 'how much do I need to work to become red' which are raised occasionally here in blogs :-)

      You are correct this number refers to those starting this kind programming, like me. Those who started in school or university and if they target for IOI or ACM they probably have trainings and lessons where they solve a lot more problems, it makes it hard to estimate the number of problems they solved in total. As I mentioned in the post I wasn't into ACM in the university, so the only problems I solved are those in online judges. And around 90% of the problems I solved are from CF, so the number 1513 is very close to the total number of problems solved by me by the time I became red.

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

        Where can I see the number of problems I have solved?

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

        BTW, getting 1513 solved problems on CF is pretty easy, because we have enormous number of very easy problems here; so i think that someone may understand your words literally, set this number as a goal, and then he'll be disappointed when after solving 1513 easy problems he will be just orange or even violet:)

        Thanks for your story, i often receive similar questions, now i'll have one more example to show:)

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

          Well, that was an irony and there is always somebody who doesn't get it. It won't be an irony otherwise.

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

          Since you're the leader now in this ranking with big advantage above the second guy (3205 vs 1933) I suppose that majority of those problems you've solved are very easy ones. Why have you done that? You're red coder and it doesn't seem that you really needed that. Do you find challenging solving As and Bs from Div2 or some regionals of nowhere :P?

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

            I, for example, solve div2 A/B just to have green spaces instead of blue ones. After all, checking colour (green/blue/white) is faster than checking the written division number :D

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

              Lol. "Codeforces grinders" :P. People who have time for filling that list with green color — you are happy people, I say :P. Though maybe I will have more time for solving problems if I would cut on permanent spamming in comments :P.

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

            First of all, there are lot of contests where you have to solve very easy problems very fast. Personal contests like CodeForces, TopCoder, SNxS, 101 Hack, CodeChef Cook-off and so on. At TopCoder solving only first problem with good speed is enough to become red. And often it is also true even for team contests. At SEERC2013 you had to solve 7 problems to qualify for World Finals (well, there was no need to do it fast — all universities with 7+ problems qualified), and in online version of this contest SPbSU4 solved these 7 tasks in ~70 minutes:)

            Among contests which i did in CF gyms most are displayed blue, not green. I mean — i still have problems to do in most of them:)

            And when i am looking at some contest that i did year ago with results like 9/12, and then take a look at problemset — i often think "what a hell, why i did not managed to solve all 12?" I would say "i am red because i did all these problems", rather than "i did all these problems because i am red and they are easy". I was not red year or two ago:)

            BTW, you may assume that i like coding, or like that feelings when you have AC-ed new problem, or simply wanted to become top-1 in problemset, or was focused on preparing for "easy contests with easy problems", or anything else like that. None of mentioned is true, but i don't want to discuss my reasons and motivation here, i don't think that it is proper place for such things.

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

    Please Ignore.

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

There are only 8 coders who have finished 1513 problems, in spite of 5 vjudge robots... But there are 16 IGMs and 467 GMs......BTW, the number of rank 16 in problem-solver is 1408, and the 483th is 461~

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

It seems to be the longest CF Round announcing post I have ever seen.

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

    But it's one of the most interesting posts I have ever seen. I even tried to remember the heroes of this contest :D

    I think that the author took the contest very seriously, let's wait for the problems :)

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

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

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

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

Так вот почему раунд перенесли с четверга на пятницу.

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

P.S.: Как обычно, разбалловка — дело последних пяти минут перед раундом.

Первый раз слышу)

P.S. Было интересно читать анонс написанный с душой.

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

never into ACM/ICPC and stuff like that before
ME TOO
It Will Be A Great Inspiration For Me

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

What a great introduction! All the best for your first round marat.snowbear :)

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

Здесь указано что gojira родился в 1988 году, сейчас ему не больше 26. http://ws.kh.ua/media/sbornik/Sbornik2010.pdf — стр.123. Вы самый старый автор задач, мои поздравления!

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

    вы забыли про Майка)

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

      Михаил Мирзаянов лучше чем автор он создатель. Мы же оранжевых не называем серыми.

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

Impressive intro. I'm looking forward to your round

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

I thought I would skip the round(as it is unrated for me) and watch some movie or something. But after reading your blog post, I think I will take part :)

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

    There is a mem in Russian saying that "while you're sleeping your opponents are levelling up" (originally it was about some online game where you need to spend a lot of time to level up further). Same saying works for watching movies ;-)

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

    So, how was the movie?

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

      I had to go out and I came 1 hour into the contest, but then I realised that I didn't register, that is actually stupid of me, but I tried the problems and was watching the standings, the problems are indeed very interesting, hope you set more contests in the future.

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

Glad to see a different announcement post for a change :-D.

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

Hope that the problem statements won't be long as the blog entry! :D

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

"know the secret every non-red coder wants to know — in order to become red you need to solve at least 1513 problems on this site."
So, If I participate in 1513 div2 round and in all of them I solve problem A, in the next round I'll be a red coder? Great! :-)

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

    If you really understand it from that line, then wait until 1513 rounds in codeforces. :O
    It has taken 5 years to complete 268 rounds. From normal mathematics, you have to wait more than (28-5)=23 years more !!! Hope you will be RED after that time !!!

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

hahaha funny intro for your Round, I guess I'll be having fun with problems' statements too. Won't miss this one.

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

such an unusual cool announcement ;)

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

Interesting and well written post.

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

Considering how you got to CodeForces and achieved so much here, I just thought you are the perfect person to ask this question:

Does the experience in competitive programming change you as a programmer?

It'll be awesome if you could explain why/why not! Thank you!

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

    Well, I think the answer here might be unclear a bit but here it goes. Yes, I think this experience changed me as a programmer, there is no way it won't affect me taking into account the total time I spent on this site solving problems and learning new algorithms and data structures. But the practical outcome of this change is not that huge, might be not even noticeable to other people. In result if you look from practical point of view only then all I got is 5-10 T-shirts and some better chances on Google interview. I have never had a job which require algorithms/data structures skills, at least not of orange/violet level. I also became a bit better in some other programming areas, like debugging things in mind for example, this is helpful when doing code review. But all of these in total is not that much taking the time into account again.

    So I would say it's a bit different, my only point of doing this was always the fun. I was always a fan of similar problem-solving sites since my high-school years. I started on sql-ex where you can solve similar problems in SQL, then I moved to project euler with its focus on maths, now I'm here. I would say that I'm here because I am already the way I am, so this site cannot change me much, neither as a person nor as a programmer.

    My opinion is that this site for me is for fun only, if you want to learn data structures or algorithms or become better in any other programming area then there other more effective ways of doing that, at least unless you're looking for some red-level skills.

    Oh, and I have just remembered one more thing where this site changed me as a programmer. After spending an year on this site I became completely bored on my job, so now I'm unemployed for the third month so far. Even though I receive around 15-20 propositions on LinkedIn per month, I'm not interested in those, so I stay here. Stay aware of this path!

    Hope this helps and doesn't sound too depressing :-) Marat.

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

      Thank you very much for your reply, Marat! I really appreciate that!

      It's really interesting to know programmer's perspective on competitive programming, since I'm a math major and I only write code for online judge.

      Too bad you are unemployed. I hope you'll find job you love soon!

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

      Hue hue hue I feel like my path of going to study physics and keeping programming only competitive and only hobby is a total win, now.

      I might still try programming-related work to get moar varied skillz, but I can't imagine sticking with it for long.

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

According to your performance I thought you are a student who's started training harder lately to get to IOI/ICPC. And now it looks pretty inspiring that you find time for all these trainings and contests at your age. orz

Recently I don't take part in div2 rounds, but going to do in yours. Good luck!

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

Longest welcome not ever :)

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

Все детство мечтал чтобы меня Якубович в студию вызвал, а тут такое :o

Признаюсь, я не дорос, титул уступаю =)

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

Hi, please could you confirm that the solutions will work with both Java 7 and Java 8? Because many solutions in contest 267 that used Java 7 got a MLE but passed with Java 8. I think that is a bit unfair. Looking forward to participate! (if I can)

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

Just Ignore ME please!!!

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

    Почему столько дизлайков я ж тут новый, ничего не знал...

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

      ПОЖАЛУЙСТА если раздражаю хотя бы проигнорьте

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

        А авторам большое спасибо за контест и успехов в этом деле))

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

    what I've done to recieve so many dislikes?

    Что я такого сделал чтоб получить столько минусов?

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

    Please can you give me +? Because of -28(( Help me please

    пожалуйста помогите-поставьте плюсы а то рейтинг минус уже:(( АУУУУУ

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

Most intresting post that I ever seen :D
Special thanks to marat.snowbear ...

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

I think it will be good contest for us.... thanks to marat.snowbear.... GOOD CONTEST!!!)))

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

5000 contestants have registered!!

EDIT: The final number is 5093. Hasn't this broken all existing records on Codeforces?

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

Contest ended))

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

в систестах Д есть антихештест?))) ну или кто ломал им?

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

    Там же алфавит настолько большой, что любые хеши завалятся.

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

      ну алфавит размера 200000. ну пусть падают ок. щас ждем массовые падения хешей.

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

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

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

    Был 1 мой такой взлом. (Кажется, сейчас это 25й тест)

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

    В моей комнате упало решение на систестах — 7966736

    И давно пора шрифт поменять в окне взлома, один участник перехитрил меня, сменив основание хеша с 131 на 113ll, что я, разумеется, принял за 11311 :( 7972894

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

How to solve D ?

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

    Form two arrays of difference between height of current tower and the previous one. Now search small array (elephant's towers) in the big one (bears' towers) like a substring in text. Special case to consider is that if w = 1.

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

    For special case w = 1, output n.

    Now observe that we can take the differences of consecutive elements, so searching for elephants is essentially finding the difference-elephant in the difference-wall. For example, if the wall is [3, 4, 5, 6, 1, 2, 3] and the elephant is [2, 3, 4], we can compute that the difference-wall is [1, 1, 1,  - 5, 1, 1] and the difference-elephant is [1, 1], so there are three such occurrences. Indeed, the elephant appears on subsequence a1, a2, a3 (after raising by 1 to [3, 4, 5]), on subsequence a2, a3, a4 (after raising by 2 to [4, 5, 6]), and on subsequence a5, a6, a7 (after lowering by 1 to [1, 2, 3]).

    Now this is essentially searching substring in a string, only with large alphabet (which doesn't matter). We use Knuth-Morris-Pratt algorithm or something like that to find them in O(n + w) time instead of O(nw).

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

    I think it can be solved taking the diferences between walls and then string matching(kmp for example) but I got wrong answer on pretest 2.

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

first is Hack.Me last is yasinkkaya

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

I have came up to solution of problem D ib five minutes. Today we had a control test on a programming lesson and I had to write a z-function. I just copypasted a code and sent it. TL 4. After some time I improved my code and it got "past pretests". There were a mistake in a code of z-function which I wrote during the lesson. It seems, that mark won't be perfect:D

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

+1 to problem setter. Awesome set. My Solution to A got hacked. Hope to see you again :)

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

How to solve C?

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

    You can look my solution http://pastebin.com/V3jPNSjK

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

    Let's denote by Hi = the minimum number of card which should be available in order to build a castle of height i. We may find the exact formula, or calculate this number inductively (Hi = H(i-1) + 3i-1). Having this formula, we realize that the maximum height a castle can have is around sqrt(n). So we can iterate through all possible heights. In order to check whether or not we may build a castle of height i with exactly n sticks, we have 2 conditions:

    1) n >= Hi 2) (n-Hi) is divisible by 3

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

    For a floor with a rooms in it, there are b cards in it, that:

    b = 2a + (a - 1) = 3a - 1

    So, if we can build n cards into a house with k floors, following statement will take place:

    n = 3x - k, k + n = 3x

    where x is sum of k different summands. It can always be written as x = 1 + 2 + 3 + ... + (k - 1) + y, where y is some integer greater than (k - 1)

    When we know it, we can write solution: 7970170

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

    Observe that the number of cards in a floor is 2k + (k - 1) = 3k - 1 where k is the number of houses there. Thus the number of cards used will be . In other words, the number of floors and the value of n must add up to a multiple of 3 (namely ).

    Let there be f floors. Since we don't care about the number of houses on each floor, only that higher floors have less houses than lower floors, we might as well set the highest floor to have 1 house, the second highest 2, and so on until the second lowest, and put the rest of the houses at the bottom. In order for this to work, we want (3·1 - 1) + (3·2 - 1) + ... + (3·f - 1) ≤ n.

    Now we can use a simple algorithm or a more difficult algorithm.

    The first algorithm is simply to loop over the number of floors from 1. Note that is quadratic on f, so this has an upper bound somewhere around , quick enough for the constraints. As long as minH = (3·1 - 1) + (3·2 - 1) + ... + (3·f - 1) ≤ n, we check if ; in that case, increment the result, as f is a possible answer.

    Using the example, n = 13:

    • f = 1. We have minH = 2 ≤ 13 = n, so we check if ...nope, since .
    • f = 2. We have minH = 2 + 5 = 7 ≤ 13 = n, so we check if ...yes, it is, . So we increment the result.
    • f = 3. We have minH = 2 + 5 + 8 = 15 > 13 = n, so we don't have enough cards for three floors, much less for more floors. So we break out from the loop and return 1 as our count.

    The second algorithm relies on another observation. Note that we want to find the highest value of f where . We manipulate this algebraically:

    3f2 + f ≤ 2n

    (6f + 1)2 = 36f2 + 12f + 1 ≤ 24n + 1

    Thus, if we can make the square root with sufficient precision, we can compute the largest integer value of f; simply do .

    Now, if , we count the floors 1, 4, 7, .... If , we count the floors 2, 5, 8, .... If , we count the floors 3, 6, 9, .... So if we add to the floors, we always end up counting the floors 3, 6, 9, ..., which is simply . So given this, the final result is simply .

    (EDIT: Codeforces is under heavy load ok. Why doesn't \pmod exist?)

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

E was harder than usual. Anyway, I liked the round and its heroes. A and B were about coding a simple idea in the simplest way while C and D required some creativity and I liked them both.

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

    Yeah, I underestimated E, my fault. Could have a problem for D for the first div :-)

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

      How to solve it?

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

        DSU + sweep line + one optimization to make it fast enough, would you mind waiting for the tutorial? I'll publish it a bit later today.

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

        Is this a valid solution to E? 1. Making graph.. 2. Dividing it onto connected components 3. Negating all the weights of edges and finding MST for every connected component(Kruskal) 4. Find the maximum of the weights in that MST 5. Answer is sum of all edges-4.

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

          Looks like you have n^2 vertices in your graph (if each vertical line intersects with each horizontal)...

          Or your first part of solution is really hard to do.

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

            Well yeah, didn't noticed that. Maybe something could be done to merge intersecting segments but doubt, even if it could be done it overflows my coding skill. Thanks anyway

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

Very Nice problem , Its really SAD when you get the idea of D at last 5 minutes , and nothing to do but stare at the problem statement because there is no TIME to code .

and even More painful , seeing your idea was correct in the forum -_-

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

    It's even sadder when you use a wrong formula for Problem C and realize the correct one when don't have enough time to correct it:(

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

      It's even sadder when you haven't solved even B because you forgot to put "YES\n" into your answer...

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

        that should give WA in the first case !!

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

          Yes, and I couldn't understand what is wrong it all the remained 1,5 hours. C was too difficult for me, so I haven't even tried to solve it. So it's my destiny to be gray, as it seems :)

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

    You have to be really new here if you consider such experience as very painful ;).

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

Please put + to my comment i have many — please help me

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

How to solve B?

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

    At first, sort the input array. You just need to permute the array 3 times that the three permutation is same. If it is possible(if two or more pair have the same value or any of three or more numbers are same) then print the value of index by their permutation, for example see the discussion which is written below the problem statement.Hope it will help. =D

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

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

Очень расстроила опечатка в моём коде, из-за которой не прошла первая задачка. Вот до чего доводит копипаст :(

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

great thanks 4 test with w = 1 in pretests in problem d

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

What a Interesting problem >> A :)

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

Hey, I don't understand why during judging my solution.. two of the solutions which passed pretests were skipped. As a result of which, my submissions show that I have solved only a single problem..?

Can some one please explain why this happened to me..?

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

    I don't want to be jerk but it seems like that you cheated. Style of coding is really different, so I think that someone gave you code, which would be skipped as it in your case.

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

It's realy sad if you submit problem B and WA after system testing :(
For what ???!!
FOR (i, 1, n+1) must be changed to FOR (i, 1, 2001)
I'm so sad now :(

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

"worse didn't take part in today's contest so the fight was tough on both sides of the table" :D

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

Does anybody know how to TL this solution — 7969881? Seems to be O(N^2), at least if find is linear, but seems to pass the tests by time.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    void create_test(){
    	cout << 200000 << ' ' << 100000 << endl;
    	for (int i = 0; i < 200000; ++i)
    		cout << 1000000000 << ' ';
    	for (int j = 0; j < 100000; ++j)
    		cout << 1000000000 << ' ';
    }
    

    This solution running more then 3 seconds on this test on my pc.

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

      But the solution running less 2 seconds on codeforces...

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

      It doesn't on CF though :-) Checked in Polygon — it takes 1934 ms. Have you tried running the same test but with ones instead of 1^9? It is there in tests (fourth test) and took 1668 ms in his submission.

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

This was my first CF contest and the problem set was VERY enjoyable. Nice mix of "easy implementation", "little harder implementation" and "thinking" problems.

Even though I missed the "easy implementation" problem A. :-)

Well done by first-time problem setter. Thank you.

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

Классный раунд, спасибо автору.

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

Мелочь конечно, в задаче A не указано, что входные числа целые, но все же в глаза бросилось.

А так, раунд понравился. Чувствуется, что работа была проделана большая и качественная! Спасибо за отличный раунд :)

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

    Ага, действительно мелочь по сравнению с неправильными ограничениями в Е :-)

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

работает.

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

I'd appreciate a nice answer. Can You please explain what's the point in making div.2 A task something with "corner" cases and things that you should think about? Shouldn't that be a task that is really straightforward, and tbh on this competition D was much more straightforward than A? Thanks in advance, enjoyed the contest. :-)

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

    What do you think is a corner case in A?

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

      Eh,maybe said it wrong, but again it's kinda not that easy/straightforward. Just my opinion, saw a lot purple/blue coders getting wa on it.

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

I got WA for my submission of B in the 7'th test case(for 2000 integers), but I am unable to view the full test case.

How can I get the full test case?

Submission here 7969957

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

    There is no way for you to see the full test. 7th test is simply 2000 random numbers. Maybe it's not the bug that failed your solution here but you seem to have an overflow when counting the number of possible permutations. You're multiplying them and they can easily become negative.

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

    Problem is in this cycle:

    for(it = M.begin(); it != M.end(); it++)
    	{
    		VI v = it->S;
    		perm_no = perm_no*1LL*SZ(v);
    	}
    

    perm_no can be easily as big as 21000. This does not fit in 64-bit integer type. But you can break from cycle, when perm_no >= 3:

    for(it = M.begin(); it != M.end(); it++)
    	{
    		VI v = it->S;
    		perm_no = perm_no*1LL*SZ(v);
                    if (perm_no >= 3)
                        break;
    	}
    

    This change makes solution AC: 7976891.

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

I'm Purple :o I'm not ready for Div1 yet...

What to do??

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

Only one person can solve problem E