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

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

Всем привет!

Сегодня в 19:30 по Московскому времени состоится 140-й раунд Codeforces. Соревнование пройдет в обоих дивизионах.

Автором задач сегодняшнего раунда являюсь я, Илья Малиновский, студент 1-го курса мат-меха СПбГУ. Это мой первый контест на Codeforces.

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

Участникам предстоит традиционно выступить в роли спасителей всех и вся от разнообразных бед и невзгод. У вас будет два часа на то, чтобы помочь былинному богатырю, инопланетянину, благородному рыцарю и другим персонажам. Кроме того, в одной из задач найдется место и антагонистам: в их роли выступят коварные кучки камней...

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

Успехов!

P.S. Информация о разбалловке появится незадолго до начала раунда.

upd. Разбалловка стандартная в обоих дивизионах.

upd 2 Раунд завершён!

Поздравляем победителей!

div1:

  1. peter50216

  2. Dmitry_Egorov

  3. Egor

  4. RAVEman

  5. bmerry

У победителей по 3-4 задачи. Задача E не покорилась ни одному участнику.

div2:

  1. Velicue (он единственный в дивизионе сдал все 5 задач)

  2. Frommi

  3. Aerolight

  4. Shahriar_sust

  5. bzdbz

Всем спасибо за участие! Надеюсь, в целом все понравилось. До новых встреч!

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

Полный разбор

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

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

Вы вообще офигели кто минусует меня, тупые свиньии.

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

     

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

    Непонятно почему его заминусовали. Вроде ничего такого не написал

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

      Ничего такого не написал, вот и заминусовали

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

        Написал, что ничего такого не написал, и заминусовали, и заминусовали.
        OH SHI

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

          Abra какая-то получается.

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

          Настроение у всех осеннее: вот у меня, например, уже три дня дождик накрапывает и тучи на все небо. Минусуя, все так прощаются с летом)

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

            Поэт что-ли?

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

              Ага) Пушкин) - ...Дни поздней осени бранят обыкновенно, - Но мне она мила, читатель дорогой, - Красою тихою, блистающей смиренно. - Так нелюбимое дитя в семье родной - К себе меня влечет. Сказать вам откровенно, - Из годовых времен я рад лишь ей одной, - В ней много доброго; любовник не тщеславный, - Я нечто в ней нашел мечтою своенравной...

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

"Сегодня в 19:30 по Московскому времени" — по-возможности нельзя ли пожалуйста указывать к какому дню относится "сегодня". Я понимаю что в большинстве случаев это можно вычислить по дате поста... Которая выглядит как "столько-то часов назад"... Но всё же. ;-)

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

    Если навести курсор на "столько-то часов назад" — всё станет понятно.

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

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

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

// Информация о разбалловке появится незадолго до начала раунда.

А почему так?

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

Осенний пессимизм на КФ — положительный пост с пожеланиями успехов заминусовали, а пожелания слить рейтинг — +25

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

    я может быть понял

    Здесь сливаются любые посты, кроме: 1) нормально-средних шуточек-прибауточек 2) постов красных (не видел ни разу, чтобы красных именно слили; может, так бывает, но это скорее исключение) 3) нормально-средних вопросов/ответов участников

    А вот посты с пожеланиями удачи минусуются вне зависимости от того, какое количество няшности автор в него вложил)

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

      4) Шутки про JKeeJ1e30

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

      Просто если каждый из 2000+ зарегистрировавшихся участников напишет один коммент "Good Luck & Have Fun", то ленту будет невозможно читать. На TopCoder'е пишут такие сообщение, потому что каждое из них содержится в своей комнате.

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

Вопрос по системе в целом: доступна ли эта фича сайта во время соревнования?

P.S. Да, абсолютно верное решение всегда проходит по времени с запасом и эта фича не нужна. :)

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

I have a question. In round #138 they explicitly said that "D language will not be available on this contest.". In the emails I get I don't ever see it mentioned in the list of available languages. What's up with that? :)

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

    You may use it on your own risk. We will announce official support after we will be sure that everything is OK.

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

Attention CHelper users. Codeforces for whatever reason slightly changed task pages format (capitalizing some tags) rendering CHelper not possible to parse tasks. Please update your plugins through File->Settings...->Plugins, right click on CHelper->Update plugin


Пользователи CHelper, Codeforces по какой-то причине слегка изменил формат страниц с задачами (некоторые теги стали большими буквами). Старая версия CHelper не может их распарсить. Обновите плагин через File->Settings...->Plugins, правый клик по CHelper->Update plugin

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

I have the impression that today... tourist, again surpass the 3000 points ... A new range? Something like Intergalactic Grandmaster? LOL

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

Читайте спойлер!!!!!

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

Can somebody explain C. I can't understand it :(

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

why my C got wrong answer at pretest 1? I already same as the sample IO

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

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

p.s писать ответ надо в standard.output или в standard output?

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

    Без файлов надо сдавать)

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

      О_о спасибо, просветил)

      всёравно падает(

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

        у тебя проблема в том что решение А отправил за В

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

          Программа называется A)) а на самом деле это В) Но возможно , что моя программа просто плоха

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

    Все вопросы надо задавать авторам через кнопку "задать вопрос" на странице со списком задач внизу.

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

Anyone search ideas from Google for E(Div 2)/C(Div 1) like me?

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

    We can use fact, that gcd(Fibx, Fiby) = Fibgcd(x, y). But I have still no correct idea how to get subset with maximal gcd(since binary search is wrong).

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
      def d_down( r,l,k ):
        d = (r-l)/(k-1)                                    ### 1 below
        while d > 1:                                       ### 4 below
          if (1+(r/d)-((l+d-1)/d))>=k: return d            ### 2 below
          N = 1 + (r/d)                                    ### 3.2 below
          d -= ( ((N*d)-r) + (N-1) ) / N                   ### 3.4 below
        return 1
      
      """
      basically` 
      1) (r-l)/(k-1) is the maximum possible d, given r, l and k
      2) the if...return tests if k d's fit between l and r
      3) if not, then d must decrease; can't loop decrement (d-=1) with 1E12 ranges, so
      3.1) R = d * (1 + r/d) is a multiple of d greater than r, and
      3.2) N = (1 + r/d) is the multiplier of d that gets to that R = N*d, so
      3.3) (N*d - r) is how far R has to drop to be <= r, so
      3.4) ((N*d-r) + (N-1)) / N is the minimum decrease in d which will drop R to <= r
      4) go back to 2) above, with decreased, new d
      
      e.g. input m,101,200,2  (answer is 66: *2=132; *3=198)
      
      Initial d = 200 - 101 = 99
      but only one multiple of 99 between 101 and 200 inclusive, i.e. 198
      
             101                       200                    ## boundaries r and l
           99                       198              297      ## multiples of max possible d; R=297; N=3
      
      and if you start decreasing d from 99, then
      
        98                      196              294           ## multiples of d-1
      97                    194               291              ## multiples of d-2
      ...
      

      so, as d decrements, the numbers on the right (3*d) move faster (3x decrease in d) to get inside 200 than the numbers in the middle (2*d) move to go past 101 (2x decrease in d). the number on the right reaches (or passes) r when 3*d <= 200 i.e. the decrease in d will be the formula in 3.4 above i.e. ( (3*99 — 200) + (3-1) ) / 3 = 33.

      the only question is whether 2*d has by that time dropped below l (101), but if it has then repeat the loop.

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

        If you want ugly, it's only 11 lines of python:

        import sys
        def recfib(n,m):
          if n==0: return (0,1,)
          a, b = recfib(n / 2,m)
          return ( [ a*(((2*b)-a)%m), ((b*b)%m)+((a*a)%m)][n%2], [ ((b*b)%m)+((a*a)%m), b*((2*a+b)%m)][n%2], )
        m,l,r,k = map( int, sys.stdin.readline().strip().split()[:4] )
        D = (r-l)/(k-1)
        while D > 1 and (1+(r/D)-((l+D-1)/D))<k:
          N = 1 + (r/D)
          D -= ( ((N*D)-r) + (N-1) ) / N
        print( recfib( D, m)[0] )
        

        only four lines implement the algorithm for the fib. index, the rest is i/o (3 lines) and the index-to-fib# function.

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

          Nice solution! Can you explain that the meaning of (a, b) in a, b = recfib(n, m)

          I guess a is the n(th) fib number. But what's b?

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

          Your code cannot pass the tests. You put the '%m' in wrong places. After my modification it passed.

          And, spliting the long long return statement in recfib using the V1 if C else V2 expression would make the code faster, since that can supress the useless evaluation.

              return ((b*b+a*a)%m, b*(2*a+b)%m) if n%2 else (a*((2*b)-a)%m, ((b*b+a*a))%m)
          

          See, it's only 80 chars. You don't even need to break the line.

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

            Thanks, you are right, I forgot about the ternary operator added in 2.5 that will short-circuit to evaluate just one of the paths. I just read about it the other day, too.

            And yes, the version I posted is not the one that worked: I added %m's after the [n%2] selectors in the return statement and it passed. Actually, your version may not pass if, for example, (b*b+a*a) overflows. Ihat's why I put so many %m ops in there. And I still think either mine or yours could fail if given the right parameters; using this construct ((VALUE%m)+m)%m) a few times should fix it though. Python may be hiding some of our problems and be more robust here because of automatic type promotion on overflow.

            Btw, I got it down to 10 lines (raw_input() instead of "import sys" & sys.stdin.readline()). That uses the ugly return construct, but the important thing to note is that the guts of the program, the GCD loop, only takes four lines.

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

              Actually, you don't need so many '%m' in python. For example, it will convert to long for you automatically if a*a+b*b run out of the range of int. And -1 % 5 == 4 in python.

              Btw, after I copy your code to my editor, the first thing I do is to remove the import line and replace sys.stdin... by raw_input().split().

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

                thanks.

                i know python promotes the type on overflow, i'm just cautious and then i don't have to think about the range of m.

                and thanks for the raw_input() thing; i know it's there but i think that changes or breaks in V3 so i tend to not use it a lot; again, i'm cautious.

                i didn't know % alway goes to a positive number; i started doing the extra +m)%m in C++. but since that's the case then even overflows are not a problem.

                hey, could the %m generate a premature n==0 in the recursive fib routine? would it matter?

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

                  The first argument of recfib, namely n, will not affected by m.

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

          2251104 Even shorter(7 lines) with functional style. Accepted.

          def recfib(n,m):
              if n == 0: return (0, 1)
              a, b = recfib(n / 2,m)
              return ((b*b+a*a)%m, b*(2*a+b)%m) if n%2 else (a*((2*b)-a)%m, ((b*b+a*a))%m)
          def next_d(D): return D if 1+r/D-(l+D-1)/D>=k else next_d(D-(D-r%D+r/D)/(1+r/D))
          m, l, r, k = map(long, raw_input().split())
          print recfib(next_d((r-l)/(k-1)), m)[0]
          
          # Trick to remove N from the code: N = 1 + r / D
          # D -= (N*D-r + N - 1)/N
          #   N*D - r = (D + r - r % D - r) = (D - r % D)
          #   N*D - r + N - 1 = D - r % D + r / D
          
          
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        A really nice solution Thank you !

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

Как решать div2 D?

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

Задача C великолепна) Давно уже стольких эмоций от взломов не получал. Для всех интересующихся что же не так — бинпоиск не работает ни в каком виде. Тест — 123456789 100000000000 300000000000 3

P.s. В целом задачи очень интересные, один из немногих раундов, где действительно надо думать, а не просто тупо писать километры кода.

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

    А как делать без бинпоиска-то?

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

      Дождитесь разбора: сегодня-завтра он появится.

      На "подумать": асимптотика авторского решения —

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

    А как тогда делать?

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

      Можна приблизительно оценить g = gcd(i1,i2,..,ik). Если g < 1000000 ,то перебрать его. Если g > 1000000, то оно в виде r/i (целая часть).

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

        не очень понял, можете конкретнее?

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

          g — такое число, что F(g) — ответ.

          Тогда приблизительно считаем g. Например g = (r — l) / k;

          Если ето число меньше 1000000, то перебираем все числа от 1 до 10^7(c запасом) и выбираем наибольшее для которого выполняеться условие.

          Если ето число больше 1000000, то g должно быть у виде r / i , потому что r / (i + 1) должно быть меньше r/i. Перебираем i от 1 до 10^7.

          Но я сам еще не уверен:)

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

            На контесте упало, потому что я баран. А вообще прошло. код

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

      Я делал так — будем постепенно уменьшать это число (пусть x). Изначально оцениваем, что оно не более r / k. b = (l — 1) / x. Теперь оцениваем x как не более r / (k + b). Снова b = (l — 1) / x и так, пока не сойдется. Не уверен, что это проходит, но у меня решение упадет независимо от

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

      ^^^ Это решение проходит за 140 мс

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

    Это неэкономно. Я вот сначала клиентов обрабатывал тестом 66 99 2, а когда они добавляли "поискать рядом с ответом из бинпоиска" — уже добивал 666666666666 999999999999 2. У меня, правда, у самого упадет из-за того, что забыл сделать 1 % mod

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

      Это уже совсем манчкинство) Но тут тогда надо внимательно действовать — люди, почему-то, по большей части писать бинпоиск не умеют, у них очень часто вылезают какие-то +-единички, крайние случаи и т.д. и т.п., можно случайно нарваться на это. Не хотел тратить время, думал, может оно еще пригодиться в E, но ничего лучше хэви-лайта не пришло в голову.

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

    ответ то какой? еще лучше нод

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

    А что же всё-таки нужно делать в том месте, где половина участников сделала двоичный поиск?

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

      Ответ имеет вид [r/z], где z — какое-то целое число. Либо z<=2e6, либо [r/z]<=2e6. Перебрали, выбрали наибольшее.

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

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

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

    В этом тесте ответ 57272247?

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

С(Div 2) прям на второй странице гугла. Пичаль :-(

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

    Как сложно определить тех, кто вместо решения ищет все в гугле...

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

классный контест. как решать Б, и на чем ломали С?

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

    В Б прошла следующая штука:
    Для k = 1 ответ очевиден, сразу посчитаем его за линию.
    Для k > 1 посмотрим, что нам будет нужно как максимум 1 кучку ни к кому не подцеплять, как максимум k кучек подцеплять один раз, и как максимум k^x кучек подцеплять x раз(из них все кроме одного непосредственно). Каждое подцепление добавляет ровно массу кучки к ответу.
    Отсортируем массив по невозрастанию и первый элемент добавим с множителем 0, следующие k с множителем 1, следующие k^2 с множителем 2 и т.д. Если будем считать ответ на подотрезке за O(1) суммами на префиксах, то итого выйдет что-то вроде logkn.

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

мне кажется, или Д уже бывала на контестах?

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

Расскажите пожалуйста решение Div 1 D

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

    Кстати, вот она.
    Ищем отрицательную строку/столбец, меняем, пока всё плохо. Это работает, так как сумма всех чисел в матрице от этого каждый раз растёт. Надеюсь работает..

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

Во время решения задачи С из этого контеста у меня возникла следующая подзадача: Найти наибольшее x такое что на отрезке с l по r есть не менее k чисел кратных x. Я умею решать такую подзадачу за O( sqrt(r) ). Можно ли быстрее?

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

    бред

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

      Это boolen значение, мне надо f(l, r, k) -  > x т.е. функцию в целые числа.

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

        забей, я вопроса не понял

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

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

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

          Невзломанный бинпоиск — это не ваша заслуга, а наша недоработка)

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

In my opinion, these OEIS problems don't add anything to the contest.

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

    Well I did it figuring out on paper and still made a noobie mistake.

    ((3^n — 1)+MOD)%MOD is the answer. I guess you never forget to do this once you lose 900points. >_<

    (I did the 3^n part efficiently and correctly)

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

      Same method but WAed!

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

      Maybe you CAN figure it out on paper but it's so much faster this way... so you have to take the easy way to stay ahead of competition.

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
        F(N) = 3*F(N-1) + 2
        
        F(1) = 2
        F(2) = 3*F(1) + 2
        F(2) = 3*2 + 2
        F(2) = 3*2 + 3 - 1
        F(2) = 3 (2+1) - 1
        F(2) = 3^2 - 1
        ...
        F(N) = 3^N - 1
        

        Took me a bit to turn the 2 into a 3-1 though :( I'm out of practice.

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

        I disagree, realizing the solution required a little thinking, and it wasn't some obscure formula or some numbers that are hard to compute. I even think that for some it was even faster thinking about the solution. If you don't try to think the easy problems, how do you expect being able to think the hard ones? That's the way you'll stay ahead, thinking

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

      Indeed, I forgot to write +MOD thing and lock my problem like a fool... 900 points lost will be a real tragedy.

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

    The fun part is not using OEIS. I think it was a nice problem

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

    [PlayLikeNeverB4: In my opinion]

    See my comment below re normative. I'm not sure if you are referring to Div-2/C or /E, but I thought they were great problems. A bit of knowledge, or maybe a chat with the Google, a little insight, and then coding it right, which was the real challenge in both cases to avoid the TLE, and WA if the modulo operation is not done right.

    The OEIS is just the turf on which the game i played. Think of yourself as TRON.

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

Повёлся на то, что C(Div1) сдают больше чем B. Своими руками нашёл способ вычисления номера числа Фибоначчи, которое окажется ответом на задачу (если я не ошибся нигде, конечно). Вот только вычисление Fn быстрее чем за О(n) мне оказалось не под силу, а копипастить нагугленный чужой малопонятный код счёл нечестным.

Вопрос: есть ли решение задачи без вычисления Fn с помощью матриц?

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

    Ответ на вопрос: есть формула Бине, она задает i-ое число Фибоначчи в явном виде, но для ее использования нужна высокоточная дробная длинка, да и по модулю ее вычислить нельзя.

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

      Такой способ мне известен. Но вы сами только что объяснили, почему он не подходит ^_^

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

I can't understand, why my O(8log(10^12)) got TL. Submission #2245668 ?

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

    Well, for Problem B(div1)/D(div2), you will get TLE if you don’t use some technique to remember the answer you printed each time. This is because there exists cases that all k equal to 1. That's how I got TLE for the first time.

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

Problem E in div2 is quite tricky...when I realized what i had done wrong it's all too late. congrats to those who solved this problem successfully.

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

Долго ещё ждать системное тестирование?

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

Е скучная — напишите HL декомпозицию с бинарным поиском за n log^2 n вместо n log^(3+) n. Остальные задачи зачотные, но С, конечно, не на своем месте с такими претестами

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

    Можно без декомпозиции, с персистентным деревом отрезков. Это заметно короче, и с большим запасом укладывается в TL.

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

      Тогда тоже клевая задачка. Жаль, что я не придумал. А кстати, так ведь можно любую HL декомпозицию, где нету изменений. Клево

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

Расскажите решение задачи C div 2

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

    Ответ: (3^N — 1) % M. 3^N считаем бинарным возведением в степень

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

    Если почертить, то становится понятно, что состояний всего 3N, следовательно, переходов будет сделано 3N - 1. Осталось только прикрутить к этому быстрое возведение в степень, взятие по модулю и грамотное по модулю вычитание. Как сделать первое, описано, например, здесь, взятие по модулю вставляется после каждой операции умножения, а грамотное вычитание описывается так: res = (pow(n) + m - 1)modm.

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

Никто не знает, что будет, если был зарегистрированный, но не получилось прийти и не сделал ни одной отправки?

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

How can we solve DIV 2 E ? How can we get the maximum gcd of all the k element subsets between L and R ?

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

Блин, делать модуль равный единице в задачах на ответ по модулю вообще не клево. =(

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

Anyone thinks that A in Div2 is more difficult than B?

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

    Solution in one phrase : cross product. Without that it'll be a bit troublesome.

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

      I did take out cross products but got WA on test 31 .[code] .. Can anyone tell me what did I do wrong because I cannot see the test case until the system test is over ... And the system test is playing with my patience by being slow

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

    I do, but only because I suck in geomtry.

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

    Well, I don't know cross product but managed to get AC by writing several ifs. It's easier since it's guaranteed that ABC makes up either right angle or straight line

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

The problemsets are good, thanks, Malinovsky239. However, some statement clarifications are wanted. Thanks for any reply.

div2(D)/div1(B):

"each pile will let you add to it not more than k times (after that it can only be added to another pile)". Assuming adding pile i to pile j, we name i as addend, j as summand, then is the constraint saying which role(addend or summand) can be used at most k times?

div2(E)/div1(C):

"for each such subset let's find the largest common divisor of Fibonacci numbers with indexes", does this refers to the elements of subsets indexing at 1,2,3,5,8...?

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

Binary search in Div1.C is incorrect :(
l=7, r=14, k=2:
7 — ok
6 — not

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

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

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

    Неожиданное совпадение!

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

    На самом деле случайно. Я не ожидал, что так получится. Задачу я раньше не видел. Перед тем как её утвердить я погуглил, но этой задачи не нашел. Мои извинения за недоработку.

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

      Да и первая задача с А дива2.

      Линк.

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

        Некоторые неудачники, не будем показывать пальцем, хотя я, конечно, имею в виду себя, умудрились и это решение зафэйлить. Никак не могу понять, что не так. Всё в long делалось, естественно.

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

          Тыц
          Задачу не читал; первое, что пришло в голову.

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

          На данной платформе long тоже имеет длину 32 бита, а вот long long — 64.

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

            Печаль. Большой печаль. Спасибо ответившим.

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

      Конечно случайно, никогда бы не подумал, что на кф дают специально свеченные задачи)))

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

Message received from user "messsi" during todays contest:

"

send me you code of A please man and i send me code of B ok???? this is my code of B now you send me your code please

/* His problem b code here.. */

"

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

Всё-таки по-моему давать задачей A во втором дивизионе геометрию, это как-то жестоко.

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

Вот это жесть... в D у меня прошел тупой рандом. Пока есть плохие линии (ряды или колонки) берем из них случайную и ее минусуем. Это самая простая задача сета :)

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

    Ну это почти авторское решение ;)

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

    Это правильно.

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

      "в D у меня прошел тупой рандом" ... "Это правильно." — вот она, вся суть некоторых задач.

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

    1. Утверждение: этот процесс сходится.

    Рассмотрим общую сумму элементов матрицы. Она может быть вычислена как сумма сумм всех строк (столбцов). Очевидно, что изменение знака с отрицательного на положительный увеличивает сумму всех строк (столбцов).

    2. Этот процесс сходится быстро.

    Всего существует не более 10^6 + 1 различных возможных сумм (максимальная сумма 10^6 по модулю, четность сохраняется). Итого это точно работает не дольше, чем за 10^6 операций. Если каждая операция реализована за O(max(N,M)) (это легко), получаем сложность 10^8 -- OK.

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

      3) Этот процесс сходится очень быстро, либо тесты слабые

      У меня каждая операция реализована за O(N*M) и все равно — ОК

      4) Задача не стоит 2000 баллов

      Прямое следствие 1.-3.

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

        3) Даже чтобы получить 10^5/2 (оценочная граница захода N*M) итераций, нужно непонятно какую матрицу сделать. Ограничение 10^6 исходит из плохо совместимых утверждений: все числа порядка 100 и при этом отрицательные суммы порядка -1.

        4) Оценка субъективна. В целом — не очень понятно, как оценивать сложность решения задачи, когда доказательство того, что решение правильно, сложнее идеи решения. ИМХО — да, эта задача не стоит 2000.

        Кстати, в решении жуткие мотивы холодильника из братьев пилотов, правда, я не умею там доказывать аналогичную эвристику "срисовать и протыкать все неправильные; повторять до посинения", а правильное решение вообще строится из специфического инварианта.

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

Классно то, что впервые за последние N контестов не было задержки на 15 минут)

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

Using "int" instead of long long caused system test fail (A. div 2) :(

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

ждем обновления рейтинга

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

Based on the number of people solving, C and D should be exchanged their order in Div 1.

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

also in Div. 2 , A and B should change their order based on difficulty level or no. of people solved.

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

    No, binary search and sorting are more difficult than school geometry.

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

      I suck at geometry and honestly I don't really like it either. And like me are a lot of Div2 participants.

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

        maybe, be we all suck at something. i had no idea about the GCD(FIB(N),FIB(M)) = FIB(GCD(N,M)) thing, but a quick google of GCD and fibonacci, plus a bit of number sense, and I was five minutes from being only the second Div-2 participant to solve E during the contest (it was trivially solved in my mind once I talked to the Google). At the same time, I still don't have a clue how to approach the lower-rated Div-2/D (I know it's probably DP from looking at others' code but the application of DP is still somewhat of a black art to me). I know you (Play...B4) have number sense because of your F(N)=3^n-1 derivation for Div-2/C, so you could have been one conversation with the Google away from solving E, too.

        So what PlayLikeNeverB4 is saying is that PlayLikeNeverB4 is normative — "... and like me are lot of Div2 participants." I am Div2 and have been doing geometry almost daily for at least of couple of dozen years. That was a trivial problem to me, but I understand that not everyone has the same strengths. But if you have been doing this for a number of years and haven't at least spent the time to understand some basic geometry (cross- and dot-product problems are not at all rare), then you will always be Div-2 (like me: DP is my insurmountable hurdle, apparently).

        And bilbo1 may be saying that bilbo1 is normative.

        The original posts, "Based on the number of people solving, ..." are probably the closest to stating what is actually normative, but people that do programming contests are self-selecting so even that sampling is suspect.

        What I would like to say is that Malinovsky239 made up an excellent problem set (with the difficulty ratings based on assuming Malinovsky239 is normative?;-) and second-guessing the difficulty level is a bit impolite without at least complimenting the problemset author on a job well done.

        Make up your own problem set and then see how you feel when people comment about the ratings.

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

      Но в задаче B не нужно ни то, ни другое=)

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

s

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

I always receive mails from codeforces after the contest is over! Can anyone tell me what needs to be done to correct this. And the delay is not of about two hours which is the difference between my and codeforces timezone but instead I receive mails on the next day.

Sorry if this does not belong here. Thanks

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

Извините не по теме у меня такая проблема. Уведомления о проведении олимпиад на Codeforces приходят на мою почту после начала олимпиады. Например: последний олимп был вчера вечером, а сообщение пришло сегодня утром. Может кто-нибудь помочь? Заранее спасибо

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

Where can I find English editorial?

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

@Mike: I can't understand the solution to problem D Div 2 :Please can you write more elaborate reasoning for your solution