Cover them all problem

#1

I want hint for this problem. Actually i want to know how to get |x-y| in O(n) . How to use fenwick tree here?

#2

@nayakashutosh99
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

Okay got it. Thank you very much!!

1 Like