Блог пользователя boleyn.su

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

Привет, Codeforces Round #221 начнется 24го декабря в 18:00 по москве. Раунд будет проводиться в обоих дивизионах.

Задачи готовили whd, oGhost и boleyn.su. Это наш первый раунд на Codeforces, и мы надеемся, что он будет весьма хорош.

Хочется поблагодарить Gerald и alpc104 за помощь в подготовке раунда, а также MikeMirzayanov за создание платформы, где все мы можем соревноваться и общаться.

Распределение баллов по задачам будет анонсировано перед началом контеста.

UPD1: Распределение баллов 500-1000-1500-2000-2500 для обоих дивизионов.

UPD2: Наши поздравления победителям! Также поздравляем с рождеством всех, кто празднует его сегодня!

Div 1:

1.Touma_Kazusa

2.al13n

3.rng_58

4.hmspmy077

5.uwi

Div 2:

1.bohuss

2.Tyg3R

3.xhsong

4.adamant

5.Kira96

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

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

Good luck

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

Hope the contest won't be like the last contest( Hard && Unrated ). Good luck to eveyone!!!

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

Good luck ... :)

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

Maybe people can already assume that every round announcement has some kind of grateful acknowledge to MikeMirzayanov, since it's becoming a bit boring to read that part every single time.

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

If this is the last round this year...

HAPPY NEW YEAR TO ALL :D

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

Why this blog isn't on the home page !?

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

Contest in Christmas Eve? And on top of that — at 18:00? Weird idea. I'm not familiar with Russian traditions, but in Poland at that time we usually gather with family around table and celebrate Christmas Eve :P. Other days will be better or at least earlier hours. Even though I will try to compete :P. In Poland it's not that bad hour, because it will be 15 :P.

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

    Pay attention to where the three round makers come from.

    They come from Renmin University of China

    The round will take place at 18:00 MSK means 22:00 CST.

    BTW, as a freshman,it's always hard for me to make a decision whether I should take part in a round start at 19:30 MSK or not , because if I do, I have to coding from 23:30 CST to 01:30 CST while my roommates are sleeping, which may bothers them.(In my school, a student should never stay outside domitory after 23:00)

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

    Christmas is not celebrated on 25th of December in Russia, see this wikipedia link. And even on 7th of January Christmas is not celebrated that widely comparing to how they celebrate it in Europe for example. In Russia people mostly celebrate New Year.

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

    The Orthodox calendar isn't affected by the Gregorian correction (not everywhere, though), so Christmas in Russia should be shifted to 13 days later. Still, 24th this late is not the best choice.

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

    You really are in no position to comment about "no-lifes" on my youtube videos if you plan on participating in a contest on 3pm-5pm Christmas Eve. ;)

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

      OK, you convinced me. Tomorrow at 3pm I'm going to watch your whole screencast :P.

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

      Yay, I participated and took in my opinion really good place — 38th :D!

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

Wow, three problem setters Chinese from RU! Look forward to it!

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

    In fact, RUC is short for Renmin University of China, while RU is not.

    By the way, I was born in Chongqing. It is good to see students from my hometown attending our contest. Good luck and have fun!

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

king base!time is good for chinese,thx for setter

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

Good time for chinese..

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

Люблю задачи от новых авторов)

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

Looking forward to it ! When the contest ends, it will be Christmas in China and we will have to go to school as usual ...

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

I love this contest!

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

Hope a better Contest than the previous one... That was not a Contest...

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

hope every contestant can have fun with the problem set :D

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

Желаю всем удачи на контесте!!

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

Have you changed the contest time or i need some sleep :) ?

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

Up-vote this comment if you can :P

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

    It is very hard. We can't. Sorry.

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

    Let me guess. After seeing some people in the last two contests, asking for downvote and getting them, you thought this would work!? If only it was that easy :p

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

Good Rate on Codeforces and Happy New Year))))

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

10 minutes before the contest and no score distribution published!

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

Just for Remember you said
The score distribution will be announced before the contest starts.

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

Я понять не могу, почему постоянно такая проблема — указать распределение баллов? Почему всегда это делается одновременно со стартом контеста, а то и позже? Кто мне объяснит?

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

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

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

      Лично я просто настраиваюсь. Не знаю как, но это помогает собраться с мыслями.

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

    Может быть, потому что Сережа настоятельно рекомендует прочесть условия ВСЕХ задач?

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

Power belt, I have late for contest and registration. WHY registration starts at late evening? Should it be possible to open registration 1,5 day before contest?

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

Merry Christmas and Happy Halloween (Note : OCT 31 = DEC 25 :D )

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

Maybe I have a chance to go to div1...thx...

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

Как решать С (div2)?

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

    Например вот так:

    1. Находим первых вхождения 1, 6, 8, 9 и перемещаем их так, чтобы они оказались в самом конце нашего числа. (Или просто удаляем из него)

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

    3. Считаем остаток от деления на 7 числа, составленного из первых n-4 цифры. Попутно выводим их.

    4. После этого какой-то (можно высчитать для каждого случая заранее, а можно перебрать за 4!, это не очень долго) комбинацией из чисел 1, 6, 8, 9 мы можем довести любое имеющееся число до делящегося на семь. Найдя нужную комбинацию, выводим её. Затем отдельно выводим выкинутые ранее лидирующие нули.

    Вроде бы должно работать...

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

      А почему при помощи этих цифр 1, 6, 8, 9 это можно сделать?

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

        можно проверить, что перестановки этих цифр дают все остатки от 0 до 6.

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

          Да. Это просто надо знать! Теория чисел. Круто мне нравиться!

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

            Минусы от того что вы все знаете теорию чисел? Молодцы. Это очень хорошо.

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

              Вообще было бы не плохо снабжать свои минусы или плюсы комментарием. Даже в обязательном порядке. Ну вот например на мое высказывание — хоть один комментарий за что минус. Очень интересно.

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

                Этого не надо знать. Можно взять и на компе (можно даже и вручную) сгенерировать все перестановки 1,6,8,9 и посмотреть остатки.

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

                Понятно все. Нет меня не трогают минусы. Скорее всего меня не уволят с работы за них. Не уйдет жена. И не обидятся оба мои сына (они еще ничего не понимают). Но все-таки хочется знать критерии постановки минусов.

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

                  Было бы клево под лайками и анти- лайками ставить подпись. Как в контакте. Чтобы обмениваться любезностями.

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

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

                  К этому посту примерно 200 комментов — мне что, к каждому лайку оставлять пояснение и аргументировать свою позицию?

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

                  Да наверное стоит к этому относится как просто к цифре с минусом и все. У меня вот нет математического образования и по образованию я борт — инженер. Мне просто нравиться программирование. Да и сейчас я работаю в этой сфере как уже 2 года. И действительно восхитился как не сложно решается эта задача. Ложки то нашлись а осадок остался.

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

                  Можно забыть про лидирующие нули, если поставить число, составленное из 1 6 8 9 в начало (тем самым, домножить его остаток от деления на 10^(n - 4)).

                  P.S А как давно это добавили?Ссылка на скрин

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

                  Целая простыня о том, как тебя волнуют, а потом о том, как не волнуют оценки к комментариям. Спрашивай и пиши коротко и по делу — будет меньше поводов получить минус за мысль «зачем я это читал».

                  p.s. «Круто мне нравитЬся» — многие ставят минус за ошибку.

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

nice contest!,but what is the algorithm to solve problem C DIV 2 or problem A DIV 1?

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

    C is pretty simple actually if you think of the reason why the setter used the digits 1,6,8,9. You can get all remainders when divided by 7 for some permutation of the digits 1,6,8,9. That is for every number x in {0,1,..6}, there exist a permutation of 1,6,8,9 such that when that permutation is divided by 7, it leaves a remainder of x. I think with this hint you might be able to complete the solution.

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

Will there be a tutorial published?

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

За какую сложность кто писал D? У меня O(Nlog2N), я отвечал в оффлайне, протаскивая вверх по дереву декартово дерево пар (количество, цвет) и приливая меньшее к большему.

UPD: Я забыл упомянуть, что я ещё и протаскиваю вверх обычный мап, в котором для каждого цвета держу его количество, а это ещё + O(Nlog2N).

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

    N^(3/2) * log(N)

    --Challenge me plz

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

    У меня тоже лог квадрат с разделяй и властвуй, но вместо декартова дерева — фенвик + хешмеп с количествами для каждого цвета

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

      Можно без фенвика, просто хранить рядом с мапой вектор ответов для всех k; при добавлении элемента он меняется только в одном месте.

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

        Как в одном месте? Пусть у тебя есть вершина, у которой два поддерева. В первом 101 вершина разных цветов, во втором 100 вершин одного цвета. Вот приливаешь ты второе поддерево к первому. Раньше у тебя вектор ответов выглядел как (101, 0, 0, ...), сейчас будет выглядеть как (101, 1, 1, 1, ...). Нет?

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

          Ну, можно же по одной добавлять вершины. И да, это дает n log решение, если мы верим в хеши :)

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

            Да, круто. Для этого надо, правда, ещё вверх вектор вершин из поддерева тянуть, то это уже ерунда.

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

              Не, можно проходить по той же мапе и добавлять по одному.

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

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

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

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

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

    Про столбцы ничего не написано:)

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

      Вот я перечитывал-перечитывал.....Глаз цепляется за большое-пребольшое определение подматрицы и, кажется, что в остальном невозможно ошибиться)

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

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

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

Yeah.. Div1 is too hard to me.. I'd better back to div2...

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

Saw few people use sort in problem B div 1. O(n*nlogn) should get TLE right? I went out of my way to use bucket sort to keep it O(n^2).

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

    Sorting? I'm kinda scared now. I didn't use sorting. At all.

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

    I didn't use sorting too, I think n^2*logn should TLE.

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

    5506448

    Sorting, no TLE =)

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

      Okay this is weird. I generally assume, 10^8 calculations take 1 second. So O(n*nlogn) is (5000*5000*12)/10^8 = 3 seconds. Time limit is 2 seconds. Since it didnt get TLE, I guess CF is a lot faster than I assumed. So how fast is it? I did the bucket sort for nothing :(

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

        It seems like the compile-time optimizations by GNU C++ are able to make up for it somehow.. Even though that some solutions that used sorting were either hacked or didn't pass the systest, so it's kind of tricky to guess whether a solution will pass or not just by looking at the source code.

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

    mine was O(n*nlogn) and it passed... :)

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

Is cin very fast on codeforces? I was surprised that cin solutions worked in B.

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

    At least it is fast enough with this: ios :: sync_with_stdio(false);

    I always use cin in CF and until now I haven't get a TLE by it.

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

    according to my testing, on GNU c++ 4.4 and above cin/cout work very fast and compareable to scanf/printf :p

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

    I think the reason is codeforces judges is really fast.

    At beginning, we do not want n^2logn solution pass, but failed to generate a testcase. I am really surprised by the speed of judge computers.

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

Problem Maximum Submatrix 2 is essentially exactly the same problem as http://www.ceoi2009.ro/tasks/logs.pdf :(

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

Need hints for problems C div 2 :( soon :D

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

    That problem looks very artificial to me, these numbers must have some magic.

    So I submit a crazy solution 5502926: until find a solution, do some random swaps, and if time out then output 0. And it passed system test.

    Seems it can't be no solution, but I don't know why. :)

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

      For every 0 ≤ r < 7 there is a permutation of {1,6,8,9} that (being read as a 4-digit number) yields remainder r when divided by 7. Choose the right one and append all the other digits to it.

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

        Even more than that, for every integer a, there exists a permutation of {1, 6, 8, 9} that is appended to a and makes the result number divisible by 7. :)

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

      You can rearrange 1,6,8,9 to form all mods from 0 to 6 -- so just order the rest of the numbers in any order, then output the correct permutation: http://codeforces.me/contest/375/submission/5507138

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

      For each 0<=r<7, there exists a permutation of {1,6,8,9} as (r*10 000 + permutation) % 7 = 0
      So, you choose a random order for the initial number (just conserve one 1, one 6, one 8, one 9 and count number of zeros), then you calculate the rest of this number, and you choose the valid permutation of {1,6,8,9}.
      You can then add as many 0 as you want lastly.

      sample: 123456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869
      (and with zeros:) 1230000456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869 -> result = 2345718690000

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

Если это сообщение наберёт пять плюсов, я поною по поводу контеста. Збань, привет.

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

Самый удачный для меня контест! Первый раз удалось решить 4 задачи за контест. :)

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

Very interesting problems, and no complex algorithm. LIKE it:) [Although i have solved a little tests] Hope u can papare more contests in the future!!

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

Are u kidding? N log^2 N solutions in D that use dat slow c++ map pass with a great handicap. Well, maybe I'm unfair cause I spent alot of time doing N log N solution, but I bet on weak tests.

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

    100000 * 18 * 18 < 100*10^6

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

      That's too rude, u don't assume that map is a redblack tree and we keep pairs in it.

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

        One of logs, which going from merge is very small. Also maps are not very big mostly. Probably this two compensate.

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

          There are even O(n * sqrt n * lg n) AC solutions, I really believe that the nature of the queries, at most n different ranges, (without partial overlaps) really improves O(n sqrt n) bound.

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

        I used a hash map (unordered_map) instead of a normal map, and the fenwick tree is tremendously fast, so the additional log n factor is quite reasonable, I was skeptic during the contest (and even tried to find an O(n lg n)), it also seems that Codeforces got some speedy machines.

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

    I think you did something wrong, O(N log N) solution isn't very hard. See 5512577.

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

      Well done, but that wasn't actually a topic of my message =)

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

      Indeed, but it was tricky to realize that is actually O(n lg n) during the contest, those who saw that all the updates are O(n) amortized mostly implemented an O(n sqrt n), the rest just used a Fenwick tree. BTW it would be interesting to find the worst case input for the O(n sqrt n) approach, here the tree structure makes the query ranges quite singular (no partial overlapping), maybe in this case is even better, O(n lg n) or even O(n)?

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

And for second time in a row a purple coder takes down the Div 1. Congratulations, Touma_Kazusa :).

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

    In fact, she is red for a very long time.

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

      In fact, she is one of the top rated users.

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

        Can you tell us who is that?

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

            :(

            Are you sure?

            The rules: "Don't create more than one account, if you have forgotten the password, use the password reminding system."

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

              Even if the rules should be applied more or less to everybody, I don't think it was an attempt to cheat, or because the password was forgotten, but an other reason (which one, I don't really know).
              The only thing that seems unfair it's that will affect rating changes of all others contestants.
              I mean, I suppose that being beaten by a purple when you are red/orange make your final rating lower than if you're beaten by a top 10 user...

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

ну блин, с каких пор N2logN тлится при N=5000?

>:(

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

    проходит оказывается

    код 5509284 с sort intов через свой компаратор — TLE 2000мс

    код 5510980 с просто sort — AC, 998мс

    С++ — говно меня огорчает

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

      Еще немного магии.
      5511406 — stable_sort с компаратором.

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

        и как спать теперь?

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

        А как писать sort со своим компаратором, чтобы он не получал TL в данной ситуации?

        Я умею только так: sort(c, c + n); reverse(c, c + n);

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

          Я написал sort(v,v+n,greater<int>()), и прошло за 1.3с.

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

          Компаратор надо через функтор писать, он оптимизируется лучше: 5523979. Подробнее можно у Мейерса прочитать.

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

    log(5000)*5000^2 ~ 3,7*25*10^6 = 92,5*10^6 ~ 9*10^8. А это как бы совсем не две секунды...

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

      В последнем "приблизительно равно" на порядок ошибся...

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

    Если вы о задаче В, то там можно и за O(n^2) решить.

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

in problem D,why my O(n*m) solution get tle? 5509804

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

Эх, на один бы взлом больше и... =)

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

thanks pretest #11, for problem A (div-2).

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

Could someone explain the solution of Problem D? Thanks in advance

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

How to solve E div 2 / C div 1?

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

The "Custom test" feature here limits testcase input to 256KB, but the maximal testcase for "Maximum Submatrix 2" (Div 1 B, Div 2 D) has a 5000x5000 matrix (25M elements), so it seems impossible to properly test the maximal case for TLE against Codeforces servers (even if you hardcode the testcase in the source, you're circumventing the time taken reading input). Is there any good strategy for handling this, or any way around this restriction?

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

[email protected] D,,my time is n*m*logn.....TLE.= =

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

What does I.O.U (name of problem B of Div 2) stands for?

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

I don't understand why in B/D n<=5000. Many people submitted correct solution, but because of using (in my case cin) got TLE. I think n<=1000 would be enough for solutions with bad asymptotics to not pass.

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

    I got n*m solution but because using "cin" got TLE.if n <=1000 than it can be solved also n*m log m and it did not want to author,I think author is strict in this issue.

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

Am I missing an easy solution to Div1 D or so many people have managed to code solution that resembles mine? I've done it by an algorithm which resembles heavy-light decomposition. I've done DFS, computed some data for every subtree and in one vertex I copied the data from smaller subtrees to the biggest one, which results in O(n log n) solution. I was really satisfied to get this problem accepted :).

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

    Can you explain more detailed your solution? In Russian comments here we discussed accepted solutions in O(Nlog2N) with the same "copy data from smaller subtree to the greater one" idea, but the data was stored in log-time containers, such as Cartesian trees and Fenwick trees, so asymptotic was O(NlogN·logN) = O(Nlog2N).

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

      There is also a solution with complexity O(N * log^2(N) + (Q + N) * sqrt(N)) without advanced data structures, by splitting the set of colors into heavy and light sets such that light set contains colors that have < sqrt(N) elements and heavy set contains colors that have >= sqrt(N), then the light sets could be processed with simple dp on tree, and heavy sets could be computed using the "copy data from smaller subtree to the greater one" idea because there is at most sqrt(N) heavy colors.

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

      Here is my code that got accepted: http://codeforces.me/contest/375/submission/5508056

      For every vertex v I call DFS(v, log) where log is some number between 1 and log n. If vertex v has children v1, ..., vk and vertex v1 has the biggest subtree, I call DFS(v1, log) and DFS(v2, log + 1), ..., DFS(vk, log + 1). If I call DFS for vertex v with corresponding argument log, after calling DFSes for its children I want to have some data in col_num[log], at_least[log] and ver[log]. For fixed color c, col_num[log][c] means how many there are vertices in this subtree with color c, for a number k, col_num[log][k] means how many there are colors c such that col_num[log][c]>=k and ver[log] is simpy vector of all colors of vertices in this subtree. Those data allow us to simply answer all queries in each vertex and update corresponding data in our parent in time O(size of our subtree) (if we aren't the biggest subtree's of our parent's children's subtrees) which results in O(n log n) complexity of whole algorithm. If our subtree is the biggest subtree of our parent's children's subtrees, our parent just treats our complete data like its initial data and update it by other children subtrees.

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

Power of MS C++!!! I think if lots of TLE codes submit their codes with MS C++ compiler,
they will get accepted!
Accepted Solution: 5511246 and 5511362 and 5511553
TLE Solution : 5511075 and 5507435 and 5505552
I submitted these TLE solutions with compiler MS C++ and got AC!
What is the real reason?

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

    problem B sux

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

    you can't strongly say that MS C++ is better than GNU C++. The difference is that cin and cout have been defined differently in these two compilers. The time of cin in MS without ios_base::sync_with_stdio(false) and with it is really close, however there is a massive difference in GNU with ios_base::sync_with_stdio(false) and without it. But GNU is faster with syncing than MS with it. I can show u a lot of codes which got acceptance with GNU with syncing that same code in MS didn't.

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

Div.2 Problem D I add ios::sync_with_stdio(false); and pass.........

Can anyone help to explain?!

What a pity...

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

Feel quite disappointed about the problems setter (or the translator) of problem D div 2. You can rearrange the row but each col MUST BE ORIGINAL

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

Можете объяснить почему 5505144 Runtime Error в задаче 376B - Задолженности ?

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

    m <= 10^4, а у тебя массивы a, b, c на 111 элементов.

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

Div.2 Problem D: priority_queue got TLE (AC in MS C++), push in vector and sort got AC :(

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

I don't know about you guys but I used a physics formula for Div 2 A. Is there any other solution?

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

Thanks for nice contest! It requires an ability to write fast without bugs not-completely-simple code in each task.

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

Can someone please tell me where my solution for div2-C is failing? I made use of the mathematical trick of finding %7 for large numbers.

http://codeforces.me/contest/376/submission/5506741

UPD: Found my mistake. Thanks to Zlobober ! :)

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

    Your idea is quite right but you should add your mp[remmod] to the end of the answer, because it will give the right remainder, but not 10^(len — 4) * right remainder.

    http://codeforces.me/contest/375/submission/5504410 -- my solution.

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

      Adding mp[remmod] to the end is wrong because that can cause leading zeroes.

      In any case, I found my mistake a while back and corrected it. :) Thanks!

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

        Well, you can add all zeroes to the end, as in the author's solution.

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

          Not quite. I'll give you an example.

          No zeroes in this case, so according to you I should add mp[remmod] to the end. But it is wrong.

          Test Case : 11689 Output : 18961 ( = 5 mod 7 )

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

It is realy unfair..... algorithm and and implement is correct only because of ios::sync_with_stdio(false); I get TLE....

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

    You should try to study more about the ur programming language sometimes :)

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

It was really best Christmas present, thank you very much and see you in DIV 1 :)

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

+100 :D

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

It is recommended to test the maximal case locally.
I think that it takes less than two minutes to write a code to generate maximal case.

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

+198 :)

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

First of all, thank you for preparing the problems for us. It was a nice Christmas Eve.

However, I would like to point out the problems is not very good (at least for me).

For Problem B, it is EXACTLY THE SAME with CEOI 2010 Day 2 Problem 1 Logs (the only difference may be the problem from CEOI asks rearranging the columns).

And for problem C/D, I cannot recall clearly the source of these problems but I have solved tons of problems based on the old idea.

I hope that Codeforces can have more problems with new idea instead of the old one. New idea may be easy, simple, interesting, ... but it is good.

Anyway, problem A/E is really nice (maybe adapted from Chengdu Onsite 2013?). I don't come up the solutions till now.

Thank you again!

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

    Well, if D has a nicer solution, than "move-info-from-smaller-subtree-to-larger" one with using some complicated data structures like maps, hashmaps, cartesian trees, fenwick trees etc (that are discussed above in Russian version of the site) then it would be great to know about them. Maybe when problemsetters publish editorial we will find more interesting solutions to it.

    And C seems very nice and interesting for me. Can you give a sample of the problem with the same idea? Moreover, if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem (but with such explanation in task the idea to store a mask of oddity for each object becomes much clearer and obvious).

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

      The Grove -- USACO 2006 January Silver

      As far as I knew, this may be the first time this idea appears. The problem can't become cooler by replacing the definition into something like "reach from the infinite point" since it must allow multiple pass of one cell. It is not that natural.

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

      If someone has read this and not my explanation few posts above — yes, instead of maps, trees and other stuff, you can use arrays :D -> http://codeforces.me/blog/entry/10034#comment-155315

      But one one drawback is that this results in also O(n log n) memory, there are other approaches with those more complicated structures which requires O(n) memory only. But if it fits into limits, there's nothing wrong with it :).

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

      "if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem" — imagine a closed curve with many selfintersections (those are allowed in this problem!). Could you clearly state what's its interior and what's its outerior? These 2 words are losing their meaning and the only thing that can tell them apart is this parity definition.

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

        Yes, that's exactly what I meant by phrase "authors have to explain what does that mean".

        hmspmy077 in his comment above showed much nicer task, that deals with that problem another way. For that task there is no need to define what interior exactly is, because it uses only the "walk around the connected figure" conception, which is much simpler to imagine and doesn't require additional clarifications.

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

    Problem A is not new at all — see there http://acm.timus.ru/problem.aspx?space=1&num=1095 There's about 2000 sucessful submissions on it on the most famous Russian online judge.

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

I did not write this round well,but I liked problems very much,thanks authors for contest.

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

How did people use sorting to solve Div2 D / Div1 B? O.o

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

    Awesome work, like previous stats.
    How do you make such requests on this website to get data? wget parser?

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

      Thanks! :)
      If I get your question right, requests are made using XMLHttpRequest from javascript. After the received html data is processed, graphs are built using Google Charts.

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

Alternative problem for Div 1 A/ Div 2 C:

Is there a simple solution at this problem:
Find a permutation of a number n composed only by 1,6,8,9 digits (666,1689 etc...) divisible by 7
I tried to solve this problem during the thirty first minutes before finding my misunderstanding...

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

    As long as there's at least one occurence of each of numbers 1,6,8,9 in that number, it's the same as Div1 A :D

    For arbitrary numbers: if the input is small, you could do DP on (remainder,how many digits of each type you have left); if it's large, there are either few ways to solve it or a permutation should always exist, like numbers "16666666","61666666",...,"66666616" which give different remainders mod 7 — so it's enough to consider a random permutation of other numbers before it and choose the ending few digits that are good.

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

      Ok, so for larges numbers, we can't have perfect polynomial solutions (I mean, without using random) ? Anyway, thanks for this answer.

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

        I think we could get constant time solutions. Well, constant if we had just the occurences of 10 digits (if we don't limit ourselves to 4). Actually, digits with 7 possible remainders.

        As long as the number is diverse enough, there should be a small subset of digits such that there's a permutation of them with remainder x for all 0 ≤ x < 7; if there's such a subset, the length of the number is, in fact, irrelevant — no matter what permutation of the remaining digits we use at the start of the number, we can always pad it with the suitable permutation of our subset.

        The problem we got just specifies the subset for us: remainders "1,1,2,6". This is quite small, and I don't think any required subset (that doesn't contain any smaller required subset) will be much larger. Notice for example that the subset "many 6-s and 1" that I presented can be replaced by "many x-s and y", and it still holds for x, y giving different remainders mod 7 and even any prime modulus (not just 7) with 10 as the primitive root!

        That leaves us with the task of bruteforcing all suitable subsets, hardwiring them into the code and just choosing the right one for any number :D

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

Thanks for the round! The problems were very clever, even though I didn't solve them during the contest!

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

Timus 1095 is exactly the same with today's A div 1. The only difference is digits used but I suppose that there're many different sets of 4 digits that work in this case — it doesn't mean though that problems will be different as well.

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

:(((

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

Не особо хотелось, но раз уж такое дело...

Достаточно долго придумывал и писал решение по А. Ну да ладно, вроде написал, отправляю. ВА4. Что?! Код же практически идеален. Ладно, ищу багу. Нахожу — хвост делал с таким же остатком, как у первой части числа, а не с (7 — остаток). Исправил, ну теперь точно правильно. Отправляю без теста на семплах. ВА2. Как так?! Нахожу ещё багу... После цикла с подсчётом первой части числа не умножаю остаток на 10000. Теперь уж потестил на семплах — претесты пройдены.

Задачу Б тоже достаточно долго придумывал для её простоты, но и ладно. Написал, засылаю — ВА4. Баги, баги... Таак, я в своём решении двигаю не строки, а столбцы, отлично. Меняю решение, отсылаю без теста на семплах — ВА2. Ну что за дела... При подсчёте подряд идущих единиц делаю cnt[i] += cnt[i] вместо cnt[i] += cnt[i + 1]. Шикарно. Отправляю снова без проверки на семплах (заметьте, какой я самоотверженный). И... ВА3 (да-да, это семпл). Снова ищу багу. Умножаю на (m — j) вместо (n — j). Одна бага замечательней другой. Исправил, отправил, прошёл претесты.

Задача С как-то не далась. Начал думать над Д. Долго мучался, извращался, придумал только за квадрат, эх, ладно, почему бы не пойти не поломать, видел в таблице плюсики за взломы. Смотрю решения по А. Вроде всё правильно. Особо негде и не набагаешь. Так, решение с BigInteger для проверки на делимость. Забано, но не поломать. Перехожу на задачу Б. Смотрю, смотрю, особо ни к кому и не придраться, возвращаюсь к оставшимся кодам по А. А вот и что-то интересное — следующее решение с оператором next_permatation(s), где s — исходная строка. Радуюсь, пишу тест, на котором должен быть ТЛ. Решение проходит... Непонятно. Пишу новый тест. И его проходит... Вот я лох, даже такую ерунду не могу взломать. Пока я осуждал себя, контест закончился. Решение то, конечно же, упало на систестах.

Но и это не всё. Решение Б падает с ТЛ. На контесте почему-то оценил решение O(n^2*logn), подставив n = 1000 вместо n = 5000, поэтому показалось более или менее годным. В последние минут двадцать глянул ещё раз решение перед тем, как блокировать. Думаю: "Ну, по сути, должно заходить. Можно, конечно, исправить сортировку слияниями на сортировку подсчётом, чтобы уж точно заходило. Хотя... Не, и так очков раз два и обчёлся, не к чему терять ещё, блокирую".

В общем, я снизу таблицы. Большой минус, выход в фиолетовую лигу.

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

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

    Я пока поношу тогда Ваши оранжевые штаны. С позволения...

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

    Каждая лишняя попытка — минус 50 очков, что соответствует 25 минутам задержки для задачи (500) и 12 минутам задержки задачи (1000). Поэтому лучше потратить две минуты на локальный прогон претестов и чего-нибудь еще, чем не потратить.

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

А как сообщество смотрит на идею о том что бы в обязательном порядке добавлять макс тесты (по времени чтения данных) в претесты, вроде этим мы ничего не теряем (кроме времени исполнения претестов) просто отсекаем тупые баги из серии считал string (при помощи cin, geline) или char[] (scanf)?

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

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

    К сожалению, мы не принимаем во внимание cin приведет над срока.

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

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

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

Anyone get TLE at DIV1-B, try scanf("%s") instead of cin. what a sad story, my O(N^2) solution with very small constant coefficient TLE.

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

Can anyone explain test 4 of Pro.B div 1 (or Pro.D div 2) for me ? In the first row we have 10 ones so we can put ones adjacent so that we have a rectangle with size 1 x 10, or I misunderstood the problem ?

http://codeforces.me/contest/375/submission/5515862

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

What is the official solution for DIV1-D? When I read other's AC codes, to my surprise the moving-interval solution could pass-_-!!

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

questions were interesting and little bit tricy...Hats off to problem setters!!!

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

Can you post the editorial please.

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

То, что фиолетовый выигрывает второй раунд подряд на КФ — это новая мода? Может, в следующем КФ поучаствовать?