Problem Link:
Author: Pavel Sheftelevich
Tester: Kanstantsin Sokal
Editorialist: Sunny Aggarwal
Difficulty:
Easy
PreRequisites:
Sorting, Geometry, Dynamic Programming, Prefix sums, Theory of Distances.
Problem Statement:
Given 2 lists L_1 and L_2 containing of M and N pairs of 2 dimensional coordinates (x, y). For each coordinate in list L_1, calculate the sum of manhattan distances from each point in list L_2 to this point.
Brief Explanation:
For each coordinate in list L_1, calculate its manhattan distance along X axis and Y axis separately from all coordinates in list L_2 and sum them up to get the actual answer.
Explanation:
Manhattan distance d between the 2 coordinates say (x_1, y_1) and (x_2, y_2) is given by following expression.
similary, manhattan distance d of a coordinate (x, y) from N other coordinates (x_1, y_1), (x_2, y_2) ... (x_N, y_N) is given by the following expression
or
It is easy to notice that we can get the actual manhattan distance by calculating the distance along X axis and Y axis separately.
Lets calculate the distance of a point (x, y) from all N points along X axis. Calculating distance along Y axis is identical.
distance along X axis (say d_x) is given by
or
More formally, for a given x, d_x can be calculated as follows:
where,

c_1 denotes the count of $x_i$s \le x.

sum_1 denotes the sum of $x_i$s \le x.

sum_2 denotes the sum of $x_i$s \gt x.
for a given x, c_1, sum_1 and sum_2 can be efficiently computed using binary search over sorted list of $ x_i$s as follows.
int X[N+1]; // given x_i s long long int sumX[N+1]; // extra array to compute sum1 and sum2 efficiently sort(X+1, X+1+N); // sort all the x_i s for(int i=1; i<=N; i++) { sumX[i] = sumX[i1] + X[i]; } // now for a given x, calculate d_x as shown below int id = upper_bound(X+1, X+1+N, x)  (X+1); // id denotes the count c1 long long int sum1 = sumX[id]; // calculating sum1 long long int sum2 = sumX[n]  sum1; // calculating sum2 long long int dx = c1 * x  sum1 + (n  c1) * sum2; // calculating dx
Note that we need to sort and maintain sum just once and thereafter, every d_x and d_y can be computed in O(log(N)). So overall complexity is O(N\log(N)+M\log(N)).
You can read more about upper_bound function here.
Complete C++ code:
const int maxn = 3 * 1e5 + 10; long long int X[ maxn ], Y[ maxn ]; char s[ maxn ]; int main() { int N, M; cin >> N >> M; vector x(n+1), y(n+1); for(int i=1; i<=N; i++) { sc2(x[i], y[i]); } sort(x.begin()+1, x.end()); sort(y.begin()+1, y.end()); for(int i=1; i<=N; i++) { X[i] = x[i] + X[i1]; Y[i] = y[i] + Y[i1]; } int u, v; u = v = 0; scanf("%s", s+1); for(int i=1; i<=M; i++) { switch( s[i] ) { case 'L': u ; break; case 'R': u ++; break; case 'U': v ++; break; case 'D': v ; break; } int cntx, cnty; long long int tot = 0; cntx = upper_bound(x.begin()+1, x.end(), u)x.begin()1; cnty = upper_bound(y.begin()+1, y.end(), v)y.begin()1; tot += 1LL * cntx * u  X[cntx]; tot += X[n]  X[cntx]  1LL * ( n  cntx ) * u; tot += 1LL * cnty * v  Y[cnty]; tot += Y[n]  Y[cnty]  1LL * ( n  cnty ) * v; printf("%lld\n", tot); } return 0; }
Time Complexity:
O(Nlog(M)+Mlog(M))
Space Complexity:
O(N)
Similiar Problems:
Solution:
Setterâ€™s solution can be found here
Testerâ€™s solution can be found here
Feel free to post comments if anything is not clear to you.