# PPCTS - Editorial

#1

Author: Pavel Sheftelevich
Tester: Kanstantsin Sokal
Editorialist: Sunny Aggarwal

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.

d = |x_1 - x_2| + |y_1 - y_2|

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

d = |x-x_1| + |y-y_1| + |x-x_2| + |y-y_2| + |x-x_3| + |y-y_3| + ... ... +|x-x_N| + |y-y_N|

or

d = |x-x_1| + |x-x_2| + |x-x_3| + ... +|x-x_N| + |y-y_1| + |y-y_2| + |y-y_3| + ... +|y-y_N|

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

d_x = |x-x_1| + |x-x_2| + |x-x_3| + ... +|x-x_N|

or

d_{x} = \sum_{\substack{ x_i <= x}}{x - x_i} + \sum_{\substack{ x_i > x}}{x_i - x}

More formally, for a given x, d_x can be calculated as follows:

d_x = c_1 * x - sum_1 + sum2 - (N - c_1) * x

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* = sumX[i-1] + X*;
}

// 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)).

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*, y*);
}

sort(x.begin()+1, x.end());
sort(y.begin()+1, y.end());

for(int i=1; i<=N; i++) {
X* = x* + X[i-1];
Y* = y* + Y[i-1];
}

int u, v;
u = v = 0;

scanf("%s", s+1);

for(int i=1; i<=M; i++) {

switch( s* ) {
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
", tot);
}
return 0;
}


### Time Complexity:

O(Nlog(M)+Mlog(M))

O(N)

### 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.

#2

Can be done in O(1) per query

#3

May be O(Nlog(N)+Mlog(N)) ?

#4

Nice solution but it works only when the coordinates given in the question consist of only integers. The solution in editorial is a more generalised one.

#5

corrected. It should be O(Nlog(M)+Mlog(M))