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

Автор E404_Not_Found, 21 месяц назад, По-английски

Hello everyone!

Thanks for participating in TheForces Round #5 (PerfectForces).

[problem:425963A]

Editorial

[problem:425963B]

Editorial

[problem:425963C]

Editorial

[problem:425963D]

Editorial

[problem:425963E]

Editorial

[problem:425963F]

Editorial

[problem:425963G]

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

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

For problem F we can use a sieve to precalculate the number of divisors of each number from 1 to N.

My submission

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

can anyone explain D question i m not getting editorial

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

    First sentence of editorial means that: $$$a_1$$$ & $$$\ldots$$$ & $$$a_n=x\implies\forall i:a_i=x$$$ | $$$smth_i$$$

    & will keep only the bit which is present in all operands. You, probably, got it.

    Second sentence of editorial means that: $$$smth_1$$$ & $$$\ldots$$$ & $$$smth_n = 0$$$

    There is no benefit of having some bit in all $$$smth_i$$$. And the other reason is that the first equality will not hold (smth is smth, but smth is not any). I quess, you fiqured it out during a contest. Now:

    Third sentence: We want minimum $$$a_n$$$. Bits that are set in x also are set in $$$a_i$$$. What is the minimum possible $$$a_1$$$? Well, we can take $$$a_1=x$$$. What is minimum possible $$$a_2$$$? we can take $$$a_1$$$ and set 'the least significant' zero-bit in it to one. What is minimum possible $$$a_3$$$? We take $$$a_1$$$ and set 'the next least significant' zero-bit to one. What is minimum possible $$$a_4$$$? We take $$$a_1$$$ and set both 'the least significant' and 'the next least significant' zero-bit to one. Now you need to notice that $$$a_i$$$ are constructed in a way of filling empty slots (zero-bits) of $$$a_1$$$. So if we want to make $$$m$$$ steps from $$$x$$$ we need to look at a binary representation of $$$m$$$ and fill this representation in empty slots of $$$x$$$.

    For example:

    $$$x=100101_2$$$

    $$$m=4=100_2$$$

    Then:

    $$$a_1=x$$$

    Empty slots of $$$x$$$ are $$$1[0][0]1[0]1_2$$$

    And $$$a_{1+m}=a_5$$$ will be $$$1[1][0]1[0]1_2$$$

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

      what will be the values of a for x u have taken in example

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

        Your guess..

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

          100101 100111 101101 101111 110101

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

            i got much of the solution but checking on binary representation of m how will this help?

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

              So you know what to do on paper, but don't know how to instruct a machine to do the same? I think the more problems on bit manipulation you encounter, the more 'manipulative' in regard to bits you will become. You can look at program text, if you wish. I don't think my explanation will be more clear then the code.

              Binary representation of m is needed to know what to insert in empty slots of $$$x$$$. In initial problem we need to find $$$a_n$$$ that means that we need to make $$$n-1$$$ steps from $$$a_1=x$$$. We can say that to solve initial problem we consider $$$m=n-1$$$. To implement this we traverse index on $$$m$$$ and for it we search for empty slot of $$$x$$$ with the help of while-loop.

              The intuition is simply we write $$$m$$$ inside $$$x$$$.