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

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

Всем привет!

Очень скоро, 25 апреля в 19:30 MSK, состоится очередной Codeforces Round #181 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Задачи были подготовлены группой авторов в составе: Гриднев Виталий (gridnevvvit), Игнатьев Александр (aiMR). Выражаем благодарность Геральду Агапову(Gerald) за помощь в подготовке задач, Михаилу Мирзаянову(MikeMirzayanov) за замечательные системы Codeforces и Polygon, Марии Беловой(Delinur) за перевод задач на английский язык.

Немного информации об авторах: я и Александр — студенты 3 курса Механико-Математического факультета Саратовского Государственного Университета. Для нас это первый раунд и, я думаю, что не последний.

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

Также настоятельно рекомендую Вам прочесть условия всех задач!

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

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

UPD1: Разбор задач

UPD2: Соревнование закончено. Поздравляем победителей:

  1. ballmaids02
  2. VIProgrammer
  3. emachaidze
  • Проголосовать: нравится
  • +164
  • Проголосовать: не нравится

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

С дебютом авторов и ВСЕМ удачи! Надеюсь задачи будут как всегда интересные)

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

Can't wait, hopefully it won't be too much maths :D

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

a

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

I think it will be interesting.

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

Good Luck ^_^

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

I hope the system testing starts soon after the contest not like the last contests.

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

    System testing after contest starts when authors of task check all hacks.

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

      I think it's not true because all hacks are checked automatically by validator.

      I suppose that main reason of our waitin' is that validator checks all the hacks.

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

Welcome ! New authors always have interesting problems I think today it will be too :)

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

One of the best announcements I ever read !!

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

i hope today will be my day :))

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

gl & hf all! :)

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

Еще полгода назад я и не знал о таком сайте, как codeforces. Очень часто в контестах встречаются интересные задачи, способствующие развитию мышления. Я уже в нескольких контестах принимал участие, разумеется, с удовольствием приму участие и в этом контесте. Спасибо авторам за подготовленный контест. Всем успехов!

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

    Он был бы ещё более замечательным, если б тут не минусовали любой попавшийся коммент, как твой)

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

      Абсолютно согласен. Я вчера вопрос задал и мне 65 лайков наставили:)

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

Сегодня состоится 181 раунд codeforces, я как участник этой олимпиады, готов участвовать в нем.

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

Саратовске ребята всегда готовят хорошие задачи. Удачного контеста всем...!!!

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

Главное чтобы не "первый блин комом" :)

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

This is my first contest in codeforces, hope i can solve some problems in the contest

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

Hello, I'm Commander Sheppard and this is my first contest on Codeforces!

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

ой кого-то забанят...

17 	boy_boy10 	0
18 	boy_boy9 	0
19 	boy_boy8 	0
...
»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hope to solve at least 3 problems :)

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

what'er pity not joinning this contest= =..dynamic scoring could be really exciting and fun T____T...hope to reach 1700 T_T

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

WTF???
UPD: he has already -179 hacks...
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Codeforces was down. But how could lrb know about it? He was sure that the solution was incorrect. He pressed and pressed the button Hack! but nothing was happening. "Ok, I'm going to count how many times I pressed that damned button!", he thought: "66, 67, 68! Codeforces is available again! Let's see where my +100 points are..."

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

    Now he has 215 unsuccessful hacks

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

    Психанул!)

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

    When I saw that lrb wanted to hack my code my heart started boom boom boom:)I thought that my solution is wrong:)but when i saw that he has more than 100 unsuccessful hacks i understood that he want to break record and i calmed down:)

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

    우리의 위대한 지도자 김 장군의 명예에, 나는 미국 제국주의를 정복 할 수있을만큼 우리 민족 강하게 만들기 위하여 열심히 컴퓨터 과학을 공부합니다!

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

what is the 5th test in B problem??? "@

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

Как всегда, узнаю о контесте когда он уже идет или прошел...

А задача D мне нравится. Почему ее так плохо решают? ..(

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

Hey, really enjoyed this competition, but i got a little problem with problem C. So im asking you for little help.

Here is what i came up with: We generate all possible sums ( highest possible sum has 6 digits ) and make equation

N = x*a + y*b, where N is our sum ( we do this with every generated sum ).

And we find number of solutions to this equation that: x>0, y>0 and a+b<=N ( it's pretty

clear ).

For most of my time i was trying to come up with some nice dp solution, but it turned

out to be impossible for me... If it's one right solution desribed above, then please explain to me how to calculate

those all solutions nicely?? Because for me it got too messy and i finished with only 2

first tasks :(

:) Thanks in advance

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

    I think that answer is sum(C(n, x)) if N = x*a +y*b is good, but there is small problem for me, how fast and correct calc C) Sorry for my bad english.

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

    n!/(x!*y!) — number of different numbers of length n and containing x of "a" digits and y of "b" digits.

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

      You can use this : C( n , k ) = n! * pow( (n-k)! * k! , mod-2 )

      from the "Number Theory" : (1 / b) % mod == ( b^(mod-2) ) % mod , because mod is a prime number !

      Sorry for my bad english

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

        i knew there is must be using some number theory, but, sadly after knowing a and b value, i cant compute C(n,a)

        could you explain more with n = 14215 and k = 13517 ?

        thx (taken from test 3 )

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

          only pre-calculate every factorials module 1000000007 and store this numbers in an array .( for example fact array ) this step takes O(N) time and space .

          then C( n , k ) = fact[n] * power( fact[k] , mod-2 ) * power( fact[n-k] , mod-2 ) . this step takes O( Log N ) .

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

            or calculating c(n,k) using c(n,k-1) c(n,k) = c(n,k-1)*(n-k+1)/(k)

            but as Reza said, we have to pre-caculate them.

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

              actually this wont work !

              because there is no necessity that c(n,k-1)%MOD or (n-k+1) is divisible by k.

              this will lead you to WA.

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

                of course!

                i didn't mention that for dividing u need to use modular division, i just said that this is another way tu calculate c(n,k)...

                for dividing u can use pow(k, mod-2)(as Reza said) or use Extended Euclid algorithm :

                // ax + by = gcd(a,b) = d
                void eea(int a, int b, int& x, int& y, int& d) {
                    if (!b) {x = 1; y = 0; d = a; return; }
                    eea(b, a % b, x, y, d);
                    int x1 = y, y1 = x - (a / b) * y;
                    x = x1, y = y1;
                }
                int divide(int a, int b) {
                    int d, x, y;
                    eea(b, MOD, x, y, d);
                    // if(a%d==0)
                    return ((x+MOD)*(a/d)) % (MOD/d);
                    // else   "no quotient"
                }
                

                both run in O(logn) time. however, pow(k,mod-2) is a lot easier... ;)

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

        "from the "Number Theory" : (1 / b) % mod == ( b^(mod-2) ) % mod , because mod is a prime number !"

        Could you provide references to this proof?

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

          from "fermet's little theorem" : a^(p-1) % p = 1

          thus a * a^(p-2) % p = 1 and a % p == a^(p-2) % p from other view a * ( 1/a ) % p = 1 and a % p == (1/a) % p

          finally : (1/a) % p == a^(p-2) % p

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

    the same idea, but a little bit differences. x is the number of digits a still have sum=a*x+b*(n-x) (a,b from input), for each single value of x, i check whether sum is a good number. if yes, calculate number of numbers you can create with that.

    the only problem that i had is the final step.

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

Хорошо! Понравилось решать задачи) Спасибо очень хороший контест gridnevvvit :)

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

Как решалась Е?

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

Но, естественно, разложение произведения чисел из ввода требует O(k * p * log a), что всё-таки слишком много.

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

    Всё верно, основная задача посчитать степени простых в знаменатели, а сделать это можно с помощью решета, которое находит наименьший простой делитель числа. Когда мы все найдём, то для каждого числа от 1 до максимального а, посчитаем сколько раз оно войдёт в знаменатель, это просто кол-во чисел а, больше либо равных данного, а далее факторизируем его за О(кол-ва простых делителей). В сумме для всех чисел от 1 до 10 в 7 это работает быстро

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

      Красиво)

      Мой вариант, немного извращенный:

      Посчитаем num[i] — сколько чисел i было в инпуте, на основании этого s[i] — сколько чисел в инпуте не больше i.

      Теперь для каждого простого числа будем определять его степень в знаменателе. Как мы это делаем? Пусть наше число k. Рассмотрим все интервалы вида pk...pk+k-1, т.е. все интервалы чисел, которые при делении на k дают p, по всем p таким, чтоб интервал влезал в 10 миллионов. Для каждого такого интервала мы можем посчитать, сколько чисел из этого интервала было в инпуте, и для каждого такого числа мы знаем, что при вычислении его факториала мы p раз умножим на число, в разложении которого есть делитель k. Поэтому к степени числа k в знаменателе надо прибавить (s[pk+k-1]-s[pk-1])*p. Теперь нам надо обратить внимание на случаи, когда k входит в разложение в степени >1. Для этого решим аналогичную задачу для k^2, k^3, k^4 и так далее:)

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

        Я думал над таким вариантом, но мне показалось что там просто гигантское кол-во операций получится, а сейчас прикинул, что там сумма ряда даже меньше гармонического) Если только первые степени рассмотреть, то получается n * (1 / 2 + 1 / 3 + 1 / 5 + ...), кстати кто-то в курсе оценок для его суммы, не O(log(log(n))) ли?

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

    Я был очень близок... Как надо осуществлять проверку в бин. поиске?

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

I can't believe that my B is going to fail because I forgot to check if the "connected-team" size is less than or equal to 3, submitted and locked it. Just after I locked it I remembered that. :(

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

Понравилась задача Е Звездные войны еще в моде)

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

не савсем понятна задача D А как она решалась?

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

задачу А не все сдали Просто реализация нечего сложного )

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

    Смешно просто что задачу E не все сдали Просто реализация нечего сложного )

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

Может мне кто-нибудь объяснить 2 вещи. Во-первых, почему в задаче С имеется вот такой вот тест: входные данные 2 3 10 выходные данные 165 Если я правильно понял условие, нужно найти количество "замечательных" чисел длины 10, то есть 10-значных чисел, состоящих из 2 и 3 и имеющих сумму, которая является "хорошим" числом. Ясно, что хорошие числа длины 10 могут иметь сумму от 20 (все двойки) до 30 (все тройки). В диапазоне от 20 до 30 есть только одно хорошее число — 23. Такую сумму имеют числа из 3 троек и 7 двоек. То есть, их количество 10!/(7!*3!)=120. Откуда 165?! Второе: почему в задаче D, в тесте 7 2 нельзя первым шагом выбрать 2-ю строку и 2-й столбец, получит 2 квадрата 1*1 и 5*5 и вторым шагом разбить на квадраты квадрат 5*5. Если можно, то почему ответ на тест 4?! Ответьте кто-нибудь, пожалуйста.

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

I think the problem more difficult than before.. a lot of counter testcase..

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

I loved the contest, especially C, got it accepted at the last minute (stupid overflow mistake :(). This is when you have to love the dynamic scoring :)

Thanks!

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

When is the rating come out??

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

Nice contest, keep up the good work.

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

The problem A — Array in the description it guarantees a correct solution: 1st list -product should be negative 2nd list — product should be positive 3rd list — product should be zero

where as your pretext 3 test case is : Input 5 -1 -2 1 2 0 Output 1 -2 3 -1 1 2 1 0

This is incorrect. List 2 doesn't have a positive product. -1 * 1 * 2 = -2 is NEGATIVE. WRONG TEST CASE.

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

what's the idea of problem D

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

UPD :

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

Расскажите что-то про 3-ий тест в задаче D. Я вижу, у многих ответы как у меня.

Делал так: 1) Для четных — ответ или 1 если k==0, или 0

2) Для нечетных — посчитаем глубину числа — сколько раз его можно делить на квадраты (пока делим на 2 и получаем нечетное число — наращиваем глубину). Далее динамика. В динамкие делим на 4 сына и пробуем перераспределеить действия между 4-мя сыновьями.

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

    У тебя хотя бы 3, а у меня 2) И я толком не могу понять в чем не прав, но смысл такой же: максимальная "глубина" — это кол-во единичек подряд в двоичном представлении начиная с младшего разряда, кроме случая степени двойки минус 1, тогда глубину надо уменьшить на 1. Далее динамика D[k][deep] — кол-во способов разбить квадрат k разрезами с макcимальной глубиной разреза deep, пересчитывается D[k][deep]=D[a][deep-1] * D[b][deep-1]*D[c][deep-1]*D[d][deep-1] | a+b+c+d -1 = k; Чтоб за 3 степень не пересчитывать ещё во второй динамике храним Pr[k][deep] = D[a][deep]*D[k-a][deep];

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

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

      Звучит вроде бы правдоподобно, пока баг не вижу.

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

      Я тут немного подебажил — вроде что-то не так. Смотри, у тебя D[1][2]=2. То есть выходит, что квадрат глубины 2 можно разбить одним разрезом двумя способами.

      Я переделал чуть твое решение — АС.

      3630529

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

        Спасибо, тоже допёр — по несколько раз одни и те же состояния считаю, дал маху)

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

    Для нечётных единица не подходит)
    http://codeforces.com/contest/300/submission/3630176

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

      Уууу, я вообще неправильно высчитывал глубину. Олень — это жизненное призвание.

      Спасибо :)

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

Hey a newbie question but I can't seem to find it in the FAQ or anywhere

How long does it take for ratings to change after a competition?

I go back to sleep right after matches (I'm in Austrlia) so I don't find out.

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

my first contest still rating is not updated ? why always me ?

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

    Your rating will be updated soon..it takes little time to update ratings. Happy coding :)

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

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

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

problems were quite interesting..hope to see your problems again soon.

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

Problems were quite interesting.Hope to see you again soon.

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

Кстати у меня до сих пор стоит баг с рейтингом, рейтинг поднимается когда у меня -37.

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

this round was better than I expect !