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

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

Привет всем! В этот вторник пройдет Codeforces Round #213, задачки для которого придумал я. Спасибо caustique, el_sanchez, KAN, malcolm, они тестировали задачи, помогали с составлением тестов и условий. Спасибо Gerald, который координировал работу и помогал в решении возникающих трудностей, MikeMirzayanov за создание возможности проводить соревнования и Delinur за перевод условий на английский.

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

Контест закончился, можно поздравить победителей

div1:

  1. lovelymoon
  2. niyaznigmatul
  3. cerealguy
  4. ainu7
  5. cgy4ever

div2:

  1. dotato
  2. netman
  3. kybconnor_4

Прошу прощения за косяки в условиях, которые вызвали тонны вопросов. Впредь я постараюсь внимательнее относиться к условиям.

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

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

scoring system?

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

    Standard. Score distribution is not defined at the moment

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

      The word is actually "standard". I've seen it get misspelled a lot on this site, it's about time I let people know how to spell it correctly.

      [http://www.oxforddictionaries.com/definition/english/standard] [http://www.merriam-webster.com/dictionary/standard]

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

        Thank you =)

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

        This is a common bug for all Russians :) In fact, the word "standard" in Russian is spelled like "standartny" with "t" but not "d". And even if you know the correct English spelling sometimes it may be hard to remember the correct ending.

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

el_sanchez onelove <ЗЗЗЗЗЗ

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

Oh,I smelt some special tricks..

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

I guess the problems will be short and interesting. Like this blog.

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

    You know what's interesting?

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

      Did you know facts are considered to be interesting. So this proves there are things that are universally interesting.

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

      I don't understand your mind clearly. But I think interesting 's different with every pepple. With me, that 's tricky test and many solution has ben hacked! O_o

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

Как можно больше задач... Автор боится проблем с авторским правом, если вдруг посоветует прочесть условия ВСЕХ задач? =)

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

hope problems will be good..

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

giygctr gotcs metrr o'le!!

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

why is today's problemset so hard?

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

This round is similar to Round 144 Div1 standings This round prepared by tunyash too.

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

look at Antoniuk at div. 1. He worked well :D

P.S : He is in last page.

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

this exam very suck for div 2 everyone have solved A and B and no one able to resolve the C , D , E

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

    I can't agree with U. Problem C was just an exercise for Range Tree, main problem was to realize it(I wasn't successful in it ._.).

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

      sum(x,y,z,t)= (s[x]+...+s[y])*(s[z]+..+s[t]) = a

      you can solve this by fixed [x] and [y] and pre calculating [z] and [t]

      nothing about Range Tree i guess.

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

Как "С" решалась? Динамика какая — та?

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

    Можно заметить, что сумма чисел в прямоугольнике с такими координатами будет sum(x,y)*sum(z,t), где суммирование идёт по соответствующим индексам строки s. Нужно лишь рассмотреть все варианты таких сумм и аккуратно подсчитать те из них, которые могут дать в итоге a.

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

    a должно быть равно произведению сумм на каких-то отрезках. Итого находим всевозможные суммы на отрезках, подсчитываем, сколько раз они встречаются, далее за линию от количества таких сумм подбираем подходящую пару.

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

Div.1, давай, до свидания! :)

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

Задачи A и B на внимательность)

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

Does anyone knows the 4-th test for B?

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

If anyone can tell me what is the pretest 3 for problem A div 2 I would be very thankful...

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

Does anybody know what's the 5-th tests for C ? I would be very thankful

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

Div 2. Problem C

The moment I realized I can't think better than O(n^3logn) or O(n^4) for MaxSum in a rectangle.

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

    That was the moment I realized the array contained only digits so I could do it in O(n^2).

    Most enlightening moment I got in a contest.

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

    I had an O(n^2log(n)) solution that I couldn't finish coding. I'm not sure if it is correct though, because it uses O(n^2) space.

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

    how do you do n^3logn?

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

where are the editorials/tutorial to div2 213?

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

У меня по Е O(nmk) работало 15 секунд локально. Надеюсь, авторское не написано на указателях с кучей оптимизаций?

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

    Авторское и тестерское разделяй и властвуй за N^2logNK отлично укладывается в TL

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

      Хм, да, у меня то же самое. Я решил что здесь T(N) = O(N^2) + 2T(N/2), поэтому посчитал что логарифма нет. Так вот, оно у меня работает довольно долго без оптимайзов. Авторы в рекурсию массивы не передавали, я так понял?

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

        Мое тестерское решение работает 10.2 с http://pastie.org/8493248 , у Артура оптимальнее написано.

        В нем как видно есть лишние проходы по массиву и никаких оптимизаций не накручено. Массивы и правда в рекурсию не передаются, а к чему?

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

          Ну офигеть, моя Е получает АС в дорешивании. Это при том что я ее долго пытался соптимайзить, потом плюнул и за минуту до конца послал, но забыл ввод раскомментить и она упала на 1 претесте, а перепослать уже не успел. Все из-за того, что на запуске стоит ТЛ 10 секунд, а локально она у меня работала 15. Кстати, прошла за 11.996, как и у единственного сдавшего ее на контесте, что очень странно. Зачем делать такой ТЛ, который даже нельзя проверить на запуске?

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

            Жаль, что так получилось. Я не знал, что ТЛ в запуске 10 секунд. Вроде бы, моя реализация более-менее starightforward.

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

            Кстати да, в Полигоне и на CF в дорешке тоже по-разному время меряется) Вот у меня теперь на секунду быстрее зашло.

            Нельзя сказать, конечно, что TL был с запасом, но такие ограничения были, чтобы предотвратить решения за куб — зафиксируем две строчки, а дальше двумя указателями посчитаем количество отрезков с заданной суммой.

            Или большинство тестов проходит тот же разделяй и властвуй, но где мы на фазе объединения ответов для фиксированной строчки не за O(k) прыгаем, а тупо идем и делаем break, когда набрали большую сумму. Такое решение фейлится только на таблице из почти всех нулей, но на этот случай можно другую заглушку поставить.

            Но вообще я согласен, что немного Гера с Артуром перегнули — в итоге хорошую задачу почти никто не сдал, а твое норм решение тоже еле зашло, да и то не на контесте.

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

            Кстати говоря, в оправдание, макстесты были в претестах — это претесты # 7 и 9. Почему бы после того, как завелось на сэмплах, было сразу не отправить? Ведь время на задачу все равно уже было порядочно потрачено, так что попробовать точно стоило:)

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

              Да я все надеялся ускорить, а оно не работало. Потом за минуту до конца решил все вернуть обратно, сделал даже сабмит, но в нем не раскомментил ввод и оно упало на 1-м семпле. А заметил это когда было уже поздно.

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

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

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

The bad description of problem D div2(problem B div1) really makes me mad!!!!

I read it more than 5 times and still don't know what are you talking about, until I found the Note at the bottom and read the Note more than 5 times.

How can you use nothing to exchange something?

You should say:

Set x can contain nothing.

Set x and Set y can't contain the same item instead of the shit of "Note that each item is one of a kind and that means that you cannot exchange set {a, b} for set {v, a}. However, you can always exchange set x for any set y, unless there is item p, such that p occurs in x and p occurs in y.".

"John knows that his city has n items in total." Ok, there are n items in the city, but how many items in the market?

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

    For the second sample, why cost two days? why not three days? Input 3 5 1 2 3 output 6 2

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

      first day = {} -> {1,2}
      now assume he leaves {1,2} at his home.

      second day = {} -> {3}
      so now he has all of {1,2,3} with him in two days.

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

        Thanks, I got it. It's hard to understand this problem of the poor description, but the solution seems not that hard.

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

Any Ideas for problem C , Div 2 ?

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

    You observe that in a rectangle the sum is (Ax1+A(x1 + 1)+...+Ax2)*(Ay1+A(y1 + 1)+...+Ay2), where x1,y1,x2,y2 are the corners, and the maximum sum of a sequence is 9*n.

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

    Range Tree. U just need to find all x1, y1, x2, y2: sum(x1, y1) * sum(x2, y2) == a. But you should do it smart: 1)Find all x, y: a % sum(x, y) == 0 2)for each of them find all x1, y1: sum(x, y) * sum(x1, y1) == a

    It seems like this solution is )(n ** 4 * log(a)(because of Range Tree)), but it is O(n**2 * k * log(a)), where k is number of divisors of a(close to log(a)).

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

      No range tree. You just need to factor n and n is equal to the multiplication of range sums that can be calculated in quadratic time

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

      No.You just keep a vector ap where ap[i]=number of sequences of sum i, i<=9*n. For a subsequence [i,j], if A%sum(i,j)==0, you add at result ap[A/sum(i,j)].Take care at the case when sum(i,j)=0 and when A=0

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

Anybody home ? someone start system testing

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

Претест 2 задача С кто-нибудь знает?

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

    По идее он есть в сэмле

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

      К сожалению, на сэмплах работает верно, но выдает ВА на претест 2

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

In problem A

When writing Let's call a number k-good if it contains all digits not exceeding k (0, ..., k).

Here, doesn't it mean that a k-good number can't have any digit greater than k ???

So far I know, it means, a k-good number can have all digits without those which are greater than k. Any digit in that number can't exceed 'k'.

It has given me a lot of pain.

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

    You cannot assume that it does not contain digits greater than k as long as it has not been mentioned in the statement.

    Actually, you just cannot assume something when it has not been specified in the problem statement.

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

Nooo, finally found out one minute after the competition, that my C gave time limit exceeded because I forgot to print the final \n. First time I've had that bug :(

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

Сложный был раунд :(

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

Got owned for the 100th time by integer overflow for div1 A T_T

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

Congratz lovelymoon for his E 5163338 :D (11.996s, TL is 12s)

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

Вот это решение висит на 5 претесте.

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

    видимо поэтому до сих пор вместо надписи "результаты" висит надпись "системное тестирование"

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

    У него в посылках уже 2 "полных решений" по этой задаче. Странно.

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

Спасибо огромное за раунд, очень крутые задачи! Надо было читать все задачи и решать милую D, а не пытаться конструктивно строить ответ в C:)

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

    В C он нормально конструктивно строится. Ну как. Конструктив и немного random_shuffle :)

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

    В C очень захотелось впилить какой-нибудь строгий вероятностный метод в стиле Алона-Спенсера. =)

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

      А по-моему, в С очень хочется написать перебор и генерить разные числа при зафиксированном количестве простых.

      Наверное, ее бы сдали больше, если бы поменяли 1000 и 1500 местами.

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

        Вот если бы D и C поменять, то D бы точно больше посдавали! Ну, или хотя бы попытались посдавать...

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

          Ты серьезно? Но ведь в C проходило что угодно, честно говоря, и локально тестить это было просто:)

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

Мне кажется, или мало кто следует советам авторов читать условия всех задач?

Лично на мой вкус, задачи A, B, C сегодня были сравнимы по сложности и простой пропихон по D тоже придумывался — надо было просто поподгонять, сколько рандомных чисел мы можем зафиксировать, если нормальной идеи в голову не приходило.

Наверное, такой низкий процент сдавших задачу потому, что многие зациклились на B, хотя она была не самой очевидной:)

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

    А кто-нибудь еще понял B так, что мы всегда обязаны менять все свои вещи?

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

      Да, я так и понял. Потому что если в наборах, которые мы можем поменять, есть одинаковые вещи (на это был акцент в условии), то мы можем их не учитывать — все равно сможем поменять.

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

      B? B про фибоначи было, а если ты про D, то там нормально сформулировано и примеры показаны.

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

        Сиреневые, оранжевые и красные — первый дивизион(1700+). Ты во втором дивизионе.

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

А когда рейтинг будет подсчитан?

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

What is the intended solution for Div1 C? Is it possible to prove it without testing all valid inputs?

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

    UPD: Sorry, here was the solution for B, not C.

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

      Correct. That is, however, the solution to Div1-B :)

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

        Ah well, that makes sense:) Sorry

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

          Well, since you already wrote it, you should probably leave it around, maybe in a separate thread.

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

      I think this is solution for Div1 B, not Div1 C

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

      I understand that the reduction works, but why does that mean that the restriction doesn't mean anything? Why can't the algorithm still find a move that is illegal?

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

        Consider any two sets A and B, with c(A) + d >= c(B). Let their intersection be denoted as C, meaning A\C and B\C don't have anything in common.

        c(A) = c(A\C + C) = c(A\C) + c(C) >= c(B) — d = c(B\C) + c(C) — d

        c(A\C) >= c(B\C) — d

        We can substitute set A\C with set B\C, thus turning A into B.

        Therefore, for any two sets A and B such that c(A) + d >= C(B) we can turn one into another in one step.

        Every step in our algorithm does exactly that, so every move we make is legal.

        Does that explain it?

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

          Yep, I got it now, thx.

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

          I thought we have to swap whole set we have currently with some other set. Really poor problem statement. :(

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

            Yes, I thought that too, until I analyzed the sample test cases.

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

    Mmm. My solution constructs correct set with k' ≥ k elements. It's possible to prove, that we can obtain correct set for any k. But then I use statistic to prove, that I can obtain correct set with exactly k elements. I will write about it in editorial.

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

По С у меня успешно получается сдать решение, которое на самом деле WA. 5164319 не работает для чисел 318-326, 1657-1685. Если еще немного уменьшить одну из констант, которая на контесте подбиралась методом угадывания, то можно заставить его не проходить еще больше тестов, получая при этом АС.

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

    А может тебе в профессиональные тестеры пойти? Постоянно ты заталкиваешь неправильные решения, особенно часто TL-решения на Опенкапе.

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

      Спасибо, я подумаю над этим)

      Но вообще это неблагодарное дело, вот составлю хорошие тесты к какой-то задаче — и потом столько людей недополучит свои АС из-за меня. Грустить будут. Оно мне надо?

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

Как решается div1 D? Что-то мне она не показалась простой)

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

    Только что в дорешивание сдал такое: 20 раз возьмем рандомную пару из массива и посчитаем их gcdg. Вероятность, что за 20 попыток мы возьмем 2 числа из половины, которая соотвествует оптимальному ответу, очень близка к единице. На каждой из 20 итераций теперь возьмем gcd(g, a[i]). Среди этих чисел — делителей g — надо найти наибольший делитель, на который делится хотя бы половина чисел. Будем делать это за квадрат от количества делителей, и по не совсем очевидным причинам наше решение зайдет.

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

      А можно десять раз взять одно число.

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

        Даже так :D Непонятно тогда, почему эта задача стоит как D, если это баянистая идея + straightforward решение. Правда не совсем очевидно, почему это заходит, ведь количество делителей у числа до 1012, казалось бы, обычно около 104, и решение работает за что-то около 109. Хотя у меня отсечения еще какие-то были, может без них не заходило.

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

          А с каких пор 10^9 за 4 секунды не заходит?

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

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

            Ну вот я прочитал, только непредвиденное обстоятельство в шаблоне меня погубило :D

            И вроде делителей должно быть примерно , так что это что-то в духе 2·109. А еще можно было предположить, что авторы сделали тесты, на которых количество делителей всегда получается большое, и тогда решение может работать намного дольше.

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

              А еще Артур говорит, что максимальное количество делителей 6700. Можно как-то пострессить или погуглить, но предлагаю поверить ему на слово.

              Я как тестер написал такое решение, оно зашло за 3 секунды и мы его считали хоть пропихоном, но нормальным.

              Кстати, на GNU C++ заходит (а в Полигоне только GNU), а вот на MSVS почему-то нет:(

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

                А, ну это вполне логично.

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

                А за сколько оно на джаве работало?

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

                  А на джаве мы решения не писали. Но мое решение http://pastie.org/8495137 не использует никаких специфичных конструкций C++ так что может быть легко переведено и скорей всего отработает за то же самое время. Может быть ты напишешь решение на Джаве?

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

                  Ну вот повезло и 7 итераций зашло: http://mirror.codeforces.com/contest/364/submission/5179270

                  Вот я 7 итераций соптимайзил и тоже зашло: http://mirror.codeforces.com/contest/364/submission/5179297

                  Ну я проверил, зайдет ли 8, не повезло и WA: http://mirror.codeforces.com/contest/364/submission/5179302

                  А вот я ещё дурью помаялся, быстрее не стало, но повезло и 8 зашло: http://mirror.codeforces.com/contest/364/submission/5179333

                  Ну то есть 10 я не представляю как на Джаве сдавать.

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

                  А почему до сих пор не существует общепринятого правила писать авторское решение на джаве?

                  Помимо того, что это позволит правильно выставить TL и избежать негативных откликов после контеста, это еще и обеспечивает надежность решения. Решения на C++ ненадежны, т.к. в этом языке можно творить что угодно, и оно может при этом работать. До определенного момента. Например, до получения вердикта взлома "Неизвестный вердикт:OTHER".

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

    Вообще предполагалось решение в таком духе: возьмем случайное число, посмотрим на все его делители, возьмем gcd со всеми остальными и теперь можно посчитать для каждого числа количество кратных ему за O(d) операций (d — количество делителей). Получалось O(iter * n log R + iter * d^2). Вообще это долго, если делать количество итераций не впритык, а с запасом. Поэтому авторское решение делает на итерацию примерно в 10 раз меньше действий, оптимизируя обе части асимптотики. Можно, например, вместо того, чтобы считать все перебором за d^2 считать все за d*2^(primes), где primes — количество различных простых в разложении текущего числа. Легко видеть, что оба сомножителя одновременно не достигают верхней оценки. Первую часть можно оптимизировать, используя статистику. Получается считать gcd за O(primes) К сожалению, я не придумал, как одновременно сделать в авторском решении количество итераций с запасом и не дать зайти решениям без оптимизаций =( Но как-то все равно задачу сдали всего два участника.

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

Nice contest and interesting problems.... Like your other contests....thanks!

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

Is there an alternate solution for Prob:C Div2 ? Something using Data-Structures ?

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

k-good numbers input 1 0 1000000000

Output

1

really 1<0?

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

    It must contain all digits who doesn't exceed k, so if 0 wasn't present, the number was invalid. But it can contain digits who exceed k, that's not a problem. So, yes , 1 > 0, but 1 0 1000000000 should get for output 1

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

      very bad translation, it is k-good if it contains all of (0,..,k) was better, I'm not American by the way

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

      kind of know the reason. "the number contains all digit from 0 to k " is not equal to " the number only can contains all digit from 0 to k.". I should not have this assumption.

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

        Actually problem is in "not exceeding k (0, ..., k)". There was no need of this portion.

        When writing Let's call a number k-good if it contains all digits not exceeding k (0, ..., k). it means, a k-good number can have all digits without those which are greater than k. Any digit in that number can't exceed 'k'.

        Anyway which happened it was to be happened. No doubt, short description of last contest was nice to see. But we also hope better translation from this great community.

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

tanks for the contest. this was to this date my best contest and I don't think I am ever going to get a better rank in codeforces. I didn't like problem C, I solved using simple backtrack. problem A and B and D were great.

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

That moment in which you get WA #115 on Div1-D because you forgot that rand() only goes up to 32767... :(

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

    Can you describe your idea?

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

      Suppose you know GHD divides some element a[i] of the array. You can then take the gcd of a[i] and all other elements, and count how many times each of the divisors of a[i] also divides other elements of the array (should be easy to do in n log n). The largest one that appears more than n/2 times is the GHD.

      Now, the question is finding such an element a[i] quickly. But as GHD divides at least half of the a[i]s, the chance that you take an a[i] that has the required property is over 50%! So just take a[i]s randomly until you run out of time.

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
        for (int i = 0; i < d.size(); i++) {
                 for (int j = 0; j < i; j++) {
                    if (d[i] % d[j] == 0) cnt[d[j]] += cnt[d[i]]; 
                 }
              }
        

        I see such chuck of your code. It doesn't seem to be O(NlogN) as announced in your short editorial, it's rather O(NlogN + (number of divisors of a[i])2 which consumes much more time.

        Can you tell how you're going to process this part of solution in O(NlogN) time?

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

          Maximum number of divisors for a number up to 1012 is less than 7000. So it is not considerably worse than O(NlogN) part I think.

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

            It's true assumption when one is trying to code working solution during a contest but what if the numbers will be up to 10^16? You still we be able to factor one number quite quickly and to calculate all GCDs quickly but the part with 2 loops to traverse list of divisors will be bottle-neck in such solution.

            I'm just trying to figure out better approach to solve this problem.

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

          vector d represent the divisors of a[idx] which is theoretical have at most 2*sqrt(a[idx]) elements. but practical it is much less.

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

        What a weird solution !

        thank you.

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

    that too, it was the last test! really unfortunate!

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

please update ratings! thank you so much

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

Не люблю моменты когда не проходит по времени только из-за того, что поставил long long вместо int!

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

    Просто в этой задаче можно обойтись без сортировки 8 миллионов чисел — тогда даже на Java все спокойно зайдет за 78мс.

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

Вот интересно, сколько человек в A div 1 решала задачу, которая написана в условии, т.е. с ограничением x ≤ y, z ≤ t? Это ограничение ведь читается как x ≤  y; x ≤  z; y ≤  t; z ≤ t!

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

    Автор явно не читал это.

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

    Кстати, да, запятая шрифта формулы, а не текста :) !

    x ≤ y, z ≤ t (всё в одних долларах)

    x ≤ y, z ≤ t (две формулы в разных долларах — более правильный вариант)

    В PDF-ке после текстовой запятой пробел между формулами был бы ощутимо больше, но для HTML «правильный» вариант тоже плохо подходит, его трудно отличить. Лучше вставлять какой-нибудь текст — или точку с запятой, как советует droptable.

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

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

    Ух, да, вы правы. Но, надеюсь, никто так не воспринял.

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

I hope Petr rise again :)

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

:)

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

I just found the "problem revision"(30) in the detailed submission page.
But What is the problem revision? Thanks for help!

Problem Lang Verdict
365D — 30 GNU C++ Wrong answer on test 8

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

This contest is very great, with so many rand() needed and some hard problems :-P

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

Задачи были интересными! Автор ждем от тебя еще контестов...

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

Editorials please !! :)

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

hi everyone, for problem B,

why this verdict???

1 1000 Answer 1 Checker Log wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements

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

Could anyone have a look on my submission 5162269 for Matrix problem? I don't understand why I am getting a run time error...

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
      if(a%(it->first) ==0 && m.find(a/(it->first))!=m.end() ){
    

    It looks like you divide by zero in this string.

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

    i think it maybe because you are trying to compute a%(it->first) and a/(it->first), but the value of it->first maybe zero if the string contains a 0 character.

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

Thanks for the contest, Finally I became blue!! :D ..

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

at the very beginning i got problem A,B done within half an hour while just before the contest end,i wrongly took the lower bound of ai as 0 and think i may be able to hack some careless guys who also didnt handle the data 0,so i quickly submitted problem A again with speical judgement for the case when ai is 0,...then the system reply tell me ai must be >= 1.and my rank in room suddenly drop from 8 to 16.. it really proves that evil will be rewarded with evil.ToT

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

A and B 's very easy. But C 's so hard. (Just with me :) )

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

i liked the problems, though i could not participate

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

Is there someone fix the description of problem D. Free Market? How to understand this statements: "Note that each item is one of a kind and that means that you cannot exchange set {a, b} for set {v, a}. However, you can always exchange set x for any set y, unless there is item p, such that p occurs in x and p occurs in y.". For the samples, second one, why 2 days? one change a day, at least three days? input 3 5 1 2 3 output 6 2

How could those get AC?

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

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

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

+

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

I look forward to editorial

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

Thanks for beautiful problems.I enjoyed so much :)

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

Unbelievably lucky! lovelymoon's (div1 winner) E problem takes 11996 ms (TL is 12s) on the maximum test case :)