akzytr's blog

Pleasant pairs -> O(n log n)
By akzytr, history, 2 weeks ago, In English

This problem:1541B - Pleasant Pairs

Editorial has the following statements:

Number of pairs(a, b) such that a*b <= 2*n is equal to

2n / 1 + 2n/2 ... where the denominator goes till 2*n.

Time complexity is said to be o(n log n), it did mention harmonic numbers, however I am having a hard time making the connection? Is this somehow in context to https://codeforces.com/blog/entry/118001 where they explain upper bound?

Any help appreciated

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 weeks ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it
$$$ \sum \limits_{i = 1}^{2n} \frac{2n}{i} $$$
$$$ = 2n \sum \limits_{i = 1}^{2n} \frac{1}{i} $$$

Let's just ignore $$$2n$$$, because we can multiply the final answer by $$$2n$$$.

And I will use another way to describe it to answer your question easier.

$$$ \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots $$$
$$$ \le \frac{1}{1} + 2\frac{1}{2} + 4\frac{1}{4} + 8\frac{1}{8} \cdots $$$

We can see the sum of the first $$$2n$$$ fractions of $$$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots$$$ is approximiately $$$\log_2 2n$$$.

Then multiply this by $$$2n$$$, we get $$$2n \log_2 2n = O(n \log n)$$$.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    And we can find that $$$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$$$ is actually $$$H_n$$$ in https://codeforces.com/blog/entry/118001.

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When we say log, is it base 2? base 10? apologies, I did try simulations to calculate with ln, essentially tried a variation of ln(n), ln(2n)

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I have fixed, and note that in $$$O()$$$, we don't need the base because:

        $$$ \log_b x = \frac{\log_c x}{\log_c b} $$$

        and $$$c, b$$$ are constants.

        → Reply
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hmm, interesting. I thought that as long as the constant c, ie log(base c)(x) / log(base c)(b), is log(base b) x, which you have shown in your equation, but how does that mean that the actual base doesn't matter in O(), log2 and log10 are different things either way?

          Feel free to correct me in every way possible.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ok, actually the big O notation is not concerned in constants, and $$$\log_c b$$$ is literally a constant.

            → Reply