COULDN'T THINK OF THE CORRECT SOLUTION

#1

I TRIED BUT COULDN’T THINK OF OPTIMIZED SLUTION FOR THIS QUESTION…

#2

@kaushikjatin
lets say we are considering a pair (x,y) of soldiers who communicate
assume x<y, so |x-y| = (y-x)
now we have 2 cases.
Case 1: b >= c
in this case the answer will simply be (y-x)*b, so total cost for this case is
sigma (y(i) - x) *b
simplifying further, we get sigma (y) b - x b (number of soldiers having less bombs than current soldier)
To answer this one, we require 2 things:

  1. number of soldiers lying ahead having less bombs
  2. sum of their positions
    this can be answered with segment tree / fenwick tree.

Case 2: b < c
total cost for this case is
sigma [(y(i) - x) * c(i)]
simplifying:
sigma [y(i) c(i)] - sigma [x c(i)]
= sigma [y(i) c(i)] - x (sigma c(i) )
the first term can be found out by precomputing all y(i)*c(i) values, and proceeding in a similar way

#3

Thnx bro…I got it…I will try with it…

1 Like