PRUGREMMER's blog

Help needed with this question
By PRUGREMMER, history, 4 years ago, In English

There are N soldiers located on our X-AXIS. The point at which soldier is located also has some number of bombs. The war is near and every soldier wants to communicate with every other soldier. If the ith soldier has b number of bombs and is located at position X then the cost of communicating with any other soldier j having c number of bombs located at position Y is defined as |X-Y|*max(b,c). Find the sum of costs of communication if every soldier wants to communicate with every other soldier. NOTE :- You have to consider pair(i,j) only once in sum of costs. Input Format

First line consists of number of test cases T. Each test case consists of three lines. The first line indicates the number of soldiers (N). The second line indicates the coordinates of the N soldiers ( X[i] ). The third line contains the number of bombs at every soldiers location ( B[i] ) . The x-coordinates needn't be in increasing order in the input. Constraints

1 <= T <= 20 1 <= N <= 200000 1 <= X[i] <= 1000000000 1 <= B[i] <= 10000 Output Format

The total cost modulo 10^9+7. Sample Input

1 3
1 3 6
10 20 30

Sample Output

280

Explanation

there are 3 pairs (1,2) -> cost = abs(3-1) * 20 = 40 (1,3) -> cost = abs(1-6) * 30 = 150 (2,3) -> cost = abs(3-6) * 30 = 90 sum = 40 + 150 + 90 = 280

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

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Move to the right and keep sum of coordinates for each amount of bombs up to the current point , along with the amount of soldiers with such bombs. Then it's just a matter of simple querying and multiplication. Repeat the same process moving to the left now and ignoring soldiers with the same amount of bombs.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • We can sort the arrays x and b in the increasing order of x[i].
  • Now we can compute the cost of other soldiers communicating with the Nth soldier.

The cost will be (x[n]-x[n-1])*b[n] + (x[n]-x[n-2])*b[n] + ... + (x[n]-x[1])*b[n].

If we rewrite the above equation, we will get ((n-1)*x[n] - (x[1]+x[2]+...+x[n-1]))*b[n].

Now (x[1]+x[2]+...+x[n-1]) can be done in O(1) with the help of prefix sums.

  • We can repeat the above step to calculate the cost for other soldiers also.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It won't be multiplied always by b[n] because the previous soldier might have more bombs, and we always multiply by the maximum bombs. That's why we need to store sums of coordinates using a Fenwick Tree or Segment Tree.

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

      My bad. Sorry. Didn't notice that it was max(b, c). You are right and thanks.

      → Reply