Destopia's blog

How to solve this problem?
By Destopia, history, 3 years ago, In English

Given an array of $$$n \leq 10^5$$$ integers. $$$a_1, a_2, \dots a_n$$$. $$$f(i)$$$ is defined as follows:

  • Take the first $$$i$$$ elements $$$a_1, a_2, a_3, \dots a_i$$$, sort them in nondecreasing order. Let's call resulting prefix after sort $$$s$$$

  • Let $$$f(i) = 1 \times s_1 + 2 \times s_2 + 3 \times s_3 + \dots + i \times s_i$$$.

We're asked to calculate $$$f(1) + f(2) + \dots + f(n)$$$ $$$\bmod 10^9 + 7$$$.

Example $$$n = 4$$$ and array $$$[4, 3, 2, 1]$$$

$$$f(1) = 1 \times 4 = 4$$$

$$$f(2) = 1 \times 3 + 2 \times 4 = 11$$$,

$$$f(3) = 1 \times 2 + 2 \times 3 + 3 \times 4 = 20$$$

$$$f(4) = 1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 4 = 30$$$

$$$f(1) + f(2) + f(3) + f(4) = 4 + 11 + 20 + 30 = 65$$$.

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Is there a place where I can submit and test my code for it?

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

    Unfortunately no, this problem was in hackerrank problem solving intermediate certification test.

    Someone posted it in Leetcode: Link

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      Suppose you know the value of $$$f(i)$$$, now how can we compute $$$f(i+1)$$$?
      Now, assume that there are $$$K$$$ numbers less than or equal to $$$A_{i+1}$$$ and $$$i-K$$$ numbers greater than $$$A_{i+1}$$$ in the $$$i$$$ numbers you have encountered so far.

      $$$A_i$$$ will increase the answer by $$$(K+1) * A_{i+1}$$$. For the numbers greater than $$$A_{i+1}$$$, they will increase the overall answer by the sum of all these $$$i-K$$$ numbers. This sum can be kept track of using a Segment Tree.

      PS: I haven't tested the solution, so probably take it with a pinch of salt.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry for my poor English and I'm not skilled in LaTeX too.

So think about it, when you have already known $$$f(k)$$$, just insert $$$a_{k+1}$$$ into the sorted list. The contribution to the answer caused by $$$a_{k+1}$$$ is easy to calculate by binary search the sorted list, and then insert $$$a_{k+1}$$$ into it. And you will see, for every element $$$s$$$ in the sorted list, it will shift to the next position when and only when $$$s \geq a_{k+1}$$$.

Thus, $$$f(1) = a_1$$$, and you will see $$$f(k + 1) = f(k) + \sum\limits_{i=1}^{k}\max(a_i, a_{k+1})$$$.

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

    Well you may need some data structures, but I'm not really good at it.

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

    Sorry that I made a big mistake. I thought I have to calculate every single $$$f(k)$$$!

    Well, you can see that the answer is

    $$$a_1 + \sum\limits_{i=2}^{n}\sum\limits_{j=1}^{i-1}\max(a_i, a_j)$$$ so it will be easy to solve.

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

      This comment itself is the biggest mistake. I don't know how could I think about it.

      → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This can be done using treaps in $$$O(nlogn)$$$

→ Reply