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

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

Всем привет!

Сегодня в 19.30 по московскому времени состоится Codeforces Round #319, который настоятельно не рекомендуется кому-либо пропускать.

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

Как всегда, благодарю Zlobober за неоценимую помощь при подготовке контеста и утонченный юмор, sankear за написание перекрестных решений, Delinur за перевод условий на английский язык и MikeMirzayanov за потрясающие системы Codeforces и Polygon.

У вас будет два часа на то, чтобы решить 5 задач. Успехов!

UPD. Разбалловка в первом дивизионе — 500-1250-1250-2000-2750.

Во втором — 500-1250-1500-2250-2250.

UPD2. Из-за тестов большого размера по некоторым задачам, системное тестирование будет идти медленно (возможно, займёт несколько часов). Благодарим за терпение!

UPD3. Разбор можно найти по ссылке.

UPD4. Winners!

Div1:

1). Marcin_smu

2). mnbvmar

3). I_love_Tanya_Romanova

Div2:

1). latisel

2). wrong_order

3). ntitry826

Отдельный респект al13n за правильное решение задачи Div1.E во время контеста!

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

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

Trinity Contest

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

Registered with bells on :)

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

If it can be postponed for 24 hours, that will much better. Friday is not weekend. Go to school or go to work prevent us from getting up late, even though we participate in Codeforces Contest in the evening.

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

Thank you for contest, I think in this contest will be interesting and a lot of hacks. Sorry for my poor english

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

Will the problems be sorted in an ascending order of difficulty?

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

    the statement in the post: "In order to increase the probability of finding that task, please read all of the problem statements" means alot

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

      I think it doesn't, since "that task" refers to "everyone will find a satisfying problem". The question wasn't if the problems will be sorted in ascending order of satisfying-ness.

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

weekend or not weekend ,i hope contest will be running.

Because it is div2 round and it will happen after a long time.

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

Thanks for this holding this CF round and hope everyone can get good score!

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

I hope the problems will be short and to the point. Not with long stories.

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

    But I hope The problems will be short and the point. Not with long stories.

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

    But I hope the problems will be short and intersting, Not with direct statement "please calculate something"

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

Wish me positive contribution :P

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

looking forward for your first set of problems :D

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

Hope that more contests will be scheduled at 11:00 instead of 11:30

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

Time to lose red!

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

hope understand from first time read :3

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

Did you notice that registration finishes as time contest starts not 5mins before...
P.S No That was an error I think? When I looked both times were same..

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

это только у меня CF начиная примерно с часа, после начала контеста жутко лагал?

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

    У меня все было ОК

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

    У меня лагал только в самом конце. Учитывая что 10 минут добавили, лагало точно не у тебя одного.

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

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

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

Thanks to author!

contest was great

,how to solve "Modulo Sum"?

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

    I used set, but might TLE. Saved all possible modulo remainders for each element, basically.

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

      That's not enough. You need to combine each remainder with each remainder to get new remainders.

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

        Yeah that's what I did. Instead of iterating over a 10^3 array, I used set, that's all. But sets have a huge constant associated with them, which is what is making me nervous.

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

          And you can also combine the remainder with itself certain number of times. I cannot view the solutions yet, but I'd like to see how you solved that.

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

            "And you can also combine the remainder with itself certain number of times." why?

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

            Actually, you can't sum one number more than once, the only strange thing was that after n, the subsecuence could continue in 1, but without repeating any number.

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

              its actually coin-change. treat the remainders as the coin that you have, how many numbers can you make. check through these numbers to see which are divisible by m. and you are done.

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

                NO, is not like that, because is a subsecuence, not a subset, a subsecuence is of continuous numbers.

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

                  It didn't have to be a contagious subsequence. One of the examples had a non-contagious solution:

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

                  Yes, but I thought It could be circular, so, after the final 3, continues the first one.

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

                  contagious=transferrable, like diseases contiguous=one after another

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

                At least that is what I thought, but now I see my answer received a WA in the 39 tests

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

    I think there's no way it's impossible if N >= M. My not-very-rigorous-but-you-get-it proof:

    Imagine you're doing a simple dynamic programming solution, with the elements sorted in ascending order first. If a number's multiples "circled back" all the way to 0 (this might mean going around the modulo space several times), we're done. So assume that didn't happen yet. If we can prove this means we'll always get at least one possible new modulo value when adding each number, it's proven. So take a new number X. There are 3 possibilities:

    • This number already occurred. It can't have circled back, so by adding it to the last iteration, we get a new value.
    • It's a multiple of a previously occurring number. Since that number hasn't circled back, we can get several new values just like we did in the first case (from the last few iterations).
    • It's a relative prime to all that occurred before. Obviously, X%M hasn't occurred before, so that's a new value.
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      i found this during the contest http://math.stackexchange.com/questions/699857/proof-subsequence-of-n-integers-is-divisible-by-n

      if you understand the proof please explain it here in plain english. thanks.

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

        this is a different problem. for this subsequence, it doesnt have to be contiguous, whereas the link that you have shown seems to talk about subsequence in contiguous form.

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

          But if there is a contiguous subsequence, then there definitely is a not necessarily contiguous one. I fail to see how this is not relevant.

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

        Appears I was right, yay! :D Anyway, what I posted above is a plain English proof of this statement. But I guess the one given on Math SE is simpler, so I'll explain that one as well:

        Let's assume M == N. I'll only use N in the proof.

        Let's define the series R_1, R_2 .. R_n like this: R_k is the remainder of the sum of the first k elements, that is, (a_1 + a_2 + .. + a_k) % N.

        If for some k we have R_k == 0, take that subsequence and we're done.

        Otherwise, there are N numbers in the R series. They can have N-1 possible values (since none of them was 0). This means there are two equal numbers in R, so there are two prefix sums in the original series whose remainder by N is the same. Let's say R_i == R_j, and i < j.

        This means that adding a_(i+1), a_(i+2), ... and a_j to R_i didn't change its remainder by N. So the subsequence a_(i+1) + a_(i+2) + ... + a_j has a remainder of 0 by N.

        This also showed that there must be a CONTAGIOUS subsequence that satisfies this.

        EDIT: ffao managed to explain this proof much simpler than I did, look at his explanation if you don't get it :)

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

      The (easier, I guess?) rigorous proof:

      Let the sum of the first i elements modulo m be S[i]. There are m different possible values of S[i]. If we find S[i] such that S[i] = 0, we're done. So suppose none of them is zero. By the pigeonhole principle, at least two of S[1], S[2], ..., S[m] must be equal, say S[x] = S[y]. But then a[x+1] + ... + a[y] = S[y] — S[x] is divisible by m!

      So it's always possible if n >= m.

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

        Thanks GrandMaster ffao

        For the case of n < m, can i add dummy values of 0 so that n >= m and then argue that if we can't find S[x] and S[y] then it was not possible with the initial sequence ?

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

          Adding dummy values of 0 is not a valid modification as it changes the answer to the problem. That happens because you can always select your newly added 0 as the divisible by m subsequence, which will make it always possible.

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

What is happening? Why the contest is still running when everybody stopped and there was even a window with information that coding phase has finished?

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

    I haven't seen any notification about extending the round and a lot of people too. Was it a bug or there was no notification at all?

    Nevertheless, I think that the submissions after the original time should not count...

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

    The system gone to total gc on 1:23 :( We are working to reduce memory consumption and prevent such situations.

    We increased contest duration while backed was restarting. Unfortunately, we were unable to send notifications.

    Right now our highest priority task to fix it. Sorry to inconvenience.

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

Was the round extended? Cause I did'nt get any notifications.

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

Seriously, no adding minutes for the round? And system is not available last 5 minutes of contest.

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

Господа, продлевать контест после того, как все увидели плашку — это ппц!

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

Are you going to cancel submits after 2:00?

Btw. I lost 5-6 minutes not knowing that round goes on. And I found a bug 10 seconds after the final end. I hope it wouldn't get AC — http://ideone.com/6DVME8

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

Продлевать контест вот так вот, без оповещения — не дело. Я-таки мог за потерянные 2,5 минуты запихать C-шку.

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

    У меня прикольнее было. Минут за 15 до конца контеста понял условие в В, начал писать, тысячу раз набажил, пока ловил баги — хром вывел сообщение "контест закончен". Я, расстроенный, сижу, дебужу не спеша. Нашел ошибки, думаю послать в дорешку. Пытаюсь открыть архив, вылезает надпись "администратор заблокировал архив". Вхожу в контест(счастье, что в этот момент не очень сильно лагало) и вижу, что контест продлили еще на 10 минут. Вставляю решение, отсылаю за 36 секунд до конца. В это время залагало, и уже после завершения контеста пришла надпись "претесты пройдены". Теперь сижу, жду систестов)

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

Я хотел написать такое решение на D(Div2) но конечно не успел: Если есть x такое что p^2[x]=x и для всех остальных чисел p^k[y]=y тогда и только тогда когда k четное, тогда ответ YES и все связаны с x либо p[x]. Иначе NO. Это правда?

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

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

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

    Ок, неважно, я тупанул :(

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

      Раз есть ребро 4-6, то должно быть 1-5. Итого не дерево.

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

      Вроде у вас в этом тесте 2 4 6 будут в цикле.

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

      Кажется твой ответ неправильный например не хватает ребра (6, 1) т.к. есть ребро (5, 6).

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

      Нет ребра 5-1. Вершина 4 может быть связана с вершиной 6 только если p[4] = 5 связана с p[6] = 1

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

    А что если существует x, что p[x] = x. Тогда ее вроде можно с остальными соединить и все ок.

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

I hacked 2 C-div1 problems with carefully written cases to solutions close to what I believe is the correct answer (somehow partitioning the space in chunks of size 1000xsth and move around them properly).

However, if they are partitioning them in chunks of something different but close to 1000, my test cases probably won't work because their structure is completely messed up,since they are meant against partitions of 1000 (could have been 1001, nothing special in 1000).

Can you come up with a way of creating a challenge that doesn't assume a particular number with which partitioning space? There should exist some of those in system testing, but I cannot come up with them.

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

    PS: the system test probably didn't have them because one of the programs I hacked got accepted just by changing the partition number from 1000 to 1500.

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

When editorial will be available?

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

Задача B(Div.2) — O(N*M) ?

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

    Да

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

    да, но вообще, как я понимаю, максимальное кол-во операций порядка 10^6(тк, почти всегда(может быть вообще всегда),если n>=m, то ответ да, следовательно достаточно дойти до n = m, а m <= 1000)

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

    Я делал с структурой bitset, которая работает на константу быстрее простого перебора по остаткам

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

      map пройдет?

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

        Map и bitset совершенно разные структуры, так что не понимаю вопроса

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

          Можешь объяснить свое решение див2 Б? Оно смотрится намного интереснее, чем то, что в разборе.

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

            Стандартная динамика dp[j] — можем ли мы получить остаток j, используя первые i элементов. (Измерение по i не нужно) Вместо обычного массива для dp используем bitset размера 2 * m. Bitset поддерживает все битовые операции. Храним единички на местах, где мы можем получить остаток j. При добавлении нового элемента, если мы можем получить какой-то остаток j, то записываем, что мы можем получить остаток j + a[i] % m. Если делать это с помощью bitset, то это выглядит так: a |= a << (a[i] % m). Где-то j + a[i] % m могло получиться >= m, в таком случае нужно сделать так, что если (m + k)-ый элемент равен 1, то k-ый элемент тоже должен быть равен 1.(т.к (m + k) % m = k): a |= a >> m;
            Потом ставим 1 на место a[i] % m: a.set(a[i] % m); Ответ YES, если на нулевой позиции стоит 1(можем получить остаток 0), иначе NO

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

        Bitset — это конкретная структура, в С++ есть такой библиотека . С помощи этим можно любую битовые операции.

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

When will editorial be available?

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

The connection problems were unfortunate, but I really liked the problems, great job! B was especially interesting.

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

For C div2, My solution is to print all prime and perfect square numbers that are less than or equal 'n'.

Why is it wrong ??

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

How solve problem C div1 ?

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

Wow , do we have a new dreamoon_love_AA : .o. ?

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

The problems are awesome. Hard to believe none of them had been used before. =)

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

    Why do you call B and C awesome? Some arguments? B is 'write two if-s', C is 'think of the correct partition', both are boring and non-interesting for me.

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

      Well, B ends up somewhat involved while being really simply stated (also I tend to like problems somehow connected to graph isomorphism =)), and C has a constructive flavour which is always nice. The 'think of the correct partition' is for sure more creative than 'implement the segment tree for the bazillionth bloody time'.

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

        I agree that such original problems are the best. Like misof said, "The less it resembles anything I've seen before, the better!"

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

      It is because you are too good For beginner, like me :'( , they are too interesting

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

    The idea of E is old though. For some reason it's still not very overused, I've only seen it maybe four times.

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

      Can you provide some links? malcolm and sankear invented this idea while solving some completely different problem (having nothing common with this kind of semi-online dynamic connectivity) in a pretty complicated but elegant manner.

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

        http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf

        (for the dynamic connectivity; the DSU with flags is new to me and was a nice touch)

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

          Of course the dynamic-connectivity-offline itself is well-known thing, we do not pretend on inventing it. What I asked you is idea that while traversing the tree of divide-and-conquer we can still modify information in the future in a manner similar to segment tree. Did you see such approach before?

          BTW, DSU with flags (as I understand you mean a data structure for adding edges and checking if the graph is bipartite) is described on e-maxx.

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

            Oh, ok, I guess that's new. Sorry, haven't thought about it as a separate idea. Probably because in the implementation I'm used to it's a straightforward modification.

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

How to solve Div1-D?

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

Div 2 D anyone??

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

please make testcase so as to fail all n*m solutions mine n*m failed while this HURTS

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

    That solution is not n*m. That solution is min(n*m, m*m). (The loop will always break after at most m iterations, for reasons discussed above).

    In other words, that solution is correct.

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

Anybody who solved C(Div 1) as follows. Divide into 1000 blocks with 10^6x1000 rectangles. in each rectangle sort points by (x[i]+y[i]), I think it can be proven that will give 2n \sqrt(n) bound.

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

Why there wasn't any announcement for the extra 10 minutes!!

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

    I tried to submit solution 2 minutes before contest end and I could not do it. 15 seconds before end I could submit, but I was not fast enough. I waited 2-3 minutes to see if contest is extended, but it was not. The only good think is that my solution would be incorrect anyway as I checked.

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

Div 2. A. What is a worst test case time complexity for this solution? 12930538.

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

    It seems to be that the worst case for that solution is a n = 10⁵ and x = Highly composite number below 10⁹. It may be something like divisors(x) * n. On a quick analysis it seems that x has more or less 10³ divisors. So, the result should be 10⁸.

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

LoL, why this solution gives TLE:12934189? Is it because of using vectors?

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

    No, because you did O(n*m). Beign n <= 10⁶ and m <= 10³ you have a 10⁹ solution. That's slow.

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

    You are dividing 1E9 times but divisions are expensive so you can't make a lot more than 1E8 of them per second.

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

      But my solution is O(m^2)( I consider case when n>m).

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

        Ah sorry, I think the problem is that you are reading a million ints using cin, c++ streams are often too slow for such huge input.

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

          that would be really sad as i also seem to have O(m**2) but i am reading data with cin :(.I also think this should have been covered in pretests

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

            cin is fine; just add this magical command:

            ios_base::sync_with_stdio(false);

            See here.

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

              Magical command helps a lot, but anyway cin is much slower then scanf, even with command.

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

                Ironically, I've had my first experience with that just now.

                But it is fairly rare. Still, I'll use scanf from now on.

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

    Do you ever clear xp? I think xp might be getting really big near the final iterations...

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

Ugh, I only had a bit less than one hour for the contest. To be precise, I'm travelling and the only place where I could do the contest was one train/bus station (next to each other). But the train station's net hotspot didn't work and the bus station only has a 3rd party connection with 1 hour free, then nothing. So I hurried a lot and I think I'm going to fail both B and C.

Why couldn't the round be 2 hours earlier... I could've done it at home then...

UPD: yes, I failed both B and C.

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

    Why didn't you leave this one for virtual contest if you were travelling?

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

      Because it'd be yet another one. Most CF contests have had awful dates for me recently (which means the last few months, because there have been so few). When I'm home, there's nothing, then I leave somewhere without net for a few days and a CF contest is guaranteed.

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

2s * 617sols * 50tests ~ 900 min testing (task C)

Where am I wrong?

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

    Ok, I can't into parallel calculations and good solutions which work fast (or fail early), but it still slows testing, thank you for the limits

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

Am I the only one who mistakenly read the constraint in problem C as 2.5·108 instead of 25·108? The common agreement about scientific representation of real numbers is to use normalized notation and according to it the constraint in problem C should've been 2.5·109.

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

    You are not alone)

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

    At first I also misread it, but the points (1000*i, 1000*j) with 1 <= i,j <= 1000 are such that the shortest Hamiltonian path has length ~10^9

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

    In fact it was possible to understand that you understood something wrong by noticing that for the 1000x1000 uniform lattice (all points of form (1000a, 1000b)) the answer has order of 10^9.

    Nevertheless, you are right, writing 2.5 * 10^9 could've been much better.

    UPD: oh, Nicolas16 said the same thing before me.

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

      Well, the statement said "it's guaranteed that the answer always exists for given input" so I didn't worry too much about that :)

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

        Yeah but then there would have been input where the minimal length is exactly 2.5 * 10^8, which means that we would have had to find the exact minimal path in this particular case (which did not seem to be the the goal of the problem).

        However, I had to remark all these things during the contests and I lost some time before understanding I misread the bound, so I am not saying you are wrong :-)

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

    I thought it was a trick to obscure the desired complexity. 2.5·109 looks pretty much like while 25·108 is «what the wierd constant is it?!»

    I really thought of it as a nice beautiful obfuscation, no irony here.

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

Too scared to look at my submissions page.

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

После конца контеста понял, что в C было манхэттенское расстояние(а не евклидово ;c)

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

    Разве это меняет решение?

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

      Да, кажется, вы правы

      Опять не подумал прежде чем запостить :c

      UPD: однако ж все равно подгорает :/

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

Those permutation problems are cool

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

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

What is special at test 9 from div1B? I looked at my source 10 times bbefore submitting it to be sure I don't miss anything. I've even hacked some sources=)))

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    printf ("%d %d\n", nod1, nod2);
    for (int i=2; i<=N; i++)
    

    Isn't this going to miss node 1 if it is not either nod1 or nod2?

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

I might be the happiest blue coder to-be ever!!!! Should be out of green right??!!!!

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

"and it's strongly disadvised to skip it."

Nice trap

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

12936106 12937847 . по моему одиннаковые посылки

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

Look, the green coder latisel is the winner of a Div2 contest!, oh wait look at his previous contest here.

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

I passed D with "bad" solution :) Only optimization is order of for loop in matrix multiplication — I remember reading somewhere that you can make naive multiplication cache-friendly by switching order of for loops from i, j, k to i, k, j. And after that, all that's left is a trivial if statement that checks a[i][k] isn't 0 before multiplying it with the for loop with j.

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

    I thought about submitting that, but I was pretty sure it wouldn't pass... Guess I shouldn't underestimate the CF servers after all :)

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

      Looks like that is the wanted complexity... Makes me think D is a pretty bad problem now, is it just "submit the obvious solution and hope that it passes"?

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

        There is a typo in editorial I think. It should be "it's not enough", not "now enough". So /32 was intended.

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

    I think I have the same solution (12942073), but it got WA44 and I can't find the bug now...

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

вот такие они, зелёные победители:

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

for DIV2 B: can any one find whats wrong with this submission: http://mirror.codeforces.com/contest/577/submission/12944993

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

Ясно с этим раундом, претесты проводят простой перебор на B, который за nm, но не проходит на полных тестах а дело то всё в том, что если мы находим ответ YES, то нужно просто выйти, если продолжать до конца(O(nm)), то будет TL

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

    На самом деле если N >= M, то сразу можно выводить YES, а иначе O(N*M) не так уж много. Это можно доказать, но мне лень, но могу привести задачу с Тимуса, решив которую за О(N), вы поймёте примерное доказательство.

    P.S. Знал бы ты, сколько я заведомо ТЛьных решений упихивал только за счет того, что когда мы нашли ответ, то стоит его просто вывести. Собственно, изначально ту задачу с Тимуса я решил, упихав O(N*N).

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

why does the use of pow function from math library give a WA while without that its AC... Ans 1 : with pow func http://mirror.codeforces.com/contest/577/submission/12941362 Ans 2 : without pow func http://mirror.codeforces.com/contest/577/submission/12947283

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

    Its happening with me too!!!!!

    codeforces is giving me this output for test case_ 7_**** 19 32 16 8 4 27 9 24 2 3 5 7 11 13 17 19 23 29 31 37

    but my system is giving this output! 19 32 16 8 4 27 9 25 2 3 5 7 11 13 17 19 23 29 31 37

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

      for me its test case 4... cf : n=15 -> 9 2 3 4 5 7 8 9 11 12 ideone : n=15 -> 9 2 3 4 5 7 8 9 11 13

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

    Pow uses floating point values and you round them down when you convert them to ints. It should pass if you add an epsilon.

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

    Try using powl()

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

al13n got 90 tests on problem E, but Endagorion got TL on 96 test, wtf?

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

hi.. i think that there is something wrong with codeforces compiler this code gives wrong answer on test4 problem C http://mirror.codeforces.com/contest/577/submission/12937746 i tried the same input with the same code on my computer and on ideone (http://ideone.com/hIQ3BM) and it gave the right answer.. could any one pleas tell me what is going on?!!

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

    You can't trust the pow function since it uses floating point arithmetics.

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

      Thanks JohStraat..but i can't really understand ..is using pow function causes undefined behavior?? ..so what do you suggest instead using pow function in general?

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

Кто-нибудь может объяснить почему в задаче "B. Сумма по модулю"

при параметрах 2 47 1 0

правильный ответ YES Я не понимаю как из чисел 1 и 0 можно сделать число которое делится по модулю на 47.

Спасибо!

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

Div1 C checker is awesome!)

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

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

I didnt became div1, but I am too close. I hope at future to be :) Thank you for the great contest!

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

Finally got into Div. 1 ..

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

Thanks pretests...

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

2496501499 in C, seems legit :D

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

    With 999 endings instead of 500 in 44th test it would go up to ~2990*10^6, buckets should be sorted to avoid that. Solution of Marcin_smu looks hackable too.

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

This is really bad in cf. TLE with cin and AC with scanf for div2 B. These are the solution links 12935258 12951554

My rating also went down. It could have gone up

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

Объясните пж, кому не лень, что за мэджик-ускорение в авторском решении С (div1)?) Попытался сам написать аналогичное авторскому решение за nlogn; оно пашет, но ТЛится на тесте с 10^6 вершин по непонятным мне причинам...

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

    cin/scanf?

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

      cin, ускорения scanf хватает?!!!

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

        Если в задаче нужно считать или вывести более миллиона чисел, то стоит сразу позабыть о cin/cout. Разница по времени может быть в несколько раз (помню один раз в 6 раз разница была).