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

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

Привет, Codeforces!

10 февраля 2016 года в 18:00 MSK состоится седьмой учебный раунд Educational Codeforces Round 7 для участников из первого и второго дивизионов.

<В прошлый раз эти абзацы всё-таки изменились>

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

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

Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.

</В прошлый раз эти абзацы всё-таки изменились>

Большое спасибо Aleksa Plavsic allllekssssa, который предложил задачи D и E, и Ивану Поповичу NVAL, предложившему задачу F. Также благодарю Mohammad Nematollahi Deemo он предложил задачу, которую мы сильно упростили и решили дать в качестве задачи C.

Подготовкой задач как всегда занимался я (Эдвард Давтян). Благодарю MikeMirzayanov мы вместе придумывали задачи A, B и C. Спасибо Маше Беловой Delinur за проверку английских текстов условий. Также большое спасибо Aleksa Plavsic allllekssssa и Ивану Поповичу NVAL за тестирование задач.

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

Good luck and have fun!

UPD1: Первая фаза соревнования закончена. Можете взламывать решения других участников.

UPD2: Разбор задач готов.

UPD3: Раунд закончен. Результаты окончательные.

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

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

Thanks a lot for the rounds. I like that each problem is meant to illustrate a specific algorithm. I just have one question: Is it possible that you will make educational rounds rated soon? especially that the problems in the last couple rounds are new and not from some previous contests?

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

    Some of the problems were not new.

    Please don't downvote :(

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

      At first it wasn't new, but in the last couple rounds I see the announcement saying that the problems are new. (I think they are new because the announcement started to say the names of people who suggested the problems).

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

        If it's first time you see a problem it doesn't mean it's new or not standard

        and those people who are mentioned in the announcement are just mentioned because they suggested standard problems not original problems

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

          Sorry, but I suggested new and for me not so standard tasks :P

          Normally that doesn't mean someone didn't invent something similar before.

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

            Ok maybe you did, but it's supposed that people suggest standard/old problems not new as it's mentioned in the announement

            If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

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

              I really don't think the quote you mentioned means that the problems were not new. It says if you prepared problems "that you can't use in rounds".

              Sorry for the questions if you don't like it, it represents my opinion only. I just asked because in MikeMirzayanov's first announcement he said that the series will be unrated (for now).

              Unrated (perhaps for now);

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

                it's not that I don't like it I didn't mean to offense, I just wanted to say that the idea of educational round is to present problems that are standard (not like what you said the problems were new), so it can't be rated because of that.

                and about "that you can't used in rounds" I'm not sure what reasons that a problem can't be used in rounds other than because it's already used somewhere or it's too standard

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

                  Well, I can not agree with you :P

                  I had several rounds in the last half year and I can not organize every 15 days one contest. Also I invented a lot of tasks soon(at least 20), so for me it is much easier option giving it now to Edvard which prepares everything and on that way help to CF ;)

                  I know you didn't talk about me, but I suppose here is many guys which will do the same thing!

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

поздравляем за Вашу полностью заслуженную награду! надеюсь, что Ваши тренировочные раунды будут продолжатся! собственно мне они очень нравятся! P.S. у того, кто фотографировал награду хорошая прическа)

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

Thanks Edvard for mentioning me!

I think the task for this round are more 'educational' than any other time :) Also I am sure that everyone will find something interesting and solvable.

About my tasks, I think they aren't standard and I would happy to see such task on some contest where I am participant... Several times they were on line to be used for my regular competition :)

Good luck and any feedback about tasks after round will be valuable :)

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

The Codeforces Educational Rounds was recognized by Snarknews as the best project in competitive programming in 2015 (the picture below is the prize).

Say whaaaat? O.o

Gratz!

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

Поздравляю!

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

The Educational rounds have been excellent in featuring algorithms that are otherwise uncommon. Also, they let contestants experiment with the contest environment without fear of rating deduction, so trying new problem solving sequences and the such. I hope that these rounds will continue to be excellent :D

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

Mathematical problems are the best. kudos to Edvard

I think Educational round is at its best. Don't make it rated as it helps us to do/learn fearless coding at a competitive level. Thanks to MikeMirzayanov for polygon n all. Keep it up guys!

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

Clash with IIIT hyderabad's Codecraft contest tomorrow.

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

clash with IIIT hyderabad, Codecraft contest tomorrow.

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

Thanks a lot for the round Edvard.

I think that the round will be interesting and cool!

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

Codeforces is an amazing community! Like none other. This place is supposed to be competitive, but instead, its such a supportive community. People are not just sharing their knowledge, they're doing so without any immediate tangible incentive in return! May God bless you MikeMirzayanov, may god bless all problem setters, editorialists, people who share their solutions in blogs, coordinators, and everybody involved in the process. Sometimes, people willingly encourage others who feel defeated and demotivated. I think the money the setters earn is nothing compared to what they give, and a lot many people share their approaches without any payment whatsoever. :) I feel humbled by you all, and I feel happy everytime I come here. I wish to become great programmers like you, and also great human beings like you. God bless codeforces!

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

You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

Does this also mean that you can hack a solution to a problem even though your submitted solution to that very problem didn't pass the pretests? Thanks!

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

Я люблю эти раунды.

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

F is really nice! Thanks!

I understand the ideas, but I don't know how to implement them in a beautiful way.

Looking forward to magical implementations.XD

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

    Indeed. I didn't know it was possible to calculate this sum effectively... Until I solved this problem today.

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

    f(n) = 1^k + 2^k + ... + n^k is a polynomial of degree (k + 1). So, using Lagrange's interpolation formula, it's possible to compute f(n) in O(klog(k)).

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

      Why is the sum a polynomial of degree (k + 1)?

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

        See the editorial. It's easy to prove by induction.

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

          Thank you, now it's clear the induction step. I can make this more formally, for those interested. Denote . We want to prove that degree of Pk(n) is k + 1.

          Base case of induction after k:

          By the induction we know that deg(Pk - 1(n)) = k. Taking the derivative of P(1)k(n) = k·Pk - 1(n). This implies that deg(P(1)k(n)) = k

          Therefore deg(Pk(n)) is exactly k + 1.

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

Oh, no... Math.. (((

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

E is really nice!

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

    Thanks for nice words. I tried to contribute cool tasks. At least I hope problems D and E were interesting for solving :) Both tasks are easy for implementation and I will try to invent something similar in future !

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

I want to sincerely thank the problemsetters. Especially the one who set D . I don't remember the last time I saw such a beautiful problem. How brilliant someone has to be to come up with such an elegant problem that can be written in problem statement in such a simple manner !! I am simply awed . Kudos!! :)

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

Только после того, как я с бегу накодил дерево отрезков в С, я понял, какая же простая это задача и как ее решать.

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

    Как?

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

      Моя идея (только что прошли претесты): для каждой позиции считаем положение двух различных ближайших левых чисел

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

    лол, а я тут вообще sqrt-декомпозицию запрогал и получал TLE17:D

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

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

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

        Скорость работы дерева пропорциональна прямоте рук кодера :)

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

          Ну, за чужое дерево не поручусь, но у меня действительно было очень кривое решение за O(Msqrt(N)log(N)), ибо я еще сеты запихивал в идею:D

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

          Видимо, у меня руки зигзагообразные. Как оно у Вас работает в 4 раза быстрее моего? И ~ во столько же раз быстрее моего решения за линию...

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

            Советую попробовать заменить cin/cout на scanf/printf. Мое дерево отрезков это ускорило с TLE20 до AC 280ms.

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

              Спасибо! Всегда думал, что ios::sync_with_stdio(0); решает подобные проблемы, но в этой задаче именно из-за этого TL. То же самое дерево с stdiо получило АС 218ms. Мое решение за линию, кстати, с минимальным отрывом — 187ms. UPD: решение за линию с ios вообще не прошло полный набор тестов

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

                В целом эмпирическое правило примерно следующее: если нужно ввести/вывести больше 500 000 отдельных сущностей — лучше на всякий случай использовать scanf/printf. При этом речь именно об отдельных сущностях — если там одна строка длиной миллион символов, то считается быстро.

                Проблема в том, что операторы >> и << виртуальные, что начинает сказываться при большом количестве вызовов.

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

Idea for D : You want to make d1 = n - 1, d2 = n - 2, ..., dn - 1 = 1 so that the sum is 0. The rest is just experimenting to find the solution.

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

    I knew this idea and yet I couldn't solve :(

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

      One of the key ideas is that d_{n} multiplied by zero, so you can make of it anything you want.

      The pattern for solution is:

      Separate all in three groups: where d_i must be some even constant, where d_i must be some odd constant, and where i == n (you don't care about d_n at all).

      Solution the task for first group it is something like (a b c c b a), you can see that it has exact d_i's as you need (1, 3, 5...).

      To solve for second + third group put n in between of this sequence and append n after (e.g. a b c N c b a N), is has also exact d_i's as you need. (2, 4, 6...)

      (Example ans for n == 4) 1 3 3 1 2 4 2 4

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

Как решать E?

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

    не знаю правильное мое решение или нет, но претесты вроде прошли.

    Я делал так, запускаем дфс из каждого ребенка корня и нахожу для каждого листа этого поддерева кратчайшее расстояние. После этого сортирую вершины по их дистанции и после этого делаю так что все расстояния были различными. Ответ будет максимальное из этих расстояний из каждого поддерева. Почему нам нужно именно кратчайшее расстояние не до корня, потому что в корень мы можем прийти одновременно из все его сыновей.

    Почему это может работать,жадно вначале поднимаем всех тех,кто ближе. И если есть свободное окно поднимаем еще кого-то.

    ссылка на код Your text to link here...

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

Educational Rounds are very helpful in learning new concepts and revising old concepts.

Thanks for Educational Rounds. Keep it unrated.

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

How to hack other people? Can i lock the submission now, if I didn't do it earlier?

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

How to solve C?

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

    one way is to split array in sqrt(n) blocks. for each block, you keep an set and do binary search on it

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

    You can do some pre-processing.
    For each position, store the position of the next number that is not equal to it.
    Just traverse the array from right to left
    if array[i + 1] != ar[i] , then nextUnequal[i] = i + 1
    else nextUnequal[i] = nextUnequal[i + 1]
    Now when you have a query(L,R,X) check A[L] if it's not equal to X, return L otherwise look at nextUnequal[L] if that's <= R, return that else return -1

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

      It takes intelligence to see the simplicity in something complex. I was so sure this is segment tree problem, and later thought of sqrt-decomposition solution lol.

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

    For each index of the array keep the index of the next element which is not equal to current.
    Then the answer for query can be obtained like this:
    1. if (a[l] != x) print l
    2. else if (nxt[l] > r) print -1
    3. else print nxt[l]

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

    For each position in array remember the last position of a number different that what you have at that position(denote it d[i]), then for each query check if tab[r] != x — r is the answer, if tab[r] == x and d[r] >= l — answer is d[r], else -1

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

    What i did was to find maximum number in the interval.

    Then i also found minimum number in interval.

    If both are the same and they are equal to the number we dont want it to be equal to , we output -1.

    Else we look which of min and max are different from it and output one of them.

    But there are better solutions.

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

    I did it a long way by having 2 segment tree, one which reports the minimum and other which reports maximum in the range [L, R]. If both of them are equal and equal to x then print -1 else find the position of one not equal to x. Since the numbers range is [1,10**6], store indexes of each number in a vector and then binary search on them to find position. Complexity: O((n+m)logn)

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

    can be solved using DP in O(N+M) time. The idea is to calculate the maximum length of subarray for each position such that the subarray contains the same number as the one in that position. You can do this in O(N) time

    Then for each query go to array[l] . If this is not equal to x, tada! else jump to the position denoted by array[l] and the length of the precalculated subarray for position l. If this is within range, return the position, else -1

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

How to solve E?

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

    Consider all children of 1, let them be v. We can calculate answers for each v separately, taking the maximum answer.

    Now, for each v, find all leaves that belong to v, and record their distance. Sort them in decreasing order, and the answer is max(d[i]+i) for 0-based distance array. The reason is that we can think in reverse way: the ants move from root to leaves, and we always want the furthest ant to move first.

    Btw, this question has appeared (exact problem) some year ago in a chinese contest.

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

      I am not doing chinese contests, but It looks as right decision to put this task on educationl round :)

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

How to solve F?

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

Hi- distance cantst got hold down.

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

How to determine the index of min element in algorithm segment tree? Is it right? My code for problem C

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

Are there at all any test cases for which an answer might fail (after passing the pretests) for the problems A and B? It's been almost 5 hours now and I have tried everything but in the end it seems that the pretests cover up almost everything for both the problems!

PS: Don't confuse this with me asking for helps to hack other's solutions. All I merely am asking is a yes or no to the question. Thanks! :)

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

Wow, I use to teach how to calculate interpolating polynomials, but in a straight-forward way...

Couldn't believe they could be used in competitive programming until now!

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

Problem C have really tight time limits. I wrote O(N) solution in Java and it exceeded the time limit on test 20. It only passed when I moved the solution to C++ with scanf/printf.

I used BufferedReader and StringTokenizer in my java solution, so it's not a problem with slow Scanner class.

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

    There was no time limits problem in your solution. Actually you have used System class to print the output which is quite slow. Also you have used println which is slower especially when it is used directly by System class(writing on console sending bytes, flushing the screen etc). To make it faster create an instance of PrintStream class and use that instance to write to the console. print("\n") uses '\n' as linefeed character and println() terminate the string with new line character depending on the platform. Best to use is '%n' with printf() in java.

    15949731 15949638 15949630

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

Can someones guess, what hack test could be in B? halyavin have already successfully done 116 hacks:D

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

I completely overkilled C and got TLE as a return gift.

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

    My approach-

    Build a segment tree in nlogn where each node has a vector of elements of its subtree in sorted order. 2 adjacent segments will have sorted elements and so merging can be done in O(n) leading to a total build complexity of nlogn. Queries will find the range in a segment which has 'x' and then return an index outside this range. Complexity of each search is therefore log^2(n).

    I realized after contest that all we need is minimum and maximum of a range to find any position which does not have x . Stupid me :/

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

Have the solution been rejudged already? With the full test cases and the successful hacks?

EDIT: Spoke too soon

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

This is the first round that I can solve problem D, although I was not in the field.