Problem Link:
Author: Pavel Sheftelevich
Tester: Kanstantsin Sokal
Editorialist: Sunny Aggarwal
Difficulty:
Easy
Pre-Requisites:
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[i-1] + 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[i-1];
Y[i] = y[i] + Y[i-1];
}
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.