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

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

Привет Codeforces!

Мы вернулись и как и в прошлом году, проводим Bubble Cup — соревнование по программированию организуемое силами Центра разработки Microsoft в Сербии (Microsoft Development Center Serbia) на протяжении последних 9 лет. И финал этого года уже на этой неделе!

Учитывая прошлогодний успешный опыт мы вновь решили провести зеркало этого финала на Codeforces! Мы хотели бы поблагодарить MikeMirzayanov и команду Codeforces за замечательную платформу, а также их поддержку в подготовке и проведении. Соревнование начнется 11-ого сентября в воскресение в 11-00 12-00 утра (по Московскому времени). Длительность контеста — 5 часов, будут использоваться правила ACM ICPC. Это будет командный контест на Codeforces, между командами (1-3) человек. Количество задач 9.

Контест подготовлен силами работников MDCS и участниками knightL и Milanin. + спасибо bayleef и vitar за помощь в тестировании.

В виду того что правила этого контеста не совсем обычны для Codeforces (и в виду того что это зеркало) контест будет нерейтинговым.

10 Лучших команд получат футболки (каждому члену команды) +10 футболок будут разданы случайно командам из топ-100.

Обратите внимание что время начала контеста 12:00 по Московскому времени

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

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

Автокомментарий: текст был обновлен пользователем ibra (предыдущая версия, новая версия, сравнить).

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

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).

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

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).

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

А случайные футболки тоже каждому члену команды или одна на команду? :)

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

Inb4 >rated?

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

    ?

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

      Greentext = quoting, inb4 = short for "in before"; full meaning: I expect someone to ask if it's rated because they're too lazy to read the whole blog post.

      UPD: Explaining when asked for an explanation = downvotes. Yep, just a normal day in CF comments.

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

Совпадает с тренировкой. А у тренировки анонс появился раньше.

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

Will there be hacks? Will all submissions be tested by system tests during the contest?

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

.

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

    Недавно был переход какого-то региона РФ в другой часовой пояс вроде, но я как клятый москаль не следил за деталями конечно)

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

      .

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

        А какая часовая зона стоит на вашем компьютере? Либа, которая, правит время исключительно client-side, работает в вашем браузере на JS.

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

          Если кликнуть на время, на timeanddate будет написано 12МСК.

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

          .

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

            Я живу в московском часовом поясе, и у меня время начала соревнования показано 12:00. Надеюсь, с этой путаницей скоро разберутся.

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

"Это будет командный контест на Codeforces, между командами (1-3) человек. Количество задач 9."

Эм, а почему тогда есть возможность зарегистрироваться ТОЛЬКО как индивидуальный участник?

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

Now, there is no option for teams :)

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

Will there be live stats board?

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

    results of Buuble cup onsite will be revealed after the competition.

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

1 PC per team?

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

I thought that the mirror is going to be today. Now I have to wait until I can do a rage post about some amazing problems in the problemset... :(

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

Автокомментарий: текст был обновлен пользователем ibra (предыдущая версия, новая версия, сравнить).

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

Auto comment: topic has been updated by ibra (previous revision, new revision, compare).

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

i hope i will enjoy :) this is my first time :)

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

i hope i will enjoy . this is my first time :)

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

what is the difficulty of problems ?

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

    Difficulty is that both divisions can participate. If you competed in last year's mirror, than i would say that difficulty is the same

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

Is it a rated contest?

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

А есть тут такие же как я одиночки, желающие объединиться в команду? Конечно сыгранности никакой, но, возможно, вместе наши шансы выше :)

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

"будут использоваться правила ACM ICPC"

Одновременно можно использовать только один компьютер на команду, я правильно понимаю?

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

very hard problem set. matter of satisfaction that it is unrated.

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

How to solve the first problem?

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

    you have to reverse the given sequence at first. then multiply every term with non reverse one and at lust add all the product. thats the answer.

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

    You just need to use magic numbers!

    20534967

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

      What do you mean by magic numbers?

      During the contest, we came up with a summation similar to the following:

      where Fi is the ith Fibonacci number. Is this correct? If yes, how to implement it? :/

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

        It can be proved simply using recursion the answer is , where s(n, k) is the coefficient of xk in the expansion of x(x - 1)...(x - n + 1) (Stirling numbers of the first kind). We precalculate s(k, j) easily. Hence it suffices to to be able to find for powers 0 ≤ p ≤ k. This can be done using Binet's formula + binomial theorem + geometric series sum. Use a struct to add, subtract, pow, inv, etc for for this purpose. I won't go through the tedious work, but the complexity I think works out to be O(k2).

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

      Can you please provide any link where I can learn about these numbers?

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

How to solve problem G ? :\

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

    You can transform the problem in to :

    Given some intervals, each interval cover some points and has a weight. Select a subset of the intervals such that the sum of weight is maximized and there isn't exist any point being covered more than x times.

    And this is a classic min cost flow problem.

    Node i represent position i in the crossword. Let the interval as from a to b with w weight.

    So you should calculate each interval. If crossword[i .. j] equals the word, add interval (i, j + 1, points of the word).

    First add edge with x capacity and 0 cost from source to node 0 and from node n to sink. Then add edge with infinite capacity and 0 cost from i to i + 1 for every i < n. Then for each interval add edge with 1 capacity and -w cost from a to b.

    The answer is the negative value of min cost flow from source to sink.

    This is correct because there is only x flow present. So it restricted each position will not be covered more than x times. And the flow tends to go to the negative edge, so it will give out the minimum value.

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

How to solve problem D ?

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

    To win the game, the xor of the pile sizes must not be zero. So we find the probability that xor of pile sizes is zero and subtract it from 1.

    Consider dp[i][j] which denotes the probability to get xor j for first i piles. The straightforward recurrence is:

    dp[i][j]=sum dp[i-1][j^k]*p[k] from k=0 to 100

    where ^ is the bitwise xor operator.

    But this is not good enough for the problem. We can do better. To calculate dp[i][j], divide i into two piles of size i/2. Then,

    dp[i][j^k]+=dp[i/2][j]*dp[i/2][k]

    Above is true when i is even. You need to modify it a little when i is odd.

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

      Thank you, got it

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

      Could you, please, elaborate a bit more. Why xor of pile sizes must be zero?

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

        Sprague-Grundy theorem.

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

          Ok, understood.

          Now I have difficulties with the next thing below :)

          Could you explain how this thing works:
          dp[i][j] =  dp[i - 1][jk] * p[k]

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

            a^a = 0 (xor operation)
            a^0 = a

            ((j^k)^k)=j

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

              Wow, I feel very stupid now.
              I am sorry, but I still don't understand how this dp works :(

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

                First player lose if xor of N pile sizes equals to 0.

                So you want to know probability, that xor of i pile sizes equals to j

                (Answer will be 1 — dp[n][0]).

                This fact can be possible if

                • i-th pile have size 0 and xor of [i — 1] pile sizes equals to (j xor 0).
                • i-th pile have size 1 and xor of [i — 1] pile sizes equals to (j xor 1).
                • ...
                • i-th pile have size 1 and xor of [i — 1] pile sizes equals to (j xor x).

                Facts are independent, so total probability is simply sum of probabilities.

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

      I did the same, but then I thought we must multiply by n! because permutations will matter, so then I completely got confused about how to incorporate n! with fast expo.

      btw, its dp[i][j^k]+=dp[i/2][j]*dp[i/2][k]

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

How to solve problem E ?

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

    As there is always a solution and the size of it doesn't matter,

    Do a normal DFS traversal , print each vertex you visit and change the color of it . Once you finish from a child print the current vertex again and change it's color because you will back to it , and if this child's color is pink then visit it again (without it's sub tree)

    you have to stop at node 1 or one of it's children , after visiting the last child of node 1 if color[1] is pink then back to it otherwise stop at this child .

    this code may help : 20538605

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

How to solve H?

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

Can someone please tell me why my same code for D get TLE and AC in different compilers? Thanks!

AC code: http://codeforces.net/contest/717/submission/20529231

TLE code: http://codeforces.net/contest/717/submission/20529203

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

    Your p[100] array is too short, iterating k up to 128 causes undefined behavior.

    The compiler does warn you about this. Use and read the warnings.

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

I do like the problems~ so interesting! and it's really lucky to get into the top50~ thanks for the competition ^_^

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

Problem H: Why does randomly dividing trainers into teams and then randomly dividing teams into two conferences work?

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

    wait for editorial, all explanations will be there

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

    Because pretty much anything in this problem works so you can either spend hours to solve it properly, which in this case is a solution with guaranteed probability, ir just try to submit anything and get AC.

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

    Because the expected number of "crossing" edges in a random team and conference distribution is equal to .

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

      Doesn't the expectation depend on input i.e. wishlist of each trainer and hate pairs?

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

Can someone tell me how to solve G ? I know that is a min cost flow problem but I don't know how to build the network.

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

Check out this amazing solution that I discovered for problem D!

Complexity: O(XlogX)

It will be featured in the BC 2016 booklet, along with the proof.